Transform - 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 Triangulation Lines transform operator we can create a triangulation consisting of lines.



The result is a set of lines that show the boundaries of triangular tiles that completely cover the region between the points. Had we wished to create tiles in the form of area objects, we could have used the Triangulation Areas transform operator. Using the Triangulation operator would simultaneously create both Triangulation Lines as well as Triangulation Areas.


There are many different algorithms that may be used to decide how a point set should be triangulated. Manifold's transform toolbar Triangulation operators use Delaunay triangulation (also spelled the Delone triangulation). The 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 blue lines show the borders of Voronoi tiles. The green lines show the Delaunay triangulation. To make the triangulation we draw a line between every two points that share a border line in the Voronoi tiling.


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.




For example, if we begin with a set of points shown above we can create a triangulation as seen below:




Transfer Rules


The triangulation operators except will transfer column data from source to target (created) objects using whatever transfer rules are in force for the data attribute columns.


See Also


Decompose to Triangles

Transform - Constrained Triangulation


Other types of networks easily created with transform operators:


Gabriel Network

Relative Neighborhood Network

Spanning Tree


Historical Note - 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 the French mathematician and astronomer who often is given credit for the triangulation method bearing this 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.


Boris Nikolaevich Delone (pronounced "Delaunay" and often spelled that way in English as well) is the Russian mathematician who invented the triangulation method now universally used throughout computational geometry.





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 researches in algebra. Delone became an Academician 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 worldview 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 ".




"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.


The Cyrillic for "Delone" is pronounced the same way as "Delaunay". It is an oddly French-sounding surname within the Russian world. Due to pronunciation conventions in English it strikes us as odd that the Latin spelling of "Delone" would be so pronounced. For this reason it is often spelled "Delaunay" in English texts, the convention adopted here.