Recherche des triangles dans lesquels se trouvent les points

Supposons que j'ai un maillage 2D constitué de triangles non chevauchants , et un ensemble de points { p i } M i = 1 ⊂ ∪ N k = 1 T K . Quelle est la meilleure façon de déterminer dans quel triangle chacun des points se trouve?$\{T_k\}_{k=1}^N$$\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$

Par exemple, dans l'image suivante, nous avons , p 2 ∈ T 4 , p 3 ∈ T 2 , donc je voudrais une fonction f qui retourne la liste f ( p 1 , p 2 , p 3 ) = [ 2 , 4 , 2 ] .$p_1 \in T_2$$p_2 \in T_4$$p_3 \in T_2$$f$$f(p_1,p_2,p_3)=[2,4,2]$

Matlab a la fonction pointlocation qui fait ce que je veux pour les maillages Delaunay, mais elle échoue pour les maillages généraux.

Ma première pensée (stupide) est que, pour tous les nœuds , parcourez tous les triangles pour savoir dans quel triangle p i se trouve. Cependant, cela est extrêmement inefficace - vous pourriez avoir à parcourir chaque triangle pour chaque point, donc cela pourrait prendre du travail O ( N ⋅ M ) .$p_i$$p_i$$O(N \cdot M)$

Ma prochaine pensée est, pour tous les points , de trouver le nœud de maillage le plus proche via la recherche du plus proche voisin, puis de regarder à travers les triangles attachés au nœud le plus proche. Dans ce cas, le travail serait O ( a ⋅ M ⋅ l o g ( N ) ) , où a est le nombre maximal de triangles attachés à n'importe quel nœud du maillage. Il y a quelques problèmes résolubles mais ennuyeux avec cette approche,$p_i$$O(a\cdot M\cdot log(N))$$a$

• Cela nécessite la mise en œuvre d'une recherche efficace du plus proche voisin (ou la recherche d'une bibliothèque qui en dispose), ce qui pourrait être une tâche non triviale.
• Cela nécessite de stocker une liste des triangles attachés à chaque nœud, pour lequel mon code n'est actuellement pas configuré - pour le moment, il n'y a qu'une liste de coordonnées de nœud et une liste d'éléments.

Dans l'ensemble, cela semble inélégant, et je pense qu'il devrait y avoir une meilleure façon. Cela doit être un problème qui se pose souvent, donc je me demandais si quelqu'un pouvait recommander la meilleure façon d'aborder la recherche des triangles dans lesquels se trouvent les nœuds, théoriquement ou en termes de bibliothèques disponibles.

Merci!

La méthode habituelle de saut de bord aléatoire devrait fonctionner. Fondamentalement, commencez par n'importe quel triangle du maillage, puis déterminez de quels bords se situe le point cible du côté opposé. C'est-à-dire, déterminer lequel des bords, lorsqu'il s'étend sur une ligne, sépare le point de l'intérieur du triangle. Lorsqu'il y a deux possibilités, choisissez-en une au hasard, considérez le triangle adjacent à cette arête partagée et répétez. La randomisation devrait faire converger cette méthode avec la probabilité 1 pour les triangulations de Delaunay, et je ne vois pas de raison pour laquelle cela ne fonctionnerait pas pour les triangulations arbitraires.

Edit : je dois ajouter que le saut de bord doit être avec une constante raisonnable pour un seul point, donc ce serait O ( M log N ) pour M points. Cependant, si vous triez vos points par localité (comme en utilisant d'abord un ordre de courbe de Hilbert), vous pouvez initialiser chaque nouvelle requête avec le triangle de la requête précédente, pour réduire davantage le temps d'exécution (je ne suis pas un théoricien CS donc je peux '' t vous dire ce que le big-O serait là).$O(\log N)$$O(M \log N)$$M$

Edit2 : Trouvé ce PDF décrivant un tel schéma de "marche" qui est garanti de se terminer, et passe en revue les approches les plus naïves.

Une autre alternative à l'utilisation d'arbres quadratiques consiste à utiliser une hiérarchie de triangulation. Voir Olivier Devillers. Amélioration de la triangulation Delaunay randomisée incrémentielle. Dans Proc. 14th Annu. ACM Sympos. Comput. Geom., Pages 106-115, 1998. Il fonctionne mieux pour les triangulations de Delaunay, mais peut également fonctionner pour les non-Delaunay.

Fondamentalement, quoi que vous fassiez pour accélérer la localisation des points, il faudra construire une structure de données auxiliaire. Dans le cas de quadtrees ou d'une autre subdivision spatiale, vous devez créer l'arborescence de subdivision. Dans le cas du saut de bord, vous devez construire la structure topologique adjacente au triangle. La hiérarchie de triangulation nécessite également de construire un arbre de triangulations plus grossières.

Je ne suis pas convaincu que votre solution soit correcte. Considérez la situation où vous avez ces nœuds:

• R: (-3, 1)
• B: (0, 2)
• C: (3, 1)
• D: (0, -5)

Il existe des triangles ABC et ACD. Maintenant, B est le point le plus proche de l'origine, mais l'origine est dans le triangle ACD, qui ne contient pas B.

Pour le reste, cette réponse fournit une solution qui peut dans des cas dégénérés être aussi lente que $O(N \cdot M)$, mais sera généralement plus rapide - en particulier pour les triangulations de Delaunay et les triangulations proches de cela dans un certain sens.

J'envisagerais la possibilité de construire un quadtree contenant les triangles eux-mêmes. C'est-à-dire que vous avez un arbre quaternaire qui stocke dans chaque nœud (ce qui correspond à une boîte englobante):

• Les coordonnées auxquelles la boîte est divisée, ou bien les boîtes englobantes des quatre sous-arbres;
• Pointeurs vers les sous-arbres;
• L'ensemble des triangles qui tombent complètement dans la zone de délimitation de ce rectangle, mais pas complètement dans l'un des quatre sous-arbres. En d'autres termes, les triangles qui coupent l'un des deux segments de ligne de subdivision du quadtree.

Lorsqu'on lui donne un point P, parcourez tous les nœuds sur le chemin de la racine du quadtree à la plus petite boîte contenant P. Vous devrez examiner tous les triangles que vous rencontrez dans ces nœuds. Pour une triangulation «bien conduite», il ne devrait y avoir que quelque chose comme$\sqrt{n}$ triangles qui doivent être examinés au niveau d'un nœud qui contient $n$ triangles dans son sous-arbre, et la profondeur doit être limitée par $\log n$. Pour une triangulation «mal comportée», vous pouvez obtenir le$O(N\cdot M)$ travail.

CGAL gère les triangulations et l'emplacement des points (et bien plus encore). En particulier, le module de triangulation 2D peut faire ce que vous voulez.