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

Question

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.

alt text

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.

alt text

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

Answer 1

I'll admit I'm not quite sure what you are asking for, but if you are looking for an algorithm that will give you all the vertices in a straight line out from the starting vertex, then you could just test how each new edge lines up with the direction you are trying to go using the Dot Product.

I've written up (but not tested) some sample code that should give you all the vertices in a straight line, and only grows with the number of edges per vertex rather than the number of vertices. Hopefully this is close to what you are looking for.

 public class Vertex{
     public List<Edge> edges;
     public Vector3 position;
     public int index;
 }
 
 public class Edge{
     public int p1_index, p2_index;
 }
 
 public List<Vertex> masterVertexList;
 
 public List<Vertex> GetStraightVertices(int startingVertex, int secondVertex, float dotProductCutoff = 0.5f){
 
     List<int> outputVertexIndices = new List<int>();
 
     Vector3 direction;
     float dot = 0;
     Vertex a = masterVertexList[startingVertex];
     Vertex b = masterVertexList[secondVertex];
 
     bool doneSearching = false;
 
     while(doneSearching == false) {
         //Get the direction between the first 2 vertices
         direction =  = b.position - a.position;
         
         int bestIndex = 0;
         float bestDotProduct = 0;
         Vertex c;
 
         //Find the edge attached to the second vertex whose direction most closely matches the initial direction        
         foreach (Edge e in b.edges)
         {
             
             //For each edge attached to the second vertex, find the closeness of its direction to the initial direction using the dot product
             if(p1_index == b.index){
                 c = masterVertexList[p2_index];
                 float dotProduct = Vector3.Dot(c.position - b.position, direction);
                 if(dotProduct > bestDotProduct){
                     //Keep track of the best matching 
                     bestIndex = p2_index;
                     bestDotProduct = dotProduct;
                 } 
             }
             else if (p2_index == b.index){
                 c = masterVertexList[p1_index];
                 float dotProduct = Vector3.Dot(c.position - b.position, direction);
                 if(dotProduct > bestDotProduct){
                     //Keep track of the best matching 
                     bestIndex = p1_index;
                     bestDotProduct = dotProduct;
                 } 
             }
         }
 
 
         //Add our new vertex to our output list
         //End once we cannot find an edge that matches close enough to our initial direction
         if(bestDotProduct > dotProductCutoff){
             outputList.Add(bestIndex);
             a = b;
             b = masterVertexList[bestIndex];
         }
         else{
             doneSearching = true;
         }
 
     }
 }

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

1 Reply

Your answer

Follow this Question

Related Questions