This is documentation for Mathematica 5, which was
based on an earlier version of the Wolfram Language.

 DiscreteMath`ComputationalGeometry` 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 is the boundary of the smallest set containing . The Voronoi diagram of is the collection of nearest neighborhoods for each of the points in . For points in the plane, these neighborhoods are polygons. The Delaunay triangulation of is a triangulation of the points in such that no triangle contains a point of in its circumcircle. This is equivalent to connecting the points in according to whether their neighborhood polygons share a common side. This loads the package. In[1]:= < {"FontSize" -> 8}] Out[13]= This plots the convex hull of the points. In[14]:= PlanarGraphPlot[data2D, convexhull] Out[14]= Here is an alternative triangulation. In[15]:= trival = Insert[Insert[Delete[delval, {{12, 2, 4}, {16, 2, 2}}], 15, {11, 2, 2}], 11, {15, 2, 3}]; This plots the triangulation of data2D given by trival. In[16]:= PlanarGraphPlot[data2D, trival, TextStyle -> {"FontSize" -> 8}] Out[16]= The default of DiagramPlot is a plot of the Voronoi diagram of the points. In[17]:= DiagramPlot[data2D] Out[17]= Here is an alternative set of diagram vertices. In[18]:= diagvert = ReplacePart[vorvert, {-6., 0.}, {27, 2}]; Here is an alternative diagram vertex adjacency list. In[19]:= diagval = Join[Drop[vorval, -8], {{9, {1, 6, 8, 3}}, {10, {2, 6, 1, 24, 27}}}, Drop[vorval, 10]]; This plots the diagram of data2D given by diagvert and diagval. In[20]:= DiagramPlot[data2D, diagvert, diagval] Out[20]= Here is a set of three-dimensional points having the same coordinates as data2D. In[21]:= data3D = Map[Append[#, Sqrt[64-(#[[1]]-8)^2-(#[[2]]-8)^2]]&, data2D]; The default of TriangularSurfacePlot is a plot of the coordinates according to the connectivity established by the Delaunay triangulation of the coordinates. In[22]:= TriangularSurfacePlot[data3D] Out[22]= This plots the coordinates according to the connectivity established by the triangulation trival. In[23]:= TriangularSurfacePlot[data3D, trival] Out[23]= Options for computational geometry functions. This gives the minimum set of points needed to define the convex hull. In[24]:= ConvexHull[{{0,0}, {1,0}, {0,0}, {2,0}, {1,1}}, AllPoints -> False] Out[24]= This returns both the Delaunay triangulation and the convex hull. In[25]:= DelaunayTriangulation[data2D, Hull -> True] // Shallow Out[25]//Shallow= Here is a set of random numbers uniformly distributed on [0, 1][0, 1]. In[26]:= random = Table[{Random[], Random[]}, {40}]; This computes the Voronoi diagram of random. In[27]:= {randvert, randval} = VoronoiDiagram[random]; The diagram plot is dominated by outlier vertices. In[28]:= DiagramPlot[random, randvert, randval, LabelPoints -> False] Out[28]= TrimPoints -> 2 means that the diagram is plotted so that both the outermost ray and the outermost vertex are eliminated. In[29]:= DiagramPlot[random, randvert, randval, LabelPoints -> False, TrimPoints -> 2] Out[29]= The TrimPoints option can be used to magnify the diagram until the points in random fill the plot. In[30]:= DiagramPlot[random, randvert, randval, LabelPoints -> False, TrimPoints -> 6] Out[30]= Testing for a Delaunay triangulation. delval is a Delaunay triangulation, so this returns True. In[31]:= DelaunayTriangulationQ[data2D, delval] Out[31]= This returns False because trival is not a Delaunay triangulation. In[32]:= DelaunayTriangulationQ[data2D, trival] Out[32]= Computing the nearest neighbor. This computes the point in data2D nearest to {7.92, 8.92}. In[33]:= neighbor = NearestNeighbor[{7.92, 8.92}, data2D] Out[33]= If the Voronoi diagram is known, the diagram vertex list and vertex adjacency list can be substituted for the point list for a faster NearestNeighbor calculation. In[34]:= NearestNeighbor[{7.92, 8.92}, vorvert, vorval] Out[34]= This gives the coordinates of the Voronoi polygon containing {7.92, 8.92}. In[35]:= vorvert[[vorval[[neighbor, 2]]]] Out[35]= For each of the points in data2D, the nearest point in data2D is the point itself. In[36]:= NearestNeighbor[data2D, vorvert, vorval] Out[36]= The first half of these points is known to derive from one distribution; the second half is known to derive from another. In[37]:= known = Join[{{5.84, 1.2}, {5.94, 10.99}, {5.1, 2.82}, {5.8, 1.67}, {5.63, 10.}}, {{0.31, 5.11}, {7.73, 5.38}, {10.42, 5.89}, {6.1, 5.1}, {6.92, 5.63}}]; Each of these points is believed to derive from one of the two distributions. In[38]:= unknown = {{5.56, 7.48}, {5.1, 1.67}, {5.17, 4.89}, {0.3, 5.27}, {6.74, 5.73}, {5.09, 9.07}}; This classifies the points in unknown according to the classifications of their nearest neighbors in known. In[39]:= If[# > 5, 2, 1]& /@ NearestNeighbor[unknown, known] Out[39]= 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 one to approximate the true underlying closed tile one 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 data2D sample was drawn. In[40]:= b1 = {{0, 1}, {14, 1}, {14, 16}, {0, 16}}; This assigns the list of bounded diagram vertices to diagvert1 and the bounded diagram vertex adjacency list to diagval1. In[41]:= {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull]; Here is a plot of the bounded diagram of data2D given by diagvert1 and diagval1. In[42]:= DiagramPlot[data2D, diagvert1, diagval1] Out[42]= 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[43]:= TileAreas[data2D, diagvert, diagval] Out[43]= In a bounded diagram, each of the tiles has finite area. In[44]:= areas = TileAreas[data2D, diagvert1, diagval1] Out[44]= This gives the tile areas scaled by the area of the rectangle from which the sample was drawn. In[45]:= areas/(14 15) Out[45]=