Diagrames de Voronoi, Triangulacions de Delaunay i Triangulacions
Restringides
Donat un conjunt de punts en un pla (que poden ser els vèrtexs
d'un poligon que volem triangularitzar), el diagrama de Voronoi es un
conjunt de regions R1 ... Rn on cada regió correspon a un dels
punts inicials V1 ... Vn , tals que la regió Rk conté el
conjunt de punts del pla que estan més a prop de Vk que de
qualsevol altre dels punts incials donats.
Un cop construit el diagrama de Voronoi, la seva dual és la
triangulació de Delaunay del conjunt de punts donats. Aquesta
dualitat s'ha d'entendre com que dos punts Vi i Vj estan conectats per
una aresta de la triangulació de Delaunay si i solament si les
dues regions corresponents Ri, Rj són contigües i
comparteixen una aresta del diagrama de Voronoi.
Els diagrames de Voronoi es poden calcular amb algorismes de "divide and
conquer" o be amb l'algorisme d'en Steven Fortune, que el calcula de
forma incremental a base d'una recta vertical que escombra el model
d'esquerra a dreta; el diagrama de Voronoi es va construint a la part
ja escombrada per la recta. Podeu trobar mes detalls i un applet
interactiu en aquesta pagina de la
implementacio visual de l'algorisme de Fortune
Podeu trobar mes informació sobre Diagrames de Voronoi i
Triangulacions de Delaunay als apunts de l'Assignatura
de Geometria Discreta i Computacional (Ferran Hurtado i altres). En
especial us recomanem els temes seguents:
Lliçó 9. Triangulació de polígons:
algorismes. Apunts fets per Marcel
Guàrdia.
Lliçó 10. Triangulació de polígons: algorismes. Apunts
fets per Alberto
Rodríguez.
Lliçó 12. Diagrama de Voronoi, triangulació de
Delaunay. Apunts
fets per Elena
Manresa.
Lliçó 13. Diagrama de Voronoi, triangulació de
Delaunay. Apunts
fets per Pau
Rue.
Lliçó 14. Cálcul del diagrama de Voronoi.
Apunts fets per Patricia
Colera.
Una triangulació restringida de Dealunay és una
triangulació tal que manté algunes arestes que s'han
especificat inicialment. En el cas de la triangulació de
polígons nosaltres voldrem triangular el conjunt de
vèrtexs d'un polígon tot mantenint les arestes inicials
del polígon.
Podeu trobar alguns algorismes de construcció de triangulacions
restringides de Delaunay a les següents url's:
Algorismes
de Samuel Peterson
Llibrería de David
Kornmann
Algorisme de
Zhihua Wang