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.

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.

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.

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

Computational geometry plotting functions.

Options for computational geometry functions.

Here is a set of random numbers uniformly distributed on ×.

Testing for a Delaunay triangulation.

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.

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.