Come determinare se un triangolo Delaunay è interno o esterno?

Question

Sto scrivendo un programma che richiede l'implementazione dell'estrazione dell'Asse mediale, di cui la triangolazione di Delaunay è un passo. L'asse mediale esterno è indesiderato, quindi i corrispondenti triangoli esterni devono essere rimossi. Fortunatamente mi sono imbattuto nello a page con molti diagrammi, anche un accenno a un metodo per determinare i triangoli di Delaunay interni ed esterni ("basato sul perimetro della linea spezzata"), ma è solo un suggerimento, senza una spiegazione dettagliata. Qualcuno conosce l'algoritmo?

EDIT: Ho dimenticato di menzionare i punti iniziali sono campionati dal confine di un poligono chiuso, la mia intenzione è di determinare se ogni triangolo Delaunay è all'interno del poligono.

Answer 1

Questa soluzione presuppone che è una struttura di dati che rappresenta la triangolazione Delaunay utilizzando un "infinito vertice Delaunay virtuale" il modo CGAL lo fa (see details here).

L'idea è di trovare i bordi del bordo di Delaunay: i bordi che collegano due punti di campionamento consecutivi; e poi "alluvione" attraverso la triangolazione di Delaunay per classificare le facce di Delaunay. Si sa che il vertice infinito è esterno in modo da poter classificare i suoi vicini (e vicini di casa, ecc.) Come esterni purché non si oltrepassino i confini. Se si raggiunge un confine, si può semplicemente contrassegnare il triangolo vicino come interno e continuare allo stesso modo.

ingresso: set di punti di campionamento densamente del contorno di una forma chiusa, che può anche contenere fori
uscita: diagramma di Voronoi nell'interno della forma (approssimazione dell'asse mediano della forma)

1. Calcola la triangolazione Delaunay dei tuoi punti
2. Mark i bordi Delaunay che collegano due punti di campionamento consecutivi. (Vedere page 4-5 of this paper come farlo con un test locale su ogni spigolo di Delaunay)
3. Classificare tutte le facce Delaunay infinite come ESTERNO e inviarle a una coda Q.
4. Mentre Q non è vuoto
   1. Delaunay faccia f = Pop da Q
   2. Per ogni triangolo prossimo classificati t di f
      • se la Delaunay bordo condiviso da t e f è contrassegnato, classificare t come l'opposto di f
      • altro classificare t stesso come f
      • spinta t a Q
5. Per ogni bordo Delaunay e
   • se i due vicini Delaunay triangoli d1, d2 sono entrambi classificati come INTERNA, uscita il segmento che collega la circumcenter di d1 e d2.

Per un ingresso simili

seguente asse ravvicinamento mediale può calcolare:

È possibile verificare come questo asse approssimazione mediale comporta in pratica utilizzando finestre libera binario di Mesecina. Codice sorgente here.

Answer 2

Forse sto facendo troppe ipotesi qui, ma sembra che tu abbia un poligono che consiste in un mucchio di punti e che stai triangolando quei punti. Quindi vuoi scartare tutti i triangoli che cadono fuori dal poligono, giusto?

Perché non basta triangolare il poligono (usando la decomposizione monotona o qualcosa di simile) in modo da non creare mai triangoli esterni? Suppongo che questo potrebbe aumentare il tempo di esecuzione (triangolare prima nel tempo O (nlogn) e quindi creare una triangolazione delaunay in O (n^2)) ma potrebbe esserci un modo più veloce di farlo.

Answer 3

Hai mai considerato di utilizzare una diversa forma di triangolazione che non crea triangoli esterni? Una volta ho seguito un corso che ha dedicato molto tempo a discutere gli aspetti teorici della triangolazione del poligono. Forse sfogliare il sito del corso ti darà qualche informazione? http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

Modifica: In realtà, ho appena pensato a qualcos'altro. Se hai già il poligono che stai cercando di triangolare, potresti usare il teorema di Green. Il teorema di Green usa il perimetro di un poligono per calcolare la sua area! Ancora più importante, in questo caso, è possibile determinare se un punto si trova su un lato di una linea o su un altro, guardando il segno dell'area. Sui poligoni, il teorema di Green risolve un semplice problema di sottrazione. Quindi prendi qualsiasi punto che tu sappia sia all'interno del poligono e calcoli l'area contro ogni bordo del poligono. Questo ti dice su quale lato di ogni linea deve essere il tuo punto. Ora basta prendere un punto all'interno di ogni triangolo e fare la stessa cosa. Se uno qualsiasi dei segni è sbagliato, allora hai un triangolo esterno. (Nota: a seconda della forma del poligono questo potrebbe non funzionare. Dovrebbe funzionare bene per i poligoni convessi, ma le concavità potrebbero introdurre ulteriori complicazioni.)

Answer 4

L'algoritmo che presentano sembra un po 'rotto, come mostrano in una delle loro figure e questo potrebbe essere il motivo per cui non sembrano esserci citazioni utili in Google Scholar.

Using their proposed algorithm on a non-convex polygon shows that it does not always recover an actual triangulation. http://www.cc.kyoto-su.ac.jp/~atsushi/Jun/Topics/Teddy/images/example2_2.jpg