How to remove an edge from a half edge structure?

Question

I am trying to implement an algorithm to remove an edge and a vertex from a half edge structure. See the attached image for an illustration:

I know there's libraries like Openmesh and CGAL etc that can help me achieve this but I plan to implement it myself.

My original idea is as follows:

1. Find out the half edges associated with that edge
2. Find out all the faces associated with each half edge
3. Find out all the edges and vertices corresponds to each face
4. Not sure how to merge them together ie how to merge edge 1 edge 2, vertex 4 and 2 and edge 5 and 4 in the attached graph.
5. Delete all the faces.
6. Delete all the half edges

Can someone please give some suggestion if I am on the right track?

I also did some research online and found an article online that seems to be helpful.

Here's the link: http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm

Under the Removing an edge section it lists the following steps:

1.Remove all of the polygons connected to the edge.
2.Link the half-edges of the edge off from the mesh.
3.Deallocate the edge and its half-edges.

The first and last ones make sense to me. However, I am not sure what the author mean by link the half-edges of the edge off from the mesh? Can someone please explain this to me? Thanks!

Answer 1

I will take this question to mean "How to implement edge collapse".

The algorithm itself is not that complicated once you have a working half edge DS.

• Grab the 2 vertices connected by the edge
• Set their out half edge pointers to be the next of the selected half edge and the pair (to avoid creating invalid pointers)
• Obtain the next of the half edge and the prev set them as a new half edge pair.
• Do the same for the pair of the selected half edge
• Select either of the vertices opposite to the the half edge. Set it to be the connecting vertex between the 2 newly generated half edges.
• Delete both faces, the unused vertex and the selected half edges.