Relier deux polygones non-convexes convexes en un

Question

Je dois joindre deux polygones convexes, non-intersectants dans un polygone covex joint en minimisant la surface résultante, comme dans l'image ci-dessous: Je cherche un alhorithme faisant ceci. Je serais également reconnaissant si quelqu'un me fournir l'implémentation de Python correspondante.

Answer 1

S'il y a deux polygones disjoints ayant par exemple, m et n sommets respectivement, alors votre problème peut être considéré ainsi:

Trouver le polygone convexe de la zone la moins contenant tous les m + n points. Cela dit, consultez le QuickHull Algorithm ici: http://www.geeksforgeeks.org/quickhull-algorithm-convex-hull/

En outre, vous pouvez également consulter ces algorithmes.

algorithme de Jarvis: http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

Et, Scan Graham: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

Hope this helps.

P.S. Je pense que vous pouvez trouver les implémentations python de ces algorithmes n'importe où sur Internet. :)

Answer 2

Trouver la coque convexe des deux ensembles fonctionnerait, mais l'approche suivante est probablement plus rapide car il n'a besoin que de visiter les sommets des polygones dans l'ordre:

1. polygones Étant donné P et Q, choisir parmi tous les un sommet p1 et q1.

2. Chercher dans Q le sommet q2 accolée à q1 de telle sorte que la rotation p1-q1-p1-q2 est dans le sens horaire (ce qui peut être vérifié en utilisant easyly produit croisé du vecteur). Répétez jusqu'à ce que vous atteigniez un point qk dont les deux sommets contigus dans Q génèrent une rotation dans le sens contraire des aiguilles d'une montre.

3. Maintenant, inverser le processus se déplaçant de p1 à travers des sommets contigus dans P de sorte que la rotation soit dans le sens inverse des aiguilles d'une montre jusqu'à ce qu'une extrême pl soit à nouveau trouvée.

4. Répéter de 2 jusqu'à ce que plus aucune avance possible. Vous avez maintenant deux points pm et pn qui sont les deux sommets où un côté de la zone rouge rencontre les polygones noirs dans votre dessin ci-dessus.

5. Maintenant, répétez l'algorithme, mais en changeant les directions, dans le sens des aiguilles d'une montre vers la gauche et vice versa, afin de trouver les sommets pour l'autre côté de la zone rouge.

6. Le seul travail restant est de générer le polygone final à partir des deux côtés de la zone rouge déjà trouvés et les segments des polygones.

Answer 3

une solution efficace, vous pouvez adapter la méthode de la chaîne Monotone (https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain) comme suit:

• pour les deux polygones, trouver les sites les plus à gauche et à droite (en cas de liens, utilisez la le plus haut/le plus bas respectivement);

• ces sites divisent les polygones en deux chaînes, qui sont ordonnées sur X;

• fusionner les deux chaînes supérieure et deux chaînes inférieures avec des comparaisons sur X (c'est un passage de mergesort);

• rejeter les sites réflexes des chaînes supérieures et inférieures, en utilisant la même procédure que dans la méthode de la chaîne monotone (une variante de la marche de Graham).

La durée totale sera régie par

• comparaisons

  n + m pour trouver les extrêmes des sites;

• n + m comparaisons pour la fusion;

• n + m + 2 h Tests LeftOf (zone signée, h est le nombre de sommets du résultat).

Ainsi, la complexité est O (n + m), ce qui est optimal, mais très probablement assez bon pour vos besoins (une solution O plus sophistiquée (Log (n + m) est possible lorsque les polygones ne le font pas se chevauchent, mais ne vaut pas le bruit de la petite taille des polygones).

Dans l'exemple, le résultat des fusions ne sont que la concaténation des chaînes, mais des cas plus complexes peuvent survenir.

Remarque finale: si vous gardez tous les polygo ns comme la concaténation de deux chaînes monotones, vous pouvez épargner la première étape de la procédure ci-dessus.