Costruire il contorno di un poligono (in particolare una triangolazione)

Question

Come potrei fare per costruire il contorno del poligono 2d che è formato da soli triangoli e può avere buchi e il contorno esterno può essere concavo / convesso e i fori possono anche essere concavi / convessi.

Da ciò che Sto leggendo qui sembra che sia esattamente l'inverso del problema di triangolazione. Conosci qualche articolo che tratta questo tipo di problema?

Gli octrees / quadtrees sono rilevanti per questo?

Answer 1

Suppongo che tu abbia dati sotto forma di insiemi di tre punti, che costituiscono un " riempito " triangolo, che questi triangoli sono adiacenti lungo i bordi e che tutti i vertici che saranno angoli della forma completa sono anche vertici di tutti i triangoli che toccano questo punto. Dovresti quindi trovare tutti i bordi che non sono raddoppiati, cioè non appartengono a due triangoli adiacenti.

Answer 2

Penso che tu possa risolvere il tuo problema creando una struttura di dati topologici per rappresentare il tuo set di triangoli, e quindi usando quella struttura per iterare in ordine sopra i bordi del triangolo che giacciono sul confine.

Ad esempio: è possibile creare una struttura di dati halfedge. Supponendo di inserire dei semi-bordi anche sul bordo (correttamente), iterare sul contorno del contorno è semplice come individuare un bordo intermedio sul bordo e quindi iterare sul suo & Quot; next & Quot; puntatore fino a quando non si torna al halfedge da cui si è partiti.

Analogamente alle mezze punte, puoi usare altre strutture topologiche come il bordo alato, ecc., ma il concetto è lo stesso.