Comment puis-je obtenir un dictionnaire de cellules de ces données de diagramme Voronoi?

https://stackoverflow.com/questions/9441007

12-11-2019
|

Question

Utilisation de la bibliothèque de génération de diagramme Voronoi / Delaunay a trouvé dans ce programme , qui est basé sur la mise en œuvre initiale de Fortune de son algorithme , avec un ensemble aléatoire de points en tant que données d'entrée, je suis capable d'obtenir les données de sortie suivantes:

une liste des bords de la Triangulation de Delaunay , ce qui signifie que pour chaque point d'entrée , Je peux voir quels points d'entrée sont ses voisins. Ils ne semblent pas être dans un ordre particulier.
une liste des sommets des paires de diagramme Voronoi , que je peux utiliser pour Dessinez le diagramme de Voronoi une ligne à la fois. Encore une fois, apparemment dans aucun ordre particulier.
une liste non nommée de paires de points , qui semble simplement être la même liste que 2, mais dans un ordre différent.
une liste des sommets formés dans le diagramme de Voronoi , également apparemment dans aucun ordre particulier.
Voici un exemple de données d'une analyse de test de mon programme à l'aide de cette bibliothèque:
Input points: 0 (426.484, 175.16) 1 (282.004, 231.388) 2 (487.891, 353.996) 3 (50.8574, 5.02996) 4 (602.252, 288.418) Vertex Pairs: 0 (387.425, 288.533) (277.142, 5.15565) 1 (387.425, 288.533) (503.484, 248.682) 2 (277.142, 5.15565) (0, 288.161) 3 (387.425, 288.533) (272.213, 482) 4 (503.484, 248.682) (637.275, 482) 5 (503.484, 248.682) (642, 33.7153) 6 (277.142, 5.15565) (279.477, 0) Voronoi lines?: 0 (279.477, 0) (277.142, 5.15565) 1 (642, 33.7153) (503.484, 248.682) 2 (503.484, 248.682) (637.275, 482) 3 (387.425, 288.533) (272.213, 482) 4 (277.142, 5.15565) (0, 288.161) 5 (387.425, 288.533) (503.484, 248.682) 6 (277.142, 5.15565) (387.425, 288.533) Delaunay Edges: 0 (282.004, 231.388) (487.891, 353.996) 1 (602.252, 288.418) (487.891, 353.996) 2 (426.484, 175.16) (487.891, 353.996) 3 (426.484, 175.16) (602.252, 288.418) 4 (50.8574, 5.02996) (282.004, 231.388) 5 (426.484, 175.16) (282.004, 231.388) 6 (50.8574, 5.02996) (426.484, 175.16) Vertices: 0 (277.142, 5.15565) 1 (503.484, 248.682) 2 (387.425, 288.533) 3 (0, 288.161) 4 (272.213, 482) 5 (637.275, 482) 6 (642, 33.7153) 7 (279.477, 0)

Bien que les données ci-dessus soient suffisantes si tout ce dont j'ai besoin, c'est de dessiner les diagrammes Voronoi et Delaunay, ce n'est pas assez d'informations pour le travail réel que j'essaie de faire avec ces diagrammes. Ce dont j'ai besoin est un dictionnaire de polygones formés par les sommets Voronoi, indexés par le point d'entrée que chaque polygone a été formé autour. de préférence, pour chaque polygone, ces points seraient triés dans le sens des aiguilles d'une montre.
Avec les informations ci-dessus, je pouvais affecter implicitement des données à chaque région, attribuer des données aux coins si nécessaire, indiquez quelles régions partagent les bords (à l'aide des bords Delaunayay) et effectuez des analyses en conséquence.
Donc en bref, Comment puis-je utiliser les données à votre disposition pour mettre en place un dictionnaire dans lequel la clé est l'un des points d'entrée et que les données indexées par cette clé sont une liste des sommets Voronoi qui forme le polygone environnant? ou alternativement, est cette information quelque part implicite dans les données que j'ai données?

La solution

L'algorithme de la fortune est O (n journal n) - mais votre code sera O (N ^ 2), si vous essayez de reconstruire les cellules de la mode brute de force comme proposé par Alink.

Le point de départ de ma réponse est que ce que vous utilisez pour générer les cellules n'est pas une bibliothèque, mais plutôt est juste Une classe écrite pour conclure parfaitement le code présenté à l'origine par Fortune lui-même , et non une bibliothèque mature. L'auteur n'a donc pas anticipé vos besoins et, bien que les informations que vous souhaitiez ont été calculées, il n'est pas accessible.

En interne, vos points d'entrée sont stockés comme des instances du "Site", et l'algorithme procède à créer demi-bords , chacun d'entre eux maintient une référence "sommet" qui est un pointeur sur le site qu'il entoure . Sortez le long des demi-arêtes que vous contournez naturellement le site fermé - exactement ce dont vous avez besoin.

Pour accéder à ces données, j'ai suggéré de modifier ou d'étendre la classe VoronoidiagraMenerator; Je le ferais en créant une table de hachage avec des pointeurs de site comme clé et un seul pointeur de demi-fruit comme valeur. Ensuite, modifiez la méthode GenerateVoroni, insérant votre nouveau code immédiatement après l'appel à Voronoi:

For each HalfEdge in ELHash
         Get table entry for current half edge's Site
         If site in table has null HalfEdge reference
            set current HalfEdge reference
         End If
End For each

... et il y a votre dictionnaire. Ce demi-bord unique vous permettra de "marcher" le périmètre du polygon enfermant le site associé, ce que je pense est ce que vous avez demandé. Votre prochain problème sera de découvrir efficacement quel Polygon entoure un nouveau point de données - mais c'est une autre question :-). J'espère que vous envisagerez de partager votre classe complétée - cela devrait être un niveau significativement plus utile que la classe de base.

EDIT: Voici une excellente présentation descibing tout ce qui précède en images: http://ima.udg. es / ~ sellares / comgeo / vor2d_1.ppt :

Définition du diagramme de Voronoy
Arbre de demi-bords (voir photos ci-dessous)
ALGORITHM FORTUNES EN PHOTO
Et voici une implémentation C # qui pourrait vous aider à récupérer le dictionnaire, tel que proposé ci-dessus: http://www.codeproject.com/articles/11275/fortune-s-voronoi-algorithm-implémented-C

Autres conseils

Votre liste d'arêtes est en quelque sorte incomplète, vous devez ajouter celles à la bordure du rectangle contenant fourni à l'appel de la bibliothèque (semble être 642 482 ici). Techniquement, une subdivision Voronoi doit utiliser des bords infinis, mais ceux-ci sont tous finis. Je suppose que vous voulez aussi que ces polygones "ouverts" près de cette frontière, car ils sont tous comme ça dans votre exemple.

Ajout de ces bords de la frontière semble pas difficile, juste fastidieux. Probablement quelque chose comme, pour chaque côté du rectangle principal, trouvez tous les sommets sur celui-ci (ignorant les coins), triez-les (par x pour l'horizontale, par Y pour la verticale) et divisez ce côté à l'aide de ces valeurs. Cela génère les bords manquants, mais ne les ajoutez pas directement à votre liste principale, car ils sont spéciaux car ils sont les seuls à ne pas séparer deux cellules.

Donc, pour la question elle-même, j'irais comme ça: Dans votre liste principale des bords (fournie par la bibliothèque), chaque EDGE sépare deux cellules et si nous trouvons ceux, alors nous pouvons simplement affecter ce bord à chacune de ces cellules. Étant donné qu'une cellule équivaut à un point d'entrée, nous aurons le dictionnaire voulu, sauf avec une liste d'arêtes au lieu de sommets, mais c'est facile à convertir.

maintenant pour obtenir ces 2 cellules: Calculez le point central du bord et de cela, trouvez les deux points d'entrée les plus proches en itérant simplement dans la liste tout en conservant les 2 dernières distances. Par les propriétés de la structure Voronoi, ces deux sont celles formant les deux cellules. Notez que ces deux distances doivent être égales, mais l'imprécision du flotteur introduira probablement une légère différence.

Pour finir, ajoutez les bords de la bordure que nous avons générés le long du rectangle principal, mais pour ceux-ci, utilisez simplement le premier point d'entrée le plus proche, car ils ne sont adjacents que d'une cellule.

Enfin, nous pouvons convertir chaque liste de bords en une liste de sommets (déchargez chaque extrémité des points dans un ensemble). Si vous souhaitez les trier dans le sens des aiguilles d'une montre, notez qu'il s'agit d'un polygone convexe avec un point d'entrée à l'intérieur. Ainsi, vous pouvez simplement générer le vecteur du point d'entrée à chaque sommet, calculer son angle d'un axe (utilisez STD :: ATAN2 (x, y)) et utilisez cet angle comme valeur comparateur pour les trier (voir std :: Trier).

J'ai utilisé le package triangulaire pour générer une triangulation Dalaunay: http://www.cs.cmu.edu/~quake/triangle.html

Ça fonctionne dans 2 modes A) comme un utilitaire triangulé.exe et b) en tant que bibliothèque C Pour la compiler comme utilitaire, il vous suffit de compiler triangle.c et de courir:

   triangulate -vZ input.poly 
   #v -voronoy, Z - starting from 0 index

Pour obtenir le diagramme de Voronoi (reportez-vous au manuel sur format .poly ) J'ai apporté une expérience avec vos données d'entrée dans un tel fichier .poly:

# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)> 
5 2 0 0
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker]
0 426.484 175.16
1 282.004 231.388
2 487.891 353.996
3 50.8574 5.02996
4 602.252 288.418
#One line: <# of segments> <# of boundary markers (0 or 1)>
5 0
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker]
0 0 1
1 1 2
2 2 3
3 3 4
4 4 0

mais cela rapporte simplement une erreur de données d'entrée.

Travailler avec ce paquet, je dirais que cela ne fonctionne souvent pas avec Ïnput signalant une erreur.Il n'accepte que des polygones d'entrée (pas des points aléatoires) et le problème ici est que vous disposez de polygone d'entrée auto-intersection.
Cela ne répond pas à votre question, signalant simplement des points, pas un dictionnaire

Vous pouvez simplement utiliser Triangle: http://www.cs.cmu.edu/ hillequke/triangle.html

http://svn.osgeo.Org / QGIS / Trunk / QGIS / Python / Plugins / FTOOLS / TOOLS / VORONOI.PY

Cette implémentation de Python par Carson Farmer vous donne des informations topologiques

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow