In place sorting of a half edge DS?

Question

Cross posting from SO because I didn;t know where to put this question.

I have an implementation of the half edge and I am trying to sort the edges such that edge n+1 is the pair of edge n.

Setup

I want to do this in place to save memory and I discovered a theoretical wall I am not sure how to solve.

Let's assume the HE are stored in a list and that you can access their members through self defining getters like .Pair() or .Next().

The idea of the algorithm is very simple.

for(uint i=0; i<half_edges.size(); i+=2)
{
   swap(half_edges[i+1], half_edges[i].Pair()); // This is pseudo code, assume this works
}

That's the gist of the idea, merely swap the he right next to you with wherever your pair is.

Now of course, you need to update your pointers, so for both the pair and the HE originally at $i + 1$ you have to go through this tedious process:

    faces[old_pair_face].edge = i + 1;
    verts[old_pair_vert].edge = i + 1;
    edges[old_pair_prev].next = i + 1;
    edges[old_pair_next].prev = i + 1;
    edges[i].pair = i + 1;

    faces[old_other_face].edge = old_pair_index;
    verts[old_other_vert].edge = old_pair_index;
    edges[old_other_prev].next = old_pair_index;
    edges[old_other_next].prev = old_pair_index;
    edges[old_other_pair].pair = old_pair_index;

Essentially just update all the pointers that pointed to the original 2 elements.

BUG

The above ALMOST works. However consider the following case. Assume we are at edge i. The pair of i is j, the next of j is i+1.

So i + 1 and j swap, so the pair of i is now at i + 1. You then want to update next, which points to i + 1, so inadvertently in this specific case, swap will accidentally make next point to yourself. Which is invalid as the Half edge does not allow an edge to point to itself.

This is pretty rare so it took me a while to find, but it's clearly an error in my logic.

The question is, given an already implemented half edge, how can you sort its edges such that the n and n+1 are pairs, while avoiding the pitfalll described above, in O(1) memory?

Answer 1

My solution to this ended up being not sorting at all. Manipualting an already initialized HE is a nightmare, so instead I built the HE with this property from the get go.

The initialization algorithm is pretty much:

• Create a new half edge.
• Check if the pair of the half edge exists.
• If it exists, you are allocated at index of pair + 1
• If it does not exist, increment an offset by 2 and store yourself at offset - 2 (i.e. allocate 2 slots in the edge array and store yourself in the even slot).

Doing it this way before setting next and prev and company guarantees that at any one time the HE is properly initialized.