CODEWITHSUNDEEP
c#algorithmdelaunayvoronoi
Joe
Joe

Reputation: 7004

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

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.

Upvotes: 3

Views: 1142

Answers (2)

Cybercartel
Cybercartel

Reputation: 12592

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.

Upvotes: 1

Darren Engwirda
Darren Engwirda

Reputation: 7015

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.

Upvotes: 0

Related Questions