<p>It depends a little on your actual data structure and how it even encodes boundary edges. What I find more useful than representing the boundary with a null half edge pointer, and thus having this situation of a half edge without an opposite and thus a hard stop for any such iteration, is instead <strong>encoding the boundary with a full half edge pair too, but with one of the half edges having a null <em>face</em> pointer</strong>.</p>

<p>So the boundary edge actually does have an opposite (or <code>pair</code> pointer) and that opposite is fully integrated into the pointer structure, complete with <code>next</code> pointer and everything. Just that its face pointer in null, thus denoting an empty face or hole. So basically <strong>every hole is represented by a null face with half edges going around it</strong>.</p>

<p>In addition to being able to iterate around vertices regardless of the starting point, this also has the advantage that you can easily iterate around boundary curves. And you can even have more than one hole at a vertex (although, that can still be problematic in other situations). Of course you might still have to handle the boundary half edges specially in some situations, especially when you're using the face pointers, but you won't get around that anyway if your mesh can have holes.</p>

<hr>

<p>If that is too much of a hassle to restructure your data and algorithms this way, though, maybe you can instead adjust your <strong>vertex starting edge pointers to always point to the boundary edge</strong> if there is one. You'd of course have to make sure that stays consistent, but if you can assume that as a precondition, you can just start iterating from there. And you can also check immediately if the vertex is at a boundary without having to iterate.</p>

CC BY-SA 4.0
2020-02-13T13:03:19.510Z
2020-02-13T13:03:19.510Z
Christian Rau
<p>Ok so let's say we have a portion of a mesh that looks somewhat like this:</p>

<p><a href="https://i.sstatic.net/Tk5F4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Tk5F4.png" alt="enter image description here"></a></p>

<p>A triangle fan with one of the triangles removed. If that triangles was not removed, we could get all the edges adjacent to that vertex this way:</p>

<pre><code>std::vector&lt;GraphEdgePtr&gt; GraphVertex::GetVertexEdges()
{
    std::vector&lt;GraphEdgePtr&gt; edges;
    auto current_edge = edge;
    do
    {
        edges.push_back(current_edge);
        current_edge = current_edge-&gt;pair-&gt;next;
    } while(current_edge != edges[0]);

    return edges;
}
</code></pre>

<p>However, if the triangle is removed, the above will segfault. One could create an additional loop that iterates backwards from the starting edge in the case the first loop finds a null pointer.</p>

<p>However that is a bit inelegant in my opinion. Is there a way to do it in a single loop? Using a stack or a queue or some sort for example?</p>

CC BY-SA 4.0
2020-02-13T04:58:12.477Z
Iterate in both directions - from the current clockwide, and anti-clockwise.
lightxbulb
CC BY-SA 4.0
2020-02-13T05:01:40.743Z
Right, but that's essentially the second loop I mentioned. Which I am hoping to avoid if can be
Makogan
CC BY-SA 4.0
2020-02-13T06:34:18.343Z
You visit all elements exactly once - what is the issue? Otherwise you would have to assign to your vertices, the leftmost/rightmost edges - then you would start at one end and finish at the other.
lightxbulb
<algorithm><c++><mathematics><computational-geometry><geometry>
How to handle Half edge boundary edge iteration from vertex?
Makogan
# How to handle Half edge boundary edge iteration from vertex?

(Asked by: username_0 on 2020-02-13)

Ok so let's say we have a portion of a mesh that looks somewhat like this:

[![enter image description here](https://i.sstatic.net/Tk5F4.png)](https://i.sstatic.net/Tk5F4.png)

A triangle fan with one of the triangles removed. If that triangles was not removed, we could get all the edges adjacent to that vertex this way:

```
std::vector<GraphEdgePtr> GraphVertex::GetVertexEdges()
{
    std::vector<GraphEdgePtr> edges;
    auto current_edge = edge;
    do
    {
        edges.push_back(current_edge);
        current_edge = current_edge->pair->next;
    } while(current_edge != edges[0]);

    return edges;
}

```

However, if the triangle is removed, the above will segfault. One could create an additional loop that iterates backwards from the starting edge in the case the first loop finds a null pointer.

However that is a bit inelegant in my opinion. Is there a way to do it in a single loop? Using a stack or a queue or some sort for example?

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

> **Comments:**
> **username_1**: Iterate in both directions - from the current clockwide, and anti-clockwise.  
> **username_0**: Right, but that's essentially the second loop I mentioned. Which I am hoping to avoid if can be  
> **username_1**: You visit all elements exactly once - what is the issue? Otherwise you would have to assign to your vertices, the leftmost/rightmost edges - then you would start at one end and finish at the other.  

---

## 1 answers

### Answer by username_2 on 2020-02-13. Score: 1 | Accepted answer

It depends a little on your actual data structure and how it even encodes boundary edges. What I find more useful than representing the boundary with a null half edge pointer, and thus having this situation of a half edge without an opposite and thus a hard stop for any such iteration, is instead **encoding the boundary with a full half edge pair too, but with one of the half edges having a null *face* pointer**.

So the boundary edge actually does have an opposite (or `pair` pointer) and that opposite is fully integrated into the pointer structure, complete with `next` pointer and everything. Just that its face pointer in null, thus denoting an empty face or hole. So basically **every hole is represented by a null face with half edges going around it**.

In addition to being able to iterate around vertices regardless of the starting point, this also has the advantage that you can easily iterate around boundary curves. And you can even have more than one hole at a vertex (although, that can still be problematic in other situations). Of course you might still have to handle the boundary half edges specially in some situations, especially when you're using the face pointers, but you won't get around that anyway if your mesh can have holes.

---

If that is too much of a hassle to restructure your data and algorithms this way, though, maybe you can instead adjust your **vertex starting edge pointers to always point to the boundary edge** if there is one. You'd of course have to make sure that stays consistent, but if you can assume that as a precondition, you can just start iterating from there. And you can also check immediately if the vertex is at a boundary without having to iterate.


---

