-
afazio
| .
|
|
|
|
CITAZIONE (reversi @ 22/1/2015, 16:15) nei documenti che ho linkato nell'altro topic sono esposti vari algoritmi per ottenere una triangolazione di delaunay (che in generale è molteplice, come dimostra l'esempio del quadrato o rettangolo che dir si voglia).
quello sopra proposto è detto "incrementale" (pare che sia uno dei più lenti a produrre la soluzione). un altro che ricordo di aver letto, più veloce del precedente, è detto "divide et impera".
Prima di passare alle diverse strategie da adottare per diminuire la complessità computazionale del processo direi di capire la logica che porta da una triangolazione alla successiva.
La strategia denominata "divide et impera" non fa altro che dividere l'insieme dei punti di partenza in due sotto-insiemi aventi una ben determinata logica di divisione (per esempio tutti i punti aventi x>=xo e quelli aventi x<xo) e quindi applicare l'algoritmo su ciascuno dei due sotto-insiemi che essendo costituiti da un numero di punti pari a circa la meta ha una complessità computazionale molto inferiore. Alla fine del processo si metteno insieme le due triangolazioni trovate. Questa strategia fa però uso del diagramma duale alla triangolazione di Delaunay denominato "tessellazione di Voronoi".
|
|
|
| .
|
26 replies since 21/1/2015, 15:43 1857 views
.
.nei documenti che ho linkato nell'altro topic sono esposti vari algoritmi per ottenere una triangolazione di delaunay (che in generale è molteplice, come dimostra l'esempio del quadrato o rettangolo che dir si voglia).
.
