Over the past couple of days I have been trying to understand how Alpha Shapes work over point sets but I have been unable to understand the Delaunley Triangulation theory.

As a result I have set off on my own root implementing it using the Half Edge Mesh structure as a corner stone. Its not currently working due to a bug breaking down the data structure validity however I am confident that with that fixed the method I have devised should be as good as any other method for creating the alpha shape of an object. My theory goes along the lines of

for every vertex
for every other vertex
if in range and not directly connected
Add Edge


however simply adding an edge would break the half edge data structure so when adding an edge it first determines which pair of edges it should join between for each vertex and then proceeds to fold down the triangle bounded by them on each vertex.

these triangles are then joined together to form a base of a prism that is then constructed by adding the edge joining the 2 vertices's and another to edges to triangulate the sides of the prism.

now the mesh is valid again and the algorithm can move on to the next pair.

there is a special case when the vertices's at the bottom of the fold are shared between the vertices's which we wish to join. In that case either the collapse could be ignored, leaving any further passes to deal with it or the shared edge can be moved up to the two vertices's which we want to join, effectively rotating the trough. Processing it may be undesirable if no further passes are going to be run as it may change the silhouette in an undesirable manner.

While I'm not currently handling the special case, I hope to have the validation bug fixed tonight so it can be seen in action and a decision on what to do next can be made tomorrow.