# Given a Set of Points, Find All the Triangular Faces that Connect Them Together

Let's say I have a list of points( in 2D coordinates!) with the vertex $V$, how to find all the triangular faces $F$ ( which has three edges $E$) that covers all of the points? In other words, I'm looking for a mesh that connects all the points together with well behaved triangles.

The conditions are that the faces must not overlap or cut through one another. And it would help if all the $F$ has not-too-narrow angles in it.

Also note that the meshing algorithm above must not introduced additional points.

I suspect that the delaunay algorithm is meant for something like this. But I am not too clear about this. Am I right? Or is it that there are other algorithms that work for this problem?

Edit: A point cloud is just a list of points, scattered in 2D. The condition is all the points must have distinct ${x,y}$ coordinates.

-
So, a convex hull? –  Ｊ. Ｍ. Dec 16 '10 at 8:45
@J.M., convex hull is all about finding the bounding face of the point cloud; it doesn't construct a set of faces that would connect all the points. –  Graviton Dec 16 '10 at 9:18
Many people have probably never heard of what a point cloud is. Would you be willing to provide a brief description? –  Eric Haengel Dec 16 '10 at 9:49
This is the problem of surface reconstruction, which has been a major research topic in computer graphics in the past decade. Google will find you several algorithms for this problem‌​. –  Rahul Dec 16 '10 at 21:29
Yes, it does sound like the Delaunay triangulation is what you are looking for. Read up on that first anyway. There are of course many possible different triangulations. The Delaunay triangulation maximizes the minimum angle that can be found in a triangle. –  yasmar Dec 17 '10 at 1:53

The Delaunay triangulation is a natural and popular way to triangulate the convex hull of a set of points, $P$, in the plane.

Conceptually, we can construct it as the dual of the Voronoi diagram of $P$. The Voronoi diagram partitions the plane into Voronoi cells, one for each point in $P$. The Voronoi cell for a point $p \in P$ is defined as that portion of the plane consisting of points that are at least as close to $p$ as to any other point in $P$. The Voronoi cells are convex polygons, but points on the convex hull of $P$ have unbounded Voronoi cells.

If two points are Voronoi neighbours, i.e., their Voronoi cells share a boundary edge, then they will be connected by an edge in the Delaunay tessellation. A Voronoi vertex is a vertex of the polygon describing a Voronoi cell. A Voronoi vertex belongs to at least three Voronoi cells. If there is no Voronoi vertex that is shared by more than three Voronoi cells, then the Delaunay tessellation will be the unique Delaunay triangulation (in which case we say the points are in general position). Otherwise, the Delaunay tessellation will contain higher order polygons, which may be triangulated arbitrarily to obtain a Delaunay triangulation.

The Delaunay triangles have the property that the inside of their circumcircles contain no points from $P$ (this is easy to check from the above description). Also, of all possible triangulations of $P$, the Delaunay triangulation maximizes the minimum angle that can be found in a triangle (this does not follow easily from the above description -- it is usually demonstrated via an edge flipping argument).

To construct the Delaunay triangulation in practice, there are several efficient algorithms. There are also many freely available implementations of these algorithms. CGAL is one popular example.

-

Typically, in modeling problems of the kind you are suggesting there are a variety of ways that the triangles could be selected, and one's goal would govern how the triangles might be chosen. Sometimes these are referred to as a triangular mesh:

http://en.wikipedia.org/wiki/Triangle_mesh

For the analogous problem of selecting triangles based on a point set in the plane you can find some ideas here:

http://en.wikipedia.org/wiki/Point_set_triangulation

-
actually that is my problem; I don't know if any of the point triangulation can do what I want; namely all the triangles they form span over all of the vertexes, and in the process no additional vertex is introduced. –  Graviton Dec 17 '10 at 1:06