# How do I get a range of vertices/edges using a half-edge data structure?

I have a half-edge data structure in 2D which loops through edges in a triangle in a clockwise order. I'm trying to get a range of vertices within a target vertex. Let's say I want all vertices within a depth of 2 like the picture below where the yellow vertex 0 is the target and the green vertices are the one's being retrieved. So far this is what I have:

public List<Vertex> GetSurroundingVerts(int index)
{
List<Vertex> vertContainer = new List<Vertex>();
HalfEdge startHE = Vertices[index].SourceHE;
HalfEdge currentHE = startHE;

do
{
currentHE = currentHE.Twin.Next;
} while (currentHE != startHE);
return vertContainer;
}


This works for getting the immediate surrounding vertices of a target vertex but once you increase the range, using this approach for each vertex will be more expensive the larger the range is. For the example picture above we have to check 19 vertices. 19 * 6 = 114 iterations which already becomes more expensive than just using a for-loop and comparing each vertex with the target vertex.

Currently, I'm trying to see if an algorithm that can traverse through the edges in a straight direction is possible (0 to 1 to 7 to 19 to 37 in the picture below) but no luck so far. What's the best way to go about retrieving the vertices in this situation?

• What's your use-case? How static is the mesh and how often do you need to do a lookup? I ask as if you need to do this frequently or there's a large set/you need to handle changes smoothly, those problems lend themselves to graph theory. You basically want all paths from your start node with a length <= 2. You can also find shortest path, etc See also learn.unity.com/tutorial/graph-theory Nov 12, 2021 at 1:44
• @Basic I'm using a half-edge data structure with the intent of displacing vertices as well as adding and removing vertices, subdividing depending on whether an edge is of a certain length. So in general, not static. Nov 12, 2021 at 1:46

The only thing I would change is using a container like SortedSet instead of Vector because it will reduce potential overlap.