NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download". Try It in NetLogo Web

## WHAT IS IT?

This model constructs a Delaunay triangulation from a set of 2-dimensional spatial coordinates. A point-set triangulation is a division of a 2-dimensional space into triangles with vertices established by a given set of points, and in a Delaunay triangulation these triangles are created such that the minimum angle of each triangle is maximized, which avoids sliver triangles (thin triangles with two highly acute angles). It also has the defining characteristic that the circumcircle of every triangle contains none of the (other) points in the set.

Delaunay triangulation has a number of computational uses, including the creation of a Voronoi tesselation (of Thiessen polygons) corresponding to the point set and other processes associated with interpolating a spatially varying scalar quantity such as elevation or rainfall. Finding the Delaunay triangulation is a first step for some methods of creating contour lines for topographic or isopleth maps.

## HOW IT WORKS

Each point in the point-set is associated with a mobile agent (a turtle of breed "point") and triangle sides are established as undirected links (of breed "edge"). Additional agents of breed "triangle" are created to establish connectivity and to facilitate the logic for determining whether a point is within the circumcircle of a given triangle (by comparing the distance of that point from the circumcenter of the triangle to the radius of the circumcircle).

The model uses the Bowyer-Watson algorithm for computing the Delaunay triangulation, which requires the creation of three additional points as the vertices of a "super triangle" that circumscribes the original set of points, or, as in this case, a pair of adjacent super triangles forming a super 'square'. The algorithmn considers each point in the data set incrementally (based on horizontal coordinate left-to-right), removing triangles that are interposed by the new point and replacing them with new conforming triangles by connecting the new point to the vertices of a "star-shaped polygonal hole" created by the union of the recently removed triangles. The super triangle vertices and all associated connections are then removed from consideration leaving the desired triangulation.

Algorithmic note: in order to ensure the creation of a convex hull, the "super" vertices should be considered at an infinite distance from the data set (a consideration that does not appear to be part of the original Bowyer or Watson literature)

## HOW TO USE IT

X1,Y1,X2,Y2,...: The user can enter a desired set of coordinates into the provided input boxes being sure that the values stay within the range listed as 'minimum x','maximum x','minimum y' and 'maximum y' above the viewscreen. Each ordered pair should also be unique. Screen size can be expanded using SETTINGS which will be reflected in the min-max monitors.

POINT1, POINT2, ...: Each spatial point can be toggled ON or OFF using the switch to have the point included in (ON) or excluded from (OFF) the point set, but note that each active point should have a unique location to avoid an error message.

VAL1, VAL2,...: These input boxes are provided to associate a scalar value with each spatial point. This value serves no function in this model, but is included under the assumption that the model might be expanded as part of a larger interpolation model.

SETUP: When pressed, displays all the active points with an identifying label

TRIANGULATE: When pressed, executes SETUP and then calculates and displayes the Delaunay triangulation of the active spatial points. Intermediate triangulations following the Bowyer-Watson algorithm are temporarily displayed but may not be visible.

PAUSE-BETWEEN-INCREMENTS?: When toggled ON, the algorithm will pause at specified places in the algorithm, namely when considering the removal of triangles violated by a newly introduced vertex. The triangles are outlined in yellow and the vertex is displayed with a larger circle. Edges deleted from consideration are subsequently drawn in red. Click on the display screen to advance the algorithm.

## THINGS TO TRY

Adjust the speed slider towards "slower" to watch a visualization of the Bowyer-Watson calculation.

## EXTENDING THE MODEL

Delaunay triangulation is a first step for some methods of creating contour lines for topographic or isopleth maps (see "Related Models"), and for creating Thiessen polygons.

## NETLOGO FEATURES

The model uses specialized breeds of turtle agents to represent both vertices and triangles, as well as a breed of undirected link agents to represent triangle edges, greatly simplifying the visualization of the triangulation.

## RELATED MODELS

The author has shared other models entitled 'Contour20' as well as a 3D version 'Contour30' that uses this triangulation in the creation of an isopleth map using contour lines.

## AUTHORSHIP
Created Dec 2017
Garrett Love, Ph.D.
Engineering Instuctor
NC School of Science and Math

This work supported by the National Science Foundation
STEM + C Award 1543228
Comp Hydro: Integrating data, computation, and visualization for model-based water literacy

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.

## CREDITS AND REFERENCES

En.wikipedia.org. (2017). Bowyer–Watson algorithm. [online] Available at: https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm [Accessed 20 Dec. 2017].

Bowyer, Adrian (1981). "Computing Dirichlet tessellations". Comput. J. 24 (2): 162–166.

Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes". Comput. J. 24 (2): 167–172.

C. Arens. The Bowyer-Watson Algorithm; An efficient Implementation in a Database Environment. Technical report, Delft University of Technology, January 2002.
https://repository.tudelft.nl/islandora/object/uuid:c65ca155-54d0-4681-96ff-62c39db19fc0/datastream/OBJ