<p>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.</p>
<p>The initialization algorithm is pretty much:</p>
<ul>
<li>Create a new half edge.</li>
<li>Check if the pair of the half edge exists.</li>
<li>If it exists, you are allocated at <code>index of pair + 1</code></li>
<li>If it does not exist, increment an <code>offset</code> by 2 and store yourself at <code>offset - 2</code> (i.e. allocate 2 slots in the edge array and store yourself in the even slot).</li>
</ul>
<p>Doing it this way before setting <code>next</code> and <code>prev</code> and company guarantees that at any one time the HE is properly initialized.</p>

CC BY-SA 4.0
2020-09-27T20:18:00.013Z
2020-09-27T20:18:00.013Z
Makogan
<p><a href="https://stackoverflow.com/questions/64084221/in-place-sorting-of-a-half-edge-data-structure">Cross posting</a> from SO because I didn;t know where to put this question.</p>
<p>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.</p>
<h1>Setup</h1>
<p>I want to do this in place to save memory and I discovered a theoretical wall I am not sure how to solve.</p>
<p>Let's assume the HE are stored in a list and that you can access their members through self defining getters like <code>.Pair()</code> or <code>.Next()</code>.</p>
<p>The idea of the algorithm is very simple.</p>
<pre><code>for(uint i=0; i&lt;half_edges.size(); i+=2)
{
   swap(half_edges[i+1], half_edges[i].Pair()); // This is pseudo code, assume this works
}
</code></pre>
<p>That's the gist of the idea, merely swap the he right next to you with wherever your pair is.</p>
<p>Now of course, you need to update your pointers, so for both the pair and the HE originally at <span class="math-container">$i + 1$</span> you have to go through this tedious process:</p>
<pre><code>    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;
</code></pre>
<p>Essentially just update all the pointers that pointed to the original 2 elements.</p>
<h1>BUG</h1>
<p>The above ALMOST works. However consider the following case. Assume we are at edge <code>i</code>. The pair of <code>i</code> is <code>j</code>, the <code>next</code> of <code>j</code> is <code>i+1</code>.</p>
<p>So <code>i + 1</code> and <code>j</code> swap, so the pair of <code>i</code> is now at <code>i + 1</code>. You then want to update <code>next</code>, which points to <code>i + 1</code>, so inadvertently in this specific case, swap will accidentally make <code>next</code> point to yourself. Which is invalid as the Half edge does not allow an edge to point to itself.</p>
<p>This is pretty rare so it took me a while to find, but it's clearly an error in my logic.</p>
<p>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?</p>

<c++><mathematics><computational-geometry><geometry>
In place sorting of a half edge DS?
Makogan
# In place sorting of a half edge DS?

(Asked by: username_0 on 2020-09-27)

[Cross posting](https://stackoverflow.com/questions/64084221/in-place-sorting-of-a-half-edge-data-structure) 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?

**Tags:** c++, mathematics, computational-geometry, geometry


---

## 1 answers

### Answer by username_0 on 2020-09-27. Score: 0 | Accepted answer

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.


---

