Opérations booléennes sur les polygones rectangle

Question

Avast y a d'autres programmeurs!

J'ai le problème suivant:

J'ai deux rectangles qui se chevauchent, comme indiqué sur l'image ci-dessous.

Je veux comprendre le polygone constitué du point ABCDEF.

Autre description de Noël: Le coupe-biscuits rouge coupe un peu le biscuit noir. Je veux calculer le cookie noir.

Chaque rectangle est une structure de données avec 4 sommets 2d.

Quel est le meilleur algorithme pour y parvenir?

Answer 1

Ceci est un cas particulier de découpage de polygones 2D général. Un bon point de départ est l'algorithme de Weiler-Atherton. Wikipedia has a summary et links to the original paper. L'algorithme semble correspondre assez bien à la structure de données que vous avez décrite. Notez qu'il est tout à fait possible que vous vous retrouviez avec un rectangle avec un trou dedans (si le rouge est entièrement à l'intérieur du noir) ou même deux rectangles (par exemple si le rouge est plus grand et plus maigre que le noir). Si vous êtes certain qu'il n'y a qu'un coin du rectangle rouge à l'intérieur du noir, alors la solution devrait être beaucoup plus simple.

Answer 2

constructive solid geometry

Answer 3

J'ai trouvé quelques trucs ici, je pourrais utiliser:

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

J'ai téléchargé en fait la source CGAL avant même posté cette question, mais je crois que je vais regarder de plus près en elle.

Answer 4

Quelle est la précision des coordonnées? Si les rectangles sont assez petits, l'approche la plus simple pourrait être de les peindre sur une toile, d'abord en rectangle noir, puis en rouge. Les pixels noirs restants sur la toile sont le polygone qui reste. Une autre approche consiste à diviser la grille de coordonnées en un groupe de rectangles basés sur tous les côtés des rectangles (sans compter les rectangles non bornés, vous avez jusqu'à 9 rectangles générés si vous avez deux rectangles d'origine). Il suffit ensuite de tester un point représentatif de chacun de ces rectangles pour l'appartenance aux polygones particuliers afin de déterminer quels rectangles sont entrés et lesquels sont absents.