Trouve efficacement le polygone dans un diagramme de Voronoi contenant un point

Question

Je projette des images sur un Voronoi diagram. Pour chaque pixel non noir de l'image, je trouve le polygone correspondant dans le diagramme et le colorie. (The site, to get an idea what I mean.) Avec quelques centaines de polygones, une approche par force brute est réalisable. Avec quelques milliers, ce n'est pas le cas.

Ma question: Comment puis-je rechercher efficacement un nombre de polygones pour ceux contenant un point? Je m'intéresse au cas général, sans faire d'hypothèses sur la distribution ou la taille des polygones.

Deux réponses existantes (que je trouve) concernent:

Finding out if a point is inside a voronoi cell Il tire parti de manière élégante le fait que les polygones Voronoi sont convexes. Par conséquent, le polygone, dont le centre est le plus proche, doit également être le polygone contenant. Malheureusement, pour déterminer le minimum, tous les polygones sont toujours recherchés. C'est ce qui ne change pas.

Finding the polygon in a 2D mesh which contains a point Il mentionne un arbre d'intervalle 2d. (Selon ces slides on the topic il devrait s'agir d'un arbre de segment.) Une propriété des diagrammes de Voronoi, cependant, est que les polygones ne se chevauchent pas, alors que les arbres de segment ne font pas cette supposition. Ainsi, si ces arbres sont effectivement la meilleure option (?), Existe-t-il une approche qui inclut cette hypothèse, lui permettant d'être plus efficace?

Je construis cela en JavaScript purement côté client, en utilisant D3, donc je suis intéressé par un algorithme, une bibliothèque ou un changement de modélisation. Une base de données spatiale telle que MySQL ou MongoDB, par exemple, ne m'aide pas.

---

Ce que j'ai essayé jusqu'à présent: je construit un indice suffisamment efficace pour le cas exactement mon utilisation qui repose sur des hypothèses que je peux faire, voir ci-dessous.

La solution pour mon cas spécifique est fondamentalement un hachage du point central des polygones.

Construire l'index:

1. Le diagramme est divisé en une grille de taille uniforme.
2. Chaque polygone est affecté à une cellule par son point central.

Lors de la recherche pour le polygone qui contient un point donné:

1. La cellule pour le point est déterminé.
2. Tous les polygones de cette cellule sont testés.
3. Si aucun ne correspond, les cellules environnantes sont recherchées, en largeur d'abord, jusqu'à ce que le polygone soit trouvé.

Cela fonctionne, parce que je fais quelques hypothèses:

1. Les polygones sont uniformément répartis. Cela signifie qu'une grille uniforme est correcte. Une grille uniforme permet de déterminer la cellule d'un point en traduisant les coordonnées.
2. Les polygones sont convexes. Cela signifie que le point central est réellement proche de la majeure partie de sa surface.
3. Les polygones ont largement la même taille. En choisissant une taille de cellule proche de la taille moyenne d'un polygone, il est très probable que la cellule directe ou l'une des cellules voisines soit associée au polygone voulu.
4. Fondamentalement toujours, il y a un polygone qui contient le point. (C'est-à-dire que peu de temps est gaspillé à chercher toutes les cellules.)

Donc, bien que cela fonctionne exactement pour mon cas d'utilisation, je voudrais desserrer certaines restrictions. Cette question concerne le rejet des hypothèses 1 et 3, si possible. (2 et 4 sont donnés pour un diagramme de Voronoi, si je comprends bien.)

Answer 1

Si ce n'est pas un problème purement géométrique alors je voudrais aller à l'image bitmap de recherche. Peignez simplement tous les polygones dans un bitmap secondaire (canevas) en utilisant des identifiants entiers pour la couleur. Pour trouver l'identifiant de poly, il suffit de vérifier la couleur des pixels sur la position correspondante. Une position - un aller chercher. Il devrait être ultra rapide mais pas géométriquement parfait. Notez que vous pouvez mettre à l'échelle le bitmap de recherche pour augmenter la précision.