Algorithm design - a better way of finding sets of triangles that share a vertex

3
votes

I'm trying to calculate a Voronoi graph from a Delaunay Triangulation, I've got the triangulation data in the form of a collection of verticies (red circles on graph) and triangles (blue lines on graph):

enter image description here

I'm able to calculate the Voronoi graph verticies easily (the intersection of the red lines) by just getting the circumcenter of all the triangles.

However, I need to derive the 'cell' information for each red polygon. To do this, for each red vertices I need to find a set of triangles that share that same vertex. So for the circled vertex, I need the green triangles:

enter image description here

So my code looks like this (c#):

    foreach (Vertex3 vertex in DelaunayVertices)
    {
        VoronoiCell cell = new VoronoiCell();
        cell.Vertex = vertex;

        //seach all triangles for the ones that match this.
        foreach (Face3 face in DelaunayTriangles)
        {
            if (face.Vertices.Where(v => v.Equals(vertex)).Any())
            {
                //shares vertices, add it's circumcenter as an edge vertex of the cell
                cell.EdgeVertices.Add(face.Circumcenter);
            }
        }
    }

Which is of course, hugely inefficient, as it's searching everything. However, the collections of faces, or verities are completely unsorted (and I'm unsure exactly how to sort them, or if it would help). Just to be confusing, there are 3 dimensional vertex on the surface of a sphere.

The only thing I have to find adjacent vertexes or faces for each triangle I have it's Adjacency, so for the orange triangle below, I know the three green triangles:

enter image description here

I'm thinking it might be more efficient to traverse this graph, but I'm struggling to come up with an approach to an algorithm that will produce sets that share points.

2
c#algorithmdelaunayvoronoi
I fear that because of the domain-specific nature, there are hidden requirements/constraints that would make it hard to come up with an answer acceptable to you. That said, I will suggest that you simply maintain a dictionary, where each vertex is a key, and the value is a list of all the triangles which use that vertex. You can populate the dictionary by enumerating the triangles, adding that triangle to each of the three lists corresponding the triangle's vertexes. Once the data structure is created, retrieving triangles for a given vertex is O(n), where n is the number of triangles found. – Peter Duniho
That sounds like a good plan, should have though of trying something similar. I'll give a go at implementing it, see how it performs. – Joe

2 Answers

1
votes

You could try a space filling curve, i.e. sorting the vertexes along a hilbert curve. You could also try a point-in-polygon test but it's very difficult. You could also try to make a bitmap with brute force algorithm.

0
votes

If you're willing to store a secondary vertex-to-triangle data-structure, you can first traverse the triangle list, pushing each triangle onto the adjacency lists associated with its three vertices:

for (all tria's ti)
    for (all nodes ni in tria ti)
        v2t[ni] <- ti
    end for
end for

This is just an O(n) sweep.