half-edge data structure delaunay triangulation

Question

I am writting Python delaunay triangulation with half edge data structure.

Also, in triangulation algorithm, I try to store only half-edges. I retrieve triangles from the list of edges.

However, this is pretty redundant, right? I have much more edges than needed to describe triangles, since one triangle is defined by one edge and can be walked through easily since each edge has got a pointer to the next.

1/ is that OK to implement Watson algo for delaunay storing only a list of half-edges? Will it be difficult then to walk through?

In Watson's algorithm step to determine the edges inside the cavity, I would like to walk on edges and find those edges vertices that are at the end of more than three distinct half-edges.

2/ Is this property 'more than two edges end at this vertex' a correct an appropriate criterion to discard edges in Bowyer Watson algo?

For walking through the mesh, I would iterate on each half-edge. So, I am working edge by edge, not triangle by triangle. I am walking through the mesh without using the 'next' property, which sounds not good.

3/ What is the way to walk through the triangles in the mesh, stored as a list of edges? Or how to better store the mesh so as to make the walk through it easier?

Thanks!

Answer 1

Half-edge data structure is fine! Use a list of faces and a list of edges, this may be sufficient.