Transform - Geometry: Triangulate

The Triangulate template appears in the template list when a geometry field, of type geom, geommfd, or geomwkb, has been picked in the Transform pane. It triangulates points and multipoints.

Triangulate

Perform a Delaunay triangulation on all points and multipoints, creating triangular areas or lines as specified in the Output type box, and save into the specified Result destination using the specified geometry type. Ignores areas and lines in the original geometry field.

Output types:

area - create triangular areas from the set of source points.
line - create line boundaries for triangles from the set of source points.

Launch the template by choosing a geometry field and then double-clicking the Triangulate template. When the template launches we can specify options.

Triangulate : area

Triangulates points to create areas. Given three or more points, performs a Delaunay triangulation of the points to create triangles as area objects. Areas, lines, and point objects that are multipoints are ignored.

We start with a drawing that contains points. None of the points are multipoints.

With the focus on the drawing, in the Transform pane we choose the Geom field and then we choose the Triangulate template.

In the Triangulate template we choose the area operation. We choose New Table and specify Triangulation areas for the name of the new drawing. As we enter the name for the drawing, the pane will automatically fill in an analogous name for the table. We can change that if we like. Press Transform.

A new Triangulation areas drawing and table appears in the Project pane. We drag and drop the new Triangulation areas drawing as a layer into the Points Drawing window.

The Triangulation areas drawing shows how the triangular areas are built using the original point locations as vertices for the triangles.

The Triangulate template does a triangulation on all points and multipoints in the drawing (or in the selection) as a single set. To perform a triangulation that is constrained within each individual area or line object, use Split : triangles.

Triangulate : line

Triangulates points to create lines. Given three or more points, performs a Delaunay triangulation of the points to create triangles as line objects. Areas, lines, and point objects that are multipoints are ignored.

We start with a drawing that contains points. None of the points are multipoints.

With the focus on the drawing, in the Transform pane we choose the Geom field and then we choose the Triangulate template.

In the Triangulate template we choose the line operation. We choose New Table and specify Triangulation lines for the name of the new drawing. As we enter the name for the drawing, the pane will automatically fill in an analogous name for the table. We can change that if we like. Press Transform.

A new Triangulation lines drawing and table appears in the Project pane. We drag and drop the new Triangulation lines drawing as a layer into the Points Drawing window.

The Triangulation areas drawing shows how the lines operation creates lines and not areas, using the original point locations as vertices.

Notes

Curvilinear segments - As a practical matter, most people doing GIS will use straight line segments for lines and areas. Few GIS systems do a good job of supporting curved segments, so there is much less data published using curved segments. Manifold's ability to work with curved segments allows us to use that data within Manifold in a limited way, at least for display and interactive editing.

However, most processing tools in Manifold, such as Transform templates and various Geom SQL functions, do their work by first converting a curvilinear segment into a straight line segment between the same two start and finish coordinates. That will often lead to weird or otherwise unexpected results. To avoid such problems, first convert curvilinear segments into equivalent constellations of straight line segments at whatever resolution is desired, using the Clean transform template with the convert curves to lines operation option and the number of linear segments desired to approximate the curve in the Curve limit parameter. See the Curved Segments discussion in the Drawings topic.

Triangulation and Voronoi Diagrams - There are many different algorithms that may be used to decide how a point set should be triangulated. The Transform pane Triangulation operators use Delaunay triangulation (also spelled Delone triangulation). A Delaunay triangulation of a point set treats the points as nodes in a network and draws links between them that divides the region between the points into triangular tiles.

If we take a set of points as shown above and apply the Triangulate All transform operator we can create a triangulation consisting of areas.

The result is a set of areas (see above with Style using a transparent fill color, showing only the area borders) which are triangular tiles that completely cover the region between the points.

A Delaunay triangulation is closely related to the Voronoi tiling of a region, as can be seen from the following illustration that shows both a Voronoi tiling as well as a triangulation.

The purple lines show the borders in a Voronoi diagram, as discussed in the Voronoi Diagrams topic. The blue lines show the borders of a Delaunay triangulation. To make the triangulation we create a boundary between every two points that share a border line in the Voronoi tiling. Georgi Voronoi was Boris Delone's doctoral thesis advisor.

Triangulations can be used for many purposes. They are a natural way of creating a network by connecting points that allows "travel" between points. Triangulations have great use in interpolation as well.

A Tale of Two "Delaunays" - Through an accident of translation of a Russian name into Latin characters, the wrong mathematician is often credited with the invention of Delaunay triangulation: Charles-Eugene Delaunay was a brilliant French mathematician and astronomer who often is given credit for the triangulation method bearing that name. However, he is the wrong "Delaunay".

Charles-Eugene Delaunay (1816 - 1872)

Educated at the Ecole des Mines in engineering and at the Sorbonne in astronomy, the French mathematician and astronomer Charles-Eugene Delaunay is best known for his contributions to the theory of lunar motion. He is honored with a lunar crater named for him as well as several street features in Paris. These include the Square Delaunay, the Rue Delaunay and (perhaps especially amusing to GIS beginners) the Impasse Delaunay. Delaunay drowned in 1872 in a boating accident in the English Channel near Cherbourg.

The right "Delaunay" is Борис Николаевич Делоне (pronounced "Delaunay"), the Russian mathematician who invented the triangulation method now universally used throughout computational geometry. Delone's name is Latinized in English texts as Boris Nikolaevich Delone or as Boris Nikolaevich Delaunay in French texts. Delone initially used the French version, that being the name of his French ancestor in the early 19th century, and then later in life switched to the English version.

Boris Nikolaevich Delone (1890 - 1980)

Борис Николаевич Делоне

Boris Delone was born in St. Petersburg on March 15, 1890 and lived a long life as a mathematician and mountain climber. He persisted in the study of algebra even after the utilitarian transformation of society in the wake of the October revolution discouraged the study of abstract mathematics. After graduating from Kiev University in 1913 Delone taught at the Kiev Polytechnic Institute. He moved to St. Petersburg in 1922 to join the faculty at Leningrad University. In 1932 he worked in the Mathematics institute of the Academy of Sciences. In 1935 he became a professor of Mathematics at the University of Moscow (MGU) from 1935 to 1942. His work in triangulation arises from his work in mathematical crystallography. He also worked in computational geometry, the theory of numbers, and the history of mathematics as well as continuing his life-long research in algebra. Delone was appointed to the Academy of Science in 1929.

Delone's fame as a mountain climber within that sport was equal to his fame as a mathematician in scientific circles. He climbed numerous peaks of the highest difficulty in the wilds of the Caucasus, Central Asia and the Altai. He wrote of his life in mountaineering: "Mountain climbing in my life was not simply a sport or the source of a good mood. It is a world view that asserts simple truths, glorifying the good things: bravery and comradeship, the desire to know and the desire to help, a devotion to purpose, a sense of and joy in daring, keenness and striking courage".

The two Delaunays may be related: Boris Delone's Russian name is the Cyrillic spelling of his ancestor's surname, a French army officer surnamed De Launay, who was captured in Russia and became one of the lucky few to survive Napoleon's ill-fated invasion of Russian in 1812. Only 27,000 French soldiers remained after 480,000 were killed or captured during the invasion and subsequent retreat. De Launay married into Russian nobility and stayed in Russia, easy to do at a time when most noble families in Russia spoke French as much as Russian.

Pronunciation - Delaunay is normally pronounced in the French style, with stress on the final syllable: "Deh - lah - NAY". The name is pronounced with "short" vowels in the first two syllables and a long "a" in the last syllable. In Russian, Delone is pronounced exactly the same way. It is an oddly French-sounding surname within the Russian world, clearly indicating a surname of foreign origin.

Due to pronunciation conventions in English it seems wrong that the Latin spelling of Delone would be so pronounced. For this reason it is often spelled Delaunay in English texts, the convention adopted in this documentation.

Transform - Geometry: Triangulate

Notes

See Also