Algoritmo per il completamento di una triangolazione parziale (Triangolazione vincolata)

Question

Dato un insieme di punti in un piano e uno triangulation of the convex hull of the points incompleto (sono forniti solo alcuni bordi), sto cercando un algoritmo per completare la triangolazione (i bordi dati iniziali dovrebbero rimanere fisso). Puoi supporre che sia possibile completare la triangolazione parziale, ma sarebbe bello se potessi anche suggerire un algoritmo per controllarlo anche tu.

AGGIORNAMENTO "Ti viene dato uno scafo convesso di un insieme di punti R^2, che è fondamentalmente un poligono con alcuni punti al suo interno. Vogliamo triangolare l'insieme di punti che è una materia diretta su se stesso, ma ti sono anche dati alcuni bordi che qualsiasi triangolazione che ti viene in mente dovrebbe usare quei bordi. "

Answer 1

Forse questa è una risposta ingenua, ma non puoi semplicemente usare una triangolazione delaunay vincolata? Aggiungi i bordi conosciuti come vincoli.

CGAL ha un nice implementation. Lo strumento triangle ha caratteristiche simili ed è più facile da iniziare, ma ha (forse) un po 'meno flessibilità.

Answer 2

Ho scoperto che il libro "Geometria computazionale: un'introduzione" ha un trattamento dettagliato del soggetto sebbene non dia uno pseudo-codice pronto per l'implementazione.

L'algoritmo più semplice è quello avido che enumera tutti i possibili bordi e quindi li aggiunge uno per uno evitando l'intersezione con le età aggiunte in precedenza. C'è una lunga discussione nel libro su come ridurre il tempo di esecuzione a O (n^2 log n).

Quindi esiste un algoritmo O (n log n) che dapprima regolarizza lo scafo convesso con i bordi dati e quindi individua ogni triangolo di poligoni monotoni.