Comment puis-je combiner des polygones complexes ?

Question

Étant donné deux polygones :

POLYGONE((1 0, 1 8, 6 4, 1 0))
POLYGONE((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

Comment puis-je calculer l'union (polygone combiné) ?

Exemple de Dave utilise SQL server pour produire l'union, mais j'ai besoin de réaliser la même chose en code. Je recherche une formule mathématique ou un exemple de code dans n'importe quel langage qui expose les maths réels. J'essaie de produire des cartes qui combinent dynamiquement des pays en régions. J'ai posé une question connexe ici : Regroupement de formes géographiques

Answer 1

C'est une très bonne question. J'ai implémenté le même algorithme en c# il y a quelque temps. L'algorithme construit un contour commun de deux polygones (c'est-à-dire, construit une union sans trous). Le voici.

---

Étape 1. Créer un graphe qui décrit les polygones.

Entrée : premier polygone (n points), deuxième polygone (m points). Sortie : graphe. Sommet - point de polygone du point d'intersection.

Nous devons trouver des intersections. Itérer à travers tous les côtés des polygones dans les deux polygones [O(n*m)] et trouver des intersections.

• Si aucune intersection n'est trouvée, ajoutez simplement des sommets et connectez-les au bord.

• Si des intersections sont trouvées, triez-les par longueur jusqu'à leur point de départ, ajoutez tous les sommets (début, fin et intersections) et connectez-les (déjà dans l'ordre trié) au bord.

Étape 2. Vérifier le graphe construit

Si nous n'avons trouvé aucun point d'intersection lorsque le graphe a été construit, nous avons l'une des conditions suivantes :

1. Le polygone1 contient le polygone2 - retourne le polygone1
2. Le polygone2 contient le polygone1 - retourne le polygone2
3. Le polygone1 et le polygone2 ne s'intersectent pas. Retourne le polygone1 ET le polygone2.

Étape 3. Trouver le sommet en bas à gauche.

Trouvez les coordonnées x et y minimum (minx, miny). Ensuite, trouvez la distance minimale entre (minx, miny) et les points du polygone. Ce point sera le point en bas à gauche.

Étape 4. Construire le contour commun.

Nous commençons à parcourir le graphe à partir du point en bas à gauche et continuons jusqu'à ce que nous y retournions. Au début, nous marquons tous les bords comme non visités. À chaque itération, vous devez sélectionner le point suivant et le marquer comme visité.

Pour choisir le point suivant, choisissez un bord avec un angle interne maximum dans le sens antihoraire.

Je calcule deux vecteurs : le vecteur1 pour le bord actuel et le vecteur2 pour chaque bord non visité suivant (comme présenté dans l'image).

Pour les vecteurs, je calcule :

1. Produit scalaire. Il retourne une valeur liée à un angle entre les vecteurs.
2. Produit vectoriel. Il retourne un nouveau vecteur. Si la coordonnée z de ce vecteur est positive, le produit scalaire me donne un angle droit dans le sens antihoraire. Sinon (la coordonnée z est négative), je calcule l'angle entre les vecteurs comme 360 - l'angle du produit scalaire.

En résultat, j'obtiens un bord (et un prochain sommet correspondant) avec l'angle maximum.

J'ajoute à la liste de résultat chaque sommet traversé. La liste de résultat est le polygone d'union.

Remarques

1. Cet algorithme nous permet de fusionner plusieurs polygones - d'appliquer de manière itérative avec des paires de polygones.
2. Si vous avez un chemin composé de nombreux courbes de Bézier et lignes, vous devez d'abord aplatir ce chemin.

Answer 2

Vous devez déterminer quels points se trouvent à l'intérieur. Après avoir retiré ces points, vous pouvez insérer un ensemble de points "extérieurs" dans l'autre. Vos points d'insertion (par exemple, là où vous avez la flèche dans l'image à droite) sont les points que vous avez dû retirer des ensembles d'entrée.

Answer 3

Essayez gpc.

Answer 4

Bonne question! Je n'ai jamais essayé cela auparavant, mais je vais essayer maintenant.

Premièrement: Vous devez savoir où ces deux formes se chevauchent. Pour ce faire, vous pourriez regarder chaque bord de Polygone A et voir où il croise un bord de Polygone B. Dans cet exemple, il devrait y avoir deux points d'intersection.

Ensuite: Créez la forme de l'union. Vous pouvez prendre tous les sommets de A et B, ainsi que les points d'intersection, puis exclure les sommets contenus par la forme finale. Pour trouver ces points, il semble que vous pourriez simplement trouver n'importe quel sommet de A qui est à l'intérieur de B, et tout sommet de B qui est à l'intérieur de A.

Answer 5

Une solution que j'ai vue en utilisant des BSP trees est décrite ici.

Fondamentalement, il décrit l'intersection en termes d'une union des arêtes du polygone A qui sont à l'intérieur du polygone B (y compris les arêtes partielles, et calculées en utilisant un arbre BSP). Ensuite, vous pouvez définir A / B comme ~(~A /\ ~B), où ~ indique l'inversion du sens du polygone, / indique l'union et /\ indique l'intersection.