1
$\begingroup$

I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices. The issue I have is that the structure is evolving during the algorithm and there are frequent creation/removal of faces, which affect the indexing of faces. So far I have overcome this issue, avoiding removing faces: updating one and adding 2 when inserting a vertex in a triangle for example. Now I am facing the same issue when removing the faces containing the 3 i(big triangle) initialization points. It seems that I am missing an important point here, should I use a dummy face list that I would also parse when inserting and update every time a face containing an initialization point has bee modified? Or is there a more elegant way to solve that issue?

$\endgroup$
  • $\begingroup$ paulbourke.net/papers/triangulate $\endgroup$ – lemon Jul 11 '14 at 10:03
  • $\begingroup$ Thank you for the link, great implementation. I am working on a library that is triangle(index)based, and not edge based. So it does not actually solve my problem. $\endgroup$ – Leo Jul 11 '14 at 11:43
  • $\begingroup$ It would be best to use a list of faces, rather than index into an array. My code here: Computational Geometry in C is based on triangles stored in a list, and might help. $\endgroup$ – Joseph O'Rourke Jul 11 '14 at 12:18
  • $\begingroup$ Thank you for your answer, and link. Very useful algorithms. Actually I use a list of faces, each face having as member an array of its neighbors, similar as the CGAL representation. I guess the best way to do is to try avoid deleting faces during insertion phases and renumber the neighbors faces so they have the correct indexes. Not very elegant but this should work. $\endgroup$ – Leo Jul 11 '14 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.