Delaunay Milestone

Triangulation is an important tool in computational geometry, because it allows us to take a complicated shape and approximate it well by a collection of triangles, whose properties we understand. Instead of shape analysis, we will be looking at problems in which we start with a scattered set of points in the plane. A triangulation constructs the maximal number of non-intersecting triangles based on these points. For a given set of points there are many triangulations possible; the Delaunay triangulation is considered the best triangulation, as it does the best job of avoiding the use of small angles.

Topics we will need to learn include:

• Creating a triangulation usually starts with the coordinates of a set of N points, stored as an Nx2 array; the triangulation is created as an integer array of Mx3 indices. Each row of the triangulation array lists the indices of 3 rows of the coordinate array, which will be the vertices of one of the triangles. The value of M cannot be worked out in advance from the value of N. There are various programs for creating a triangulation from a set of points.
• A triangulation is always finite, and only involves triangles, so it is a very regular data structure. To describe a triangulation, we would need two files, an Nx2 node file (real numbers), and an Mx3 triangle file (integers). Let's write a Python function to read such information.
• It is worth practicing how to plot the triangles of a triangulation.
• The triangulation of a set of points is not unique. The Delaunay triangulation is (essentially) unique, and has the property that, of all possible triangulations, it has the maximum minimum angle. Let's understand that concept, and compare two triangulations to see what this means.
• In the polygon notebook, we already used the idea of understanding properties of the polygon by working with the properties of the triangles that form it. The same ideas allow us to work with the polygonal shape described by a triangulation. Let's show that, given a set of points and their triangulation, we can compute the area of the total shape, and the centroid, and uniform sample points, and hence an integral.
• SciPy includes commands to compute the Delaunay triangulation and to display it. The Delaunay triangulation is the "dual" of the Voronoi diagram. Let's plot both of these objects and see if we can understand this relationship.