Triangle de délimitation initiale infini dans les triangulateurs itératifs de Delaunay

Question

La plupart des algorithmes itératifs requièrent un triangle vide initial pour lancer la boule. Il semble qu'une astuce couramment utilisée consiste simplement à rendre le super triangle très grand par rapport à l'ensemble de points.

Mais selon « recettes numériques: l'art de l'informatique scientifique »:

» ... si la distance est simplement finie (aux points limites) la triangulation construit peut être pas tout à fait Delaunay Par exemple. sa limite extérieure pourrait, dans des cas inhabituels, être légèrement concave, avec de petits angles négatifs de l'ordre du diamètre de l'ensemble de points «réels» divisé par la distance aux points «frontières» fictifs

sont là pour augmenter les coordonnées cartésiennes avec des points à l'infini, sans avoir à convertir toute l'entrée à un système de coordonnées différentes telles que des coordonnées homogènes? avec les prédicats géométriques usuels CCW et Incircle?

Incirculation (a, b, c) Infini -> Faux. à condition que a, b, c soient finis. Mais qu'en est-il lorsque l'un des a, b, c est un point à l'infini? Est-ce que le cercle devient un demi-plan et le test devient alors un contrôle CCW? Que faire si 2 points ou plus sur le cercle sont infinies? le cercle se développe-t-il dans un plan complet, ce qui rend le test toujours vrai? Qu'en est-il de CCW? comment classer un point par rapport à une ligne qui a un ou plusieurs points à l'infini?

Answer 1

Je pense que vous vous rendez la vie difficile en essayant de définir les mathématiques complètes des géométries qui contiennent des points à une distance infinie. Ceci n'est pas nécessaire aux fins de votre problème original de calcul de la triangulation de Delaunay avec précision.

j'ai écrit un générateur Delaunay en Java il y a un certain temps et il est disponible ici: http://open.trickl.com/trickl-graph/index.html

Voir http://open.trickl.com/trickl-graph/apidocs/index.html et en particulier:

// Check if fourth point is within the circumcircle defined by the first three 
    private boolean isWithinCircumcircle(PlanarGraph<V, E> graph, V first, 
      V second, 
      V third, 
      V fourth) { 
     // Treat the boundary as if infinitely far away 
     Coordinate p = vertexToCoordinate.get(fourth); 
     if (PlanarGraphs.isVertexBoundary(graph, first)) { 
     return isLeftOf(third, second, p); 
     } else if (PlanarGraphs.isVertexBoundary(graph, second)) { 
     return isLeftOf(first, third, p); 
     } else if (PlanarGraphs.isVertexBoundary(graph, third)) { 
     return isLeftOf(second, first, p); 
     } else if (PlanarGraphs.isVertexBoundary(graph, fourth)) { 
     return false; 
     } 

     Coordinate a = vertexToCoordinate.get(first); 
     Coordinate b = vertexToCoordinate.get(second); 
     Coordinate c = vertexToCoordinate.get(third); 

     boolean within = (a.x * a.x + a.y * a.y) * getDblOrientedTriangleArea(b, c, p) 
       - (b.x * b.x + b.y * b.y) * getDblOrientedTriangleArea(a, c, p) 
       + (c.x * c.x + c.y * c.y) * getDblOrientedTriangleArea(a, b, p) 
       - (p.x * p.x + p.y * p.y) * getDblOrientedTriangleArea(a, b, c) > 0; 

     return within; 
    } 

Ici, les points limites sont explicitement vérifiées lors de cette vérification l'état de circoncision, de sorte qu'ils peuvent effectivement être traités comme "infiniment". C'est beaucoup plus facile que de comprendre toutes les implications géométriques que vous décrivez.

Answer 2

Il est assez facile d'implémenter une triangulation de Delaunay en ajoutant un point à l'infini. Choisissez une convention pour le sommet infini (par exemple, l'index de vertex -1).

Au début, on crée un premier fini tétraèdre T0 entre 4 périodes de non-coplanaires prélevés par le PointSet d'entrée, et ensuite créer quatre tétraèdres infini qui relient chaque face de T0 au sommet infini 0 (et ne n'oubliez pas de les interconnecter correctement le long de leurs faces communes infinies).

Ensuite, vous insérez chaque point p, un par un, comme d'habitude (Boyer-Watson algo), en (1) calculant le tétraèdre T qui contient le point p (localiser) et (2) trouver la zone de conflit, suit:

(1) localiser est non modifié: vous marchez vers p à partir d'un aléatoire tétraèdre.Pendant la marche, si vous arrivez dans un tétraèdre infini, alors vous arrêtez là (cela signifie que le point est en dehors de la coque convexe des points insérés précédemment)

(2) La détermination de la zone de conflit a besoin d'une petite modification:

• un point p est en conflit avec un fini tétraèdre T si son dans sa sphère circonscrite (comme d'habitude)

• Pour un infini tétraèdre T = (p1, p2, p3, p4), un de p1, p2, p3, p4 est l'infini ite vertex (par exemple p2, alors T = (p1, infini, p3, p4)). Pour vérifier si p est en conflit avec T, remplacer le sommet infini par p, et calculer le volume signé du tétraèdre: signed_volume (p1, p, p3, p4) dans notre exemple, s'il est positif, alors T est en conflit avec p. Si elle est négative alors T n'est pas en conflit avec p. Si p est exactement sur le plan de support des trois sommets finis de T, alors T est en conflit avec p si T 'est en conflit avec p, où T' est le tétraèdre adjacent à T le long de la face finie de T (de manière équivalente, au lieu de trancher T ', on peut vérifier si p est dans le cercle circonscrit de la facette finie de T).

Voir les implémentations dans:

• geogram: http://alice.loria.fr/software/geogram/doc/html/classGEO_1_1Delaunay3d.html
• CGAL: http://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay