Comment créer des arcs sur les points de délimitation de voronoi?

Question

Bonjour frères dans l'informatique? Je suis tout nouveau dans la programmation 2D.

J'écris un logiciel graphique 2D. Et dans mon projet j'ai utilisé l'algorithme de Voronoi. Et le résultat est correct comme je m'y attendais (Pic 1). Ensuite, je veux ajouter une fonctionnalité sur les points de limite comme (Pic 2). Donc je pense que j'ai besoin d'implémenter la coque concave sur les points de limites et de créer ensuite des arcs dessus.

Pic 1.

Mais ma coque concave ne fonctionne pas correctement en raison du paramètre de concavité. Quelle est la meilleure façon et le meilleur algorithme pour transformer mon résultat du logiciel dans Pic 2.

Pic 2.

Answer 1

Vous pouvez créer bitmap ab/w avec la coque concave et le comparer avec chaque point de la voronoi diagramme. J'ai utilisé une fonction php imagefilledpolygon dans mon tracé de contour de l'implémentation php: https://cntm.codeplex.com/.

Vous pouvez également essayer cette réponse et reconstruire les arêtes voronoï à la bordure, généralement les arêtes à l'infini: Colorize Voronoi Diagram.

Answer 2

Vous devriez être capable de faire une promenade autour du voronoi à la recherche de sommets avec seulement un seul bord adjacent (ce n'est pas une mauvaise idée de commencer avec un sommet qui n'a qu'un seul bord adjacent). Trouvez le premier, passez au suivant, puis reliez les bords avec un arc, répétez jusqu'à votre dos au premier bord. L'algorithme devrait être plutôt efficace O(N) si le voronoi est structuré comme un graphe.

La promenade:

La promenade se fait par le tri angle des bords et en prenant le bord suivant dans le sens horaire à celui que vous avez commencé sur.

Par exemple:

Si les angles (en degrés) sont 40, 50, 60, 70, et le bord previus était dans la direction du 50, alors vous suivez les 60 ou 40 bord (selon si vous avez décidé d'aller dans le sens des aiguilles d'une montre ou dans le sens inverse des aiguilles d'une montre), mais vous ne suivrez pas les 70, même si cela conduit à l'intérieur plutôt que de coller à l'extérieur.