QGIS Delaunay Triangulation

Delaunay Triangulation - What is it and what can we do with it?

In mathematics and computational geometry, a Delaunay Triangulation (DT) for a set P of points (Let P = {P1,…Pn}) in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles. - Wikipedia Page on Delaunay Triangulation

But what does that mean?

Myers-20131124-01-DelaunayTriangulation.png Myers-20131124-02-CompareConvexH.png
Delaunay Triangulation Convex Hull

For this demo, the point data was points of interest in the Bay Area. Many of those points happen to be shopping centers, so only the shopping centers were selected and used that to create these maps, that way we can see what Convex Hull does - it triangulates an area based on points. We could think of this as a Shopping Center Area.

A Triangulation creates a plane out of triangles. The effect of Delaunay Triangulation is a more-detailed version of the Convex Hull. It takes point data, and it triangulates each of the points (creating triangles between the points). So it takes the premise of Convex Hull - putting a rubber band around the area that contains all the points, and it uses more rubber bands, putting a band around every 3 points and creating a series of triangles within the Convex Hull. If you compare the two images above, you'll note that the Delaunay Triangulation creates the same outside shape as the Convex Hull, but on top of that it creates a triangle between all of the points.

But that's just if you're using an x,y coordinate system. If we have point data using the x,y,z coordinate system - where x is longitude, y is latitude and z is depth - not only can you still use Delaunay Triangulation, but it is helpful in showing elevation and other 3D effects (They have a really good explanation here: http://www.mathworks.com/help/matlab/math/delaunay-triangulation.html).


Primary Sources




http://www.cs.uu.nl/docs/vakken/ga/slides9alt.pdf (Added by PT)