Efficient Way to construct triangles from Edges/Lines?

Question

Lets say I have a set of points and I have lines/edges between them. All of these edges create non-overlapping triangles within the convex hull of my points. All points are connected to triangles.

How can I efficiently check which points are part of which triangle? I could check incident points of each edge and gradually construct a triple of points, but that sounds awefully slow (o(n^2)?). Is there something like linesweep or so to do that?

cheers.

Answer 1

The edges define an undirected graph G and the triangles are the set of cycles in G with length=3.

Geometric triangulations typically have relatively low nodal degree (degree d is the number of edges adjacent to each node, d<=10 is typical for geometric triangulations) and, as such, here is a reasonably efficient O(n*d^3) algorithm that can be used to construct the set of triangles.

1. Setup a graph-like data structure, supporting access to the list of edges adjacent to each node.

2. Iterate over all nodes. Consider all pairs of edges adjacent to a given node i. For a given pair of edges adjacent to i, we have a potential nodal triplet i,j,k. This triplet is a triangle if there is an edge joining nodes j,k, which can be checked by scanning the edge lists of j,k.

Duplicate triangles will be generated by a naive implementation of (2). Maintain a hash table of triangles to reject duplicate triplets as they're considered.

I've assumed that the edges define a valid disjoint triangulation, being non-intersecting, etc.

Hope this helps.

Answer 2

If you have a 2-dimensional set-up like you described, then you have a fully triangulated planar graph (no intersecting edges when you exclude the endpoints) which spans the convex hull of your points. In this case, if you sort the edges around each vertex circularly according to the angle they make with the vertex, then you know for sure that each pair of adjacent edges makes a triangle. Furthermore, every triangle can be found this way if you perform this procedure for each vertex. Each triangle will be found 3 times when you iterate over all vertices. You can either use a hash table to detect duplicates, or sort all your triangles when you are done to identify duplicates. If you use hash table, then the overall complexity if you have V vertices is O(V log d), where d is the maximum degree of a vertex (because the total number of edges is linear in the number of vertices because you have a planar graph). So absolute worst-case is O(V log V), which is the same worst-case if you sort all triangles to find duplicates (because the max number of triangles is also linear in the number of vertices). The only caveat to make this work is that you need to know the neighbor vertices (i.e. the incidental edges) for each vertex.