Générer Graphique de Connected Convex Polygones

Question

Je suis en train de prendre un graphique dense de points tels que cette , et tournez dans un graphique de polygones convexes connectées. Les polygones doivent être aussi grand et aussi simple que possible tout en restant connecté. Le graphique résultant sera utilisé pour pathfinding. point que quelqu'un peut me dans la bonne direction?

Answer 1

Il est très ennuyeux que je ne peux pas poster des liens. Il est difficile d'être un Rôdeur et que participator occasionnel.

Je fini par utiliser les techniques suivantes:

Tout d'abord, créez une transformation de distance. Je l'algorithme décrit ici [ne peut pas lier], entraînant une image comme celle [lien ne peut pas]. Ensuite, créez un bassin versant transform du DT pour le diviser en zones. Ce besoin de quelques travaux, mais il semble actuellement comme ça [ne peut pas lier] Ensuite, utilisez les points médians des polylignes reliant chaque paire de zones, pour créer un graphique de point de passage.

Résultat

Le partitionnement des bassins versants est pas encore parfait, notez le aliasing causant des bandes, mais je me retrouve avec 181 zones et 281 points de passage pour cette carte 128x128.

Answer 2

Ce n'est pas ce que vous avez demandé, mais voici quelques autres idées pour résoudre ce problème de planification de trajectoire 2D:

• Utiliser A *. Cela donne le chemin le plus court sans collision. Les performances peuvent être OK, même sans simplification du bitmap.

• Utilisez un feuille de route basée sur l'échantillonnage . Ceci est une autre représentation discrétisée que les polygones. Étant donné que votre espace de recherche est petite, vous pouvez traverser le bitmap entier pour vérifier que chaque point peut être connecté à la feuille de route. Si un compact feuille de route est importante (mais les chemins courts ne sont pas), le la technique de feuille de route de visibilité peut être utilisée.

Puisque vous avez à traiter avec une représentation graphique et graphique la recherche de toute façon, ces techniques semblent beaucoup plus facile que l'extraction des polygones. Je dégoté quelques questions SO pour ce problème:

• Convertir Bitmap à Polygon
• Comment puis-je convertir bitmap de forme simple vecteur

Lorsque l'espace a été localisé par des polygones (éventuellement à l'aide d'un outil), il peut être divisé en polygones convexes ou une autre représentation qui peut être recherchée. Ceci est également discuté par LaValle:

• Vertical (trapézoïdale) Cell décomposition
• -chemin feuilles de route Shortest