1
\$\begingroup\$

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.

enter image description here

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;

        vertContainer.Add(startHE.SourceVert);

        do
        {
            vertContainer.Add(currentHE.Next.SourceVert);
            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. enter image description here

What's the best way to go about retrieving the vertices in this situation?

\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – Basic
    Nov 12, 2021 at 1:44
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 12, 2021 at 1:46

1 Answer 1

0
\$\begingroup\$

Your first approach is the best way to do this. You are getting the surrounding points, and then getting the next layer of points. This is the fastest way to make sure that you get all points depth 2 from the original vertex.

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

\$\endgroup\$
4
  • \$\begingroup\$ what are your thoughts on just comparing each vertex with the target vertex by calculating distance between them and then filtering out ones that are too far away? @Jay \$\endgroup\$ Nov 12, 2021 at 13:38
  • \$\begingroup\$ You mean distance in space or distance as number of edges? @nikonemanja \$\endgroup\$
    – Jay
    Nov 13, 2021 at 3:21
  • \$\begingroup\$ Distance in space. Taking the distance between a position and each vertex. @Jay \$\endgroup\$ Nov 13, 2021 at 17:00
  • \$\begingroup\$ @nikonemanja You could do that but you would be looking at the points only, so you would have no use for the edges in your data structure \$\endgroup\$
    – Jay
    Nov 15, 2021 at 1:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .