Computational Geometry Package

Computational geometry is the study of efficient algorithms for solving geometric problems. The nearest neighbor problem involves identifying one point, out of a set of points, that is nearest to the query point according to some measure of distance. The nearest neighborhood problem involves identifying the locus of points lying nearer to the query point than to any other point in the set. This package provides functions for solving these and related problems in the case of planar points and the Euclidean distance metric.

ConvexHull[{{x1,y1},{x2,y2},...}]compute the convex hull of a set of points in the plane
DelaunayTriangulation[{{x1,y1},{x2,y2},...}]
compute the Delaunay triangulation of a set of points in the plane
VoronoiDiagram[{{x1,y1},{x2,y2},...}]
compute the Voronoi diagram of a set of points in the plane

Computational geometry functions.

The convex hull of a set S is the boundary of the smallest set containing S. The Voronoi diagram of S is the collection of nearest neighborhoods for each of the points in S. For points in the plane, these neighborhoods are polygons. The Delaunay triangulation of S is a triangulation of the points in S such that no triangle contains a point of S in its circumcircle. This is equivalent to connecting the points in S according to whether their neighborhood polygons share a common side.

This loads the package.
In[1]:=
Click for copyable input
Here is a list of points in the plane.
In[2]:=
Click for copyable input
This gives the indices of the points lying on the convex hull in counterclockwise order.
In[3]:=
Click for copyable input
Out[3]=
Duplicate points are ignored.
In[4]:=
Click for copyable input
Out[4]=
This gives the counterclockwise vertex adjacency list for each point in the Delaunay triangulation. For example, the entry indicates that the first point in is connected in counterclockwise order to the fourth, third, and second points.
In[5]:=
Click for copyable input
Out[5]//Shallow=

While DelaunayTriangulation need only specify the connections between points, VoronoiDiagram must specify both a set of diagram vertices and the connections between those vertices. Another difference between the two functions is that while a triangulation consists of segments, a diagram consists of both segments and rays. For example, in the case of a Voronoi diagram, points in the interior of the convex hull will have nearest neighborhoods that are closed polygons, but the nearest neighborhoods of points on the convex hull will be open polygons.

These considerations make the output of VoronoiDiagram more complex than that of DelaunayTriangulation. The diagram is given as a list of diagram vertices followed by a diagram vertex adjacency list. The finite vertices of the diagram are listed first in the vertex list. The vertices lying at infinity have head Ray and are listed last.

This assigns the list of Voronoi diagram vertices to and the Voronoi diagram vertex adjacency list to .
In[6]:=
Click for copyable input
The first vertex in is a finite diagram vertex having coordinates . The last vertex in is a point at infinity. This point is represented by a Ray object having origin and containing .
In[7]:=
Click for copyable input
Out[7]=
Each entry in gives the index of a point in followed by a counterclockwise list of the Voronoi diagram vertices that comprise the point's nearest neighborhood polygon.
In[8]:=
Click for copyable input
Out[8]//Short=
Here is the Voronoi polygon vertex adjacency list for the first point in .
In[9]:=
Click for copyable input
Out[9]=
This selects the coordinates of the polygon vertices from . The first two vertices have head List, while the last two have head Ray. Thus, the Voronoi polygon associated with the first point in is open and is defined by a segment and two rays.
In[10]:=
Click for copyable input
Out[10]=
VoronoiDiagram[{{x1,y1},{x2,y2},...},delval]
compute the Voronoi diagram using the Delaunay triangulation vertex adjacency list delval
VoronoiDiagram[{{x1,y1},{x2,y2},...},delval,convexhull]
compute the Voronoi diagram using the Delaunay triangulation vertex adjacency list delval and the convex hull index list convexhull

Computing the Voronoi diagram using the Delaunay triangulation and the convex hull.

This computes the Voronoi diagram of more efficiently by making use of the Delaunay triangulation vertex adjacency list.
In[11]:=
Click for copyable input
Here the Voronoi diagram is computed using both the Delaunay triangulation and the convex hull.
In[12]:=
Click for copyable input
PlanarGraphPlot[{{x1,y1},{x2,y2},...}]
plot the Delaunay triangulation of the points
PlanarGraphPlot[{{x1,y1},{x2,y2},...},indexlist]
plot the graph depicted by the counterclockwise list of indices in indexlist
PlanarGraphPlot[{{x1,y1},{x2,y2},...},val]
plot the graph depicted by the vertex adjacency list val
DiagramPlot[{{x1,y1},{x2,y2},...}]plot the Voronoi diagram of the points
DiagramPlot[{{x1,y1},{x2,y2},...},diagvert,diagval]
plot the diagram depicted by the vertex list diagvert and the vertex adjacency list diagval
TriangularSurfacePlot[{{x1,y1,z1},{x2,y2,z2},...}]
plot the surface according to the Delaunay triangulation established by projecting the points onto the x-y plane
TriangularSurfacePlot[{{x1,y1,z1},{x2,y2,z2},...},trival]
plot the surface according to the triangulation depicted by the vertex adjacency list trival

Computational geometry plotting functions.

The default of PlanarGraphPlot is a plot of the Delaunay triangulation of the points.
In[13]:=
Click for copyable input
Out[13]=
This plots the convex hull of the points.
In[14]:=
Click for copyable input
Out[14]=
Here is an alternative triangulation.
In[15]:=
Click for copyable input
This plots the triangulation of given by .
In[16]:=
Click for copyable input
Out[16]=
The default of DiagramPlot is a plot of the Voronoi diagram of the points.
In[17]:=
Click for copyable input
Out[17]=
Here is an alternative set of diagram vertices.
In[18]:=
Click for copyable input
Here is an alternative diagram vertex adjacency list.
In[19]:=
Click for copyable input
This plots the diagram of given by and .
In[20]:=
Click for copyable input
Out[20]=
Here is a set of three-dimensional points having the same x-y coordinates as .
In[21]:=
Click for copyable input
The default of TriangularSurfacePlot is a plot of the z coordinates according to the connectivity established by the Delaunay triangulation of the x-y coordinates.
In[22]:=
Click for copyable input
Out[22]=
This plots the z coordinates according to the connectivity established by the triangulation .
In[23]:=
Click for copyable input
Out[23]=
Compare to the default ListPlot3D behavior.
In[24]:=
Click for copyable input
Out[24]=
ConvexHull[{{x1,y1},{x2,y2},...},AllPoints->False]
give the minimum set of points needed to define the convex hull
DelaunayTriangulation[{{x1,y1},{x2,y2},...},Hull->True]
give both the Delaunay triangulation vertex adjacency list and the convex hull
PlanarGraphPlot[{{x1,y1},{x2,y2},...},LabelPoints->False]
plot the Delaunay triangulation without labels
DiagramPlot[{{x1,y1},{x2,y2},...},LabelPoints->False]
plot the Voronoi diagram without labels
DiagramPlot[{{x1,y1},{x2,y2},...},TrimPoints->n]
plot the Voronoi diagram with the outermost ray plus of the outermost diagram vertices trimmed

Options for computational geometry functions.

This gives the minimum set of points needed to define the convex hull.
In[25]:=
Click for copyable input
Out[25]=
This returns both the Delaunay triangulation and the convex hull.
In[26]:=
Click for copyable input
Out[26]//Shallow=
Here is a set of random numbers uniformly distributed on ×.
In[27]:=
Click for copyable input
This computes the Voronoi diagram of .
In[28]:=
Click for copyable input
The diagram plot is dominated by outlier vertices.
In[29]:=
Click for copyable input
Out[29]=
TrimPoints->2 means that the diagram is plotted so that both the outermost ray and the outermost vertex are eliminated.
In[30]:=
Click for copyable input
Out[30]=
The TrimPoints option can be used to magnify the diagram until the points in fill the plot.
In[31]:=
Click for copyable input
Out[31]=
DelaunayTriangulationQ[{{x1,y1},{x2,y2},...},trival]
give True if the vertex adjacency list trival represents a Delaunay triangulation of the points, and False otherwise

Testing for a Delaunay triangulation.

is a Delaunay triangulation, so this returns True.
In[32]:=
Click for copyable input
Out[32]=
This returns False because is not a Delaunay triangulation.
In[33]:=
Click for copyable input
Out[33]=
BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...}]
compute the bounded Voronoi diagram of a set of points , where the bound is the convex polygon described by the points
BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...},delval]
compute the bounded Voronoi diagram using the Delaunay triangulation vertex adjacency list delval
BoundedDiagram[{{a1,b1},{a2,b2},...},{{x1,y1},{x2,y2},...},delval,convexhull]
compute the bounded Voronoi diagram using the Delaunay triangulation vertex adjacency list delval and the convex hull index list convexhull

Computing the bounded Voronoi diagram.

When spatial data is collected within a finite region of the plane, the unbounded Voronoi diagram of the points may not offer an accurate picture of the region of influence of each point. A tile on the periphery of the diagram will be open, indicating an infinite region of influence, when in fact an open tile is simply due to the limited extent of the spatial sampling. It is sometimes useful to intersect the unbounded Voronoi diagram of the data with the boundary of the convex region from which the data was collected. Then each point in the data can be associated with a closed tile or finite region of influence.

BoundedDiagram begins by finding the unbounded Voronoi diagram. It then works counterclockwise around the boundary, integrating bounding polygon vertices into the diagram, and deleting Voronoi diagram vertices falling outside of the boundary. Bounding an open tile of the Voronoi diagram allows you to approximate the true underlying closed tile you would have if the data collection had not been limited to a portion of the plane.

The bounded diagram is represented as two lists: (1) a vertex coordinate list, and (2) a vertex adjacency list, one entry for each point in the original unbounded diagram indicating the associated bounded polygon vertices in counterclockwise order.

Since BoundedDiagram requires the unbounded Voronoi diagram, the computation of the bounded diagram can be made more efficient by providing additional arguments, such as the Delaunay triangulation vertex adjacency list and the convex hull.

These are the coordinates of the rectangular region from which the sample was drawn.
In[34]:=
Click for copyable input
This assigns the list of bounded diagram vertices to and the bounded diagram vertex adjacency list to .
In[35]:=
Click for copyable input
Here is a plot of the bounded diagram of given by and .
In[36]:=
Click for copyable input
Out[36]=
TileAreas[{{x1,y1},{x2,y2},...},{{q1, q2,...},val}]
find the areas of the tiles centered on and having vertices , as stipulated by the vertex adjacency list val

Computing tile areas.

You can make use of Voronoi diagrams to build spatial interaction models, or simply calculate the area of influence of individual tiles.

In an unbounded Voronoi diagram, some of the tiles have infinite area.
In[37]:=
Click for copyable input
Out[37]=
In a bounded diagram, each of the tiles has finite area.
In[38]:=
Click for copyable input
Out[38]=
This gives the tile areas scaled by the area of the rectangle from which the sample was drawn.
In[39]:=
Click for copyable input
Out[39]=
New to Mathematica? Find your learning path »
Have a question? Ask support »