While it is possible to compute the convex hull of a reasonably large set of points in the plane through the geometry module of the library SymPy, this is not recommended. A much faster and reliable code is available in the module scipy.spatial through the class ConvexHull, which implements a wrapper to the routine qconvex, from the Qhull libraries (http://www.qhull.org/). This routine also allows the computation of convex hulls in higher dimensions. Let's compare both methods, with the famous Lake Superior polygon, superior.poly.

Following is an example.

# part of file chapter6.py
from numpy import array
def read_poly(file_name):
  """
  Simple poly-file reader, that creates a python dictionary
  with information about vertices, edges and holes.
  It assumes that vertices have no attributes or boundary markers.
  It assumes that edges have no boundary markers.
  No regional attributes or area constraints are parsed.
  """
  output = {'vertices': None, 'holes': None, 'segments': None}
  # open file and store lines in a list
  file = open(file_name, 'r')
  lines = file.readlines()
  file.close()
  lines = [x.strip('
').split() for x in lines]
  # Store vertices
  vertices= []
  N_vertices,dimension,attr,bdry_markers = [int(x) for x in lines[0]]
  # We assume attr = bdrt_markers = 0
  for k in range(N_vertices):
    label,x,y = [items for items in lines[k+1]]
    vertices.append([float(x), float(y)])
  output['vertices']=array(vertices)
  # Store segments
  segments = []
  N_segments,bdry_markers = [int(x) for x in lines[N_vertices+1]]
  for k in range(N_segments):
    label,pointer_1,pointer_2 = [items for items in lines[N_vertices+k+2]]
    segments.append([int(pointer_1)-1, int(pointer_2)-1])
  output['segments'] = array(segments)
  # Store holes
  N_holes = int(lines[N_segments+N_vertices+2][0])
  holes = []
  for k in range(N_holes):
    label,x,y = [items for items in lines[N_segments + N_vertices + 3 + k]]
    holes.append([float(x), float(y)])
  output['holes'] = array(holes)
  return output

Notice that loading each vertex as Point, as well as computing the convex hull with that structure, requires far too many resources and too much time. Note the difference:

In [1]: import numpy as np, matplotlib.pyplot as plt; 
   ...: from sympy.geometry import Point, convex_hull; 
   ...: from scipy.spatial import ConvexHull; 
   ...: from chapter6 import read_poly
In [2]: lake_superior = read_poly("superior.poly"); 
   ...: vertices_ls = lake_superior['vertices']
In [3]: %time hull = ConvexHull(vertices_ls)
CPU times: user 1.59 ms, sys: 372 µs, total: 1.96 ms
Wall time: 1.46 ms
In [4]: vertices_sympy = [Point(x) for x in vertices_ls]
In [5]: %time convex_hull(*vertices_sympy)
CPU times: user 168 ms, sys: 54.5 ms, total: 223 ms
Wall time: 180 ms
Out[5]:
Polygon(Point(1/10, -629607/1000000), Point(102293/1000000, -635353/1000000),
        Point(2773/25000, -643967/1000000), Point(222987/1000000, -665233/1000000),
        Point(8283/12500, -34727/50000), Point(886787/1000000, -1373/2000),
        Point(890227/1000000, -6819/10000), Point(9/10, -30819/50000),
        Point(842533/1000000, -458913/1000000), Point(683333/1000000, -17141/50000),
        Point(16911/25000, -340427/1000000), Point(654027/1000000, -333047/1000000),
        Point(522413/1000000, -15273/50000), Point(498853/1000000, -307193/1000000),
        Point(5977/25000, -25733/50000), Point(273/2500, -619833/1000000))

Let us produce a diagram with the solution, using the computations of scipy.spatial.ConvexHull:

In [5]: plt.figure(); 
   ...: plt.xlim(vertices_ls[:,0].min()-0.01,   vertices_ls[:,0].max()+0.01); 
   ...: plt.ylim(vertices_ls[:,1].min()-0.01, vertices_ls[:,1].max()+0.01); 
   ...: plt.axis('off'); 
   ...: plt.axes().set_aspect('equal'); 
   ...: plt.plot(vertices_ls[:,0], vertices_ls[:,1], 'b.')
Out[5]: [<matplotlib.lines.Line2D at 0x10ee3ab10>]
In [6]: for simplex in hull.simplices:
   ...:     plt.plot(vertices_ls[simplex, 0], ...:              vertices_ls[simplex, 1], 'r-')
In [7]: plt.show()

This plots the following image:

To modify the output of ConvexHull, we are allowed to pass all required qconvex controls through the parameter qhull_options. For a list of all qconvex controls and other output options, consult the Qhull manual at http://www.qhull.org/html/index.htm. In this chapter, we are content with showing the results obtained with the default controls qhull_options='Qx Qt' if the dimension of the points is greater than four, and qhull_options='Qt' otherwise.

Let's now illustrate a few advanced uses of ConvexHull. First, the computation of the convex hull of a random set of points in the 3D space. For visualization, we will use the mayavi libraries:

In [8]: points = np.random.rand(320, 3)
In [9]: hull = ConvexHull(points)
In [10]: X = hull.points[:, 0]; 
   ....: Y = hull.points[:, 1]; 
   ....: Z = hull.points[:, 2]
In [11]: from mayavi import mlab
In [12]: mlab.triangular_mesh(X, Y, X, hull.simplices,
   ....:                      colormap='gray', opacity=0.5,
   ....:                      representation='wireframe')

This plots the following image:

Computing the Voronoi diagram of a set of vertices (our seeds) can be done with the class Voronoi (and its companion voronoi_plot_2d for visualization) from the module scipy.spatial. This class implements a wrapper to the routine qvoronoi from the Qhull libraries, with the following default controls qhull_option='Qbb Qc Qz Qx' if the dimension of the points is greater than four, and qhull_options='Qbb Qc Qz' otherwise. For the computation of the furthest-site Voronoi diagram, instead of the nearest-site, we would add the extra control 'Qu'.

Let's work a simple example with the usual Voronoi diagram:

In [13]: from scipy.spatial import Voronoi, voronoi_plot_2d
In [14]: vor = Voronoi(vertices_ls)

To understand the output, it is very illustrative to replicate the diagram that we obtain by restricting the visualization obtained by voronoi_plot_2d in a small window, centered somewhere along the north shore of Lake Superior:

In [15]: ax = plt.subplot(111, aspect='equal'); 
   ....: voronoi_plot_2d(vor, ax=ax); 
   ....: plt.xlim( 0.45,  0.50); 
   ....: plt.ylim(-0.40, -0.35); 
   ....: plt.show()

This plots the following image:

There are other attributes of the object vor that we could use to inquire properties of the Voronoi diagram, but the ones we have described should be enough to replicate the previous diagram. We leave this as a nice exercise:

A triangulation of a set of vertices in the plane is a division of the convex hull of the vertices into triangles, satisfying one important condition. Any two given triangles can be either one of the following:

These plain triangulations have not much computational value, since some of their triangles might be too skinny—this leads to uncomfortable rounding errors, computation or erroneous areas, centers, and so on. Among all possible triangulations, we always seek one where the properties of the triangles are somehow balanced.

With this purpose in mind, we have the Delaunay triangulation of a set of vertices. This triangulation satisfies an extra condition—none of the vertices lie in the interior of the circumcircle of any triangle. We refer to triangles with this property as Delaunay triangles.

For this simpler setting, in the module scipy.spatial, we have the class Delaunay, which implements a wrapper to the routine qdelaunay from the Qhull libraries, with the controls set exactly, as in the case of the Voronoi diagram:

In [20]: from scipy.spatial import Delaunay
In [21]: tri = Delaunay(vertices_ls)
In [22]: plt.figure()
   ....: plt.xlim(vertices_ls[:,0].min()-0.01, vertices_ls[:,0].max()+0.01); 
   ....: plt.ylim(vertices_ls[:,1].min()-0.01,vertices_ls[:,1].max()+0.01); 
   ....: plt.axes().set_aspect('equal'); 
   ....: plt.axis('off'); 
   ....: plt.triplot(vertices_ls[:,0], vertices_ls[:,1], tri.simplices, 'k-'); 
   ....: plt.plot(vertices_ls[:,0], vertices_ls[:,1], 'r.'); 
   ....: plt.show()

This plots the following diagram:

It is possible to generate triangulations with imposed edges too. Given a collection of vertices and edges, a constrained Delaunay triangulation is a division of the space into triangles with those prescribed features. The triangles in this triangulation are not necessarily Delaunay.

We can accomplish this extra condition sometimes by subdividing each of the imposed edges. We call this triangulation conforming Delaunay, and the new (artificial) vertices needed to subdivide the edges are called Steiner points.

A constrained conforming Delaunay triangulation of an imposed set of vertices and edges satisfies a few more conditions, usually setting thresholds on the values of angles or areas of the triangles. This is achieved by introducing a new set of Steiner points, which are allowed anywhere, not only on edges.

Let's compute those different triangulations for our running example. We once again use the poly file with the features of Lake Superior, which we read into a dictionary with all the information about vertices, segments, and holes. The first example is that of the constrained Delaunay triangulation (cndt). We accomplish this task with the flag p (indicating that the source is a planar straight line graph, rather than a set of vertices):

In [23]: from triangle import triangulate, plot as tplot
In [24]: cndt = triangulate(lake_superior, 'p')
In [25]: ax = plt.subplot(111, aspect='equal'); 
   ....: tplot.plot(ax, **cndt); 
   ....: plt.show()

Note the improvement with respect to the previous diagram, as well as the absence of triangles outside of the original polygon:

The next step is the computation of a conforming Delaunay triangulation (cfdt). We enforce Steiner points on some segments to ensure as many Delaunay triangles as possible. We achieve this with the extra flag D:

In [26]: cfdt = triangulate(lake_superior, 'pD')

Either slight or no improvement, with respect to the previous diagram, can be observed in this case. The real improvement arises when we further impose constraints in the values of minimum angles on triangles (with the flag q) or in the maximum values of the areas of triangles (with the flag a). For instance, if we require a constrained conforming Delaunay triangulation (cncfdt) in which all triangles have a minimum angle of at least 20 degrees, we issue the following command:

In [27]: cncfq20dt = triangulate(lake_superior, 'pq20D')
In [28]: ax = plt.subplot(111, aspect='equal'); 
   ....: tplot.plot(ax, **cncfq20dt); 
   ....: plt.show()

This presents us with a much more improved result, as seen in the following diagram:

To conclude this section, we present a last example where we further impose a maximum area on triangles:

In [29]: cncfq20adt = triangulate(lake_superior, 'pq20a.001D')
In [30]: ax = plt.subplot(111, aspect='equal'); 
   ....: tplot.plot(ax, **cncfq20adt); 
   ....: plt.show()

The last (very satisfying) diagram is as follows:

We will use the previous example to introduce a special setting to the problem of shortest paths. We pick a location on the Northwest coast of the lake (say, the vertex indexed as 370 in the original poly file), and the goal is to compute the shortest path to the furthest Southeast location on the shore, at the bottom-right corner—this is the vertex indexed as 179 in the original poly file. By a path in this setting, we mean a chain of edges of the triangulation.

In the SciPy stack, we accomplish the computation of the shortest paths on a triangulation (and in some other similar geometries that can be coded by means of graphs) by relying on two modules:

Let's illustrate this example with proper code. We start by collecting the indices of the vertices of all segments in the triangulation, and the lengths of these segments.

In [31]: X = cncfq20adt['triangles'][:,0]; 
   ....: Y = cncfq20adt['triangles'][:,1]; 
   ....: Z = cncfq20adt['triangles'][:,2]
In [32]: Xvert = [cncfq20adt['vertices'][x] for x in X]; 
   ....: Yvert = [cncfq20adt['vertices'][y] for y in Y]; 
   ....: Zvert = [cncfq20adt['vertices'][z] for z in Z]
In [33]: from scipy.spatial import minkowski_distance
In [34]: lengthsXY = minkowski_distance(Xvert, Yvert); 
   ....: lengthsXZ = minkowski_distance(Xvert, Zvert); 
   ....: lengthsYZ = minkowski_distance(Yvert, Zvert)

We now create the weighted-adjacency matrix, which we store as a lil_matrix, and compute the shortest path between the requested vertices. We gather, in a list, all the vertices included in the computed path, and plot the resulting chain overlaid on the triangulation.

>>> from scipy.spatial import distance_matrix
>>> A = distance_matrix(cncfq20adt['vertices'], cncfq20adt['vertices'])

In [35]: from scipy.sparse import lil_matrix; 
   ....: from scipy.sparse.csgraph import shortest_path
In [36]: nvert = len(cncfq20adt['vertices']); 
   ....: G = lil_matrix((nvert, nvert))
In [37]: for k in range(len(X)):
   ....:     G[X[k], Y[k]] = G[Y[k], X[k]] = lengthsXY[k]
   ....:     G[X[k], Z[k]] = G[Z[k], X[k]] = lengthsXZ[k]
   ....:     G[Y[k], Z[k]] = G[Z[k], Y[k]] = lengthsYZ[k]
   ....:
In [38]: dist_mat, pred = shortest_path(G, return_predecessors=True,
   ....:                                directed=True, ....:                                unweighted=False)
In [39]: index = 370; 
   ....: path = [370]
In [40]: while index != 197:
   ....:     index = pred[197, index]
   ....:     path.append(index)
   ....:
In [41]: print path
[380, 379, 549, 702, 551, 628, 467, 468, 469, 470, 632, 744, 764, 799, 800, 791, 790, 789, 801, 732, 725, 570, 647, 177, 178, 179, 180, 181, 182, 644, 571, 201, 200, 199, 197]
In [42]: ax = plt.subplot(111, aspect='equal'); 
   ....: tplot.plot(ax, **cncfq20adt)
In [43]: Xs = [cncfq20adt['vertices'][x][0] for x in path]; 
   ....: Ys = [cncfq20adt['vertices'][x][1] for x in path]
In [44]: ax.plot(Xs, Ys '-', linewidth=5, color='blue'); 
   ....: plt.show()

This gives the following diagram:

The problem of point location is fundamental in computational geometry, given a partition of the space into disjoint regions, we need to query the region that contains a target location.

The most basic point location problems are those where the partition is given by a single geometric object—a circle or a polygon, for example. For those simple objects that have been constructed through any of the classes in the module sympy.geometry, we have two useful methods: .encloses_point and .encloses.

The former checks whether a point is interior to a source object (but not on the border), while the latter checks whether another target object has all its defining entities in the interior of the source object:

In [1]: from sympy.geometry import Point, Circle, Triangle
In [2]: P1 = Point(0, 0); 
   ...: P2 = Point(1, 0); 
   ...: P3 = Point(-1, 0); 
   ...: P4 = Point(0, 1)
In [3]: C = Circle(P2, P3, P4); 
   ...: T = Triangle(P1, P2, P3)
In [4]: print "Is P1 inside of C?", C.encloses_point(P1)
Is P1 inside of C? True
In [5]: print "Is T inside of C?", C.encloses(T)
Is T inside of C? False

Of special importance is this simple setting where the source object is a polygon. The routines in the sympy.geometry module get the job done, but at the cost of too many resources and too much time. A much faster way to approach this problem is by using the Path class from the libraries of matplotlib.path. Let's see how with a quick session. First, we create a representation of a polygon as a Path:

In [6]: import numpy as np, matplotlib.pyplot as plt; 
   ...: from matplotlib.path import Path; 
   ...: from chapter6 import read_poly; 
   ...: from scipy.spatial import ConvexHull
In [7]: superior = read_poly("superior.poly")
In [8]: hull = ConvexHull(superior['vertices'])
In [9]: my_polygon = Path([hull.points[x] for x in hull.vertices])

We can now ask whether a point (respectively, a sequence of points) is interior to the polygon. We accomplish this with either contains_point or contains_points:

In [10]: X = .25 * np.random.randn(100) + .5; 
   ....: Y = .25 * np.random.randn(100) - .5
In [11]: my_polygon.contains_points([[X[k], Y[k]] for k in range(len(X))])
Out[11]:
array([False, False,  True, False,  True, False, False, False,  True,
       False, False, False,  True, False,  True, False, False, False,
        True, False,  True,  True, False, False, False, False, False,
       ...
        True, False,  True, False, False, False, False, False,  True,
        True, False,  True,  True,  True, False, False, False, False,
       False], dtype=bool)

More challenging point location problems arise when our space is partitioned by a complex structure. For instance, once a triangulation has been computed, and a random location is considered, we need to query for the triangle where our target location lies. In the module scipy.spatial, we have handy routines to perform this task over Delaunay triangulations created with scipy.spatial.Delaunay. In the following example, we track the triangles that contain a set of 100 random points in the domain:

In [12]: from scipy.spatial import Delaunay, tsearch
In [13]: tri = Delaunay(superior['vertices'])
In [14]: points = zip(X, Y)
In [15]: print tsearch(tri, points)
[ -1 687  -1 647  -1  -1  -1  -1 805 520 460 647 580  -1  -1  -1  -1 304  -1  -1  -1  -1 108 723  -1  -1  -1  -1  -1  -1  -1 144 454  -1 -1  -1 174 257  -1  -1  -1  -1  -1  52  -1  -1 985  -1 263  -1 647 -1 314  -1  -1 104 144  -1  -1  -1  -1 348  -1 368  -1  -1  -1 988 -1  -1  -1 348 614  -1  -1  -1  -1  -1  -1  -1 114  -1  -1 684  -1 537 174 161 647 702 594 687 104  -1 144  -1  -1  -1 684  -1]

In [16]: print tri.find_simplex(points)
[ -1 687  -1 647  -1  -1  -1  -1 805 520 460 647 580  -1 -1  -1  -1 304  -1  -1  -1  -1 108 723  -1  -1  -1  -1  -1  -1  -1 144 454  -1  -1  -1 174 257  -1  -1  -1  -1 -1  52  -1  -1 985  -1 263  -1 647  -1 314  -1  -1 104 144  -1  -1  -1  -1 348  -1 368  -1  -1  -1 988  -1  -1  -1 348 614  -1  -1  -1  -1  -1  -1  -1 114  -1  -1 684  -1 537 174 161 647 702 594 687 104  -1 144  -1  -1  -1 684  -1]

The problem of finding the Voronoi cell that contains a given location is equivalent to the search for the nearest neighbor in a set of seeds. We can always perform this search with a brute-force algorithm—and this is acceptable in some cases—but in general, there are more elegant and less complex approaches to this problem. The key lies in the concept of k-d trees—a special case of binary space partitioning structures for organizing points, conductive to fast searches.

In the SciPy stack, we have an implementation of k-d trees; the Python class KDTree, in the module scipy.spatial. This implementation is based on ideas published in 1999 by Maneewongvatana and Mount. It is initialized with the location of our input points. Once created, it can be manipulated and queried with the following methods and attributes:

There is a faster implementation of this object created as an extension type in Cython, the cdef class cKDTree. The main difference is in the way the nodes are coded on each case:

Let's use this idea to solve a point location problem, and at the same time revisit the Voronoi diagram from Lake Superior:

In [17]: from scipy.spatial import cKDTree, Voronoi, voronoi_plot_2d
In [18]: vor  = Voronoi(superior['vertices']); 
   ....: tree = cKDTree(superior['vertices'])

First, we query for the previous dataset, of 100 random locations, the seeds that are closest to each of them:

In [19]: tree.query(points)
Out[19]:
(array([ 0.38942726,  0.05020313,  0.06987993,  0.2150344 , 0.16101652,  0.08485664,  0.33217896,  0.07993277,  0.06298875,  0.07428273,  0.1817608 ,  0.04084714, 
         0.0094284 ,  0.03073465,  0.01236209,  0.02395969,  0.17561544,  0.16823951,  0.24555293,  0.01742335,  0.03765772,  0.20490015,  0.00496507]),
 array([  3, 343, 311, 155, 370, 372, 144, 280, 197, 144, 251, 453, 42  233, 232, 371, 280, 311,   0, 307, 507,  49, 474, 370, 114,   5,   1, 372, 285, 150, 361,  84,  43,  98, 418, 482, 155, 144, 371, 113,  91,   3, 453,  91, 311, 412, 155, 156, 251, 251,  22, 179, 394, 189,  49, 405, 453, 506, 407,  36, 308,  33,  81,  46, 301, 144, 280, 409, 197, 407, 516]))

Note the output is a tuple with two numpy.array: the first one indicates the distances of each point to its closest seed (their nearest neighbors), and the second one indicates the index of the corresponding seed.

We can use this idea to represent the Voronoi diagram without a geometric description in terms of vertices, segments, and rays:

In [20]: X = np.linspace( 0.45,  0.50, 256); 
   ....: Y = np.linspace(-0.40, -0.35, 256); 
   ....: canvas = np.meshgrid(X, Y); 
   ....: points = np.c_[canvas[0].ravel(), canvas[1].ravel()]; 
   ....: queries = tree.query(points)[1].reshape(256, 256)
In [21]: ax1 = plt.subplot(121, aspect='equal'); 
   ....: voronoi_plot_2d(vor, ax=ax1); 
   ....: plt.xlim( 0.45,  0.50); 
   ....: plt.ylim(-0.40, -0.35)
Out[21]: (-0.4, -0.35)
In [22]: ax2 = plt.subplot(122, aspect='equal'); 
   ....: plt.gray(); 
   ....: plt.pcolor(X, Y, queries); 
   ....: plt.plot(vor.points[:,0], vor.points[:,1], 'ro'); 
   ....: plt.xlim( 0.45,  0.50); 
   ....: plt.ylim(-0.40, -0.35); 
   ....: plt.show()

This gives the following two different representations of the Voronoi diagram, in a small window somewhere along the North shore of Lake Superior:

A range searching problem tries to determine which objects of an input set intersect with a query object (that we call the range). For example, when given a set of points in the plane, which ones are contained inside a circle of radius r centered at a target location Q? We can solve this sample problem easily with the attribute query_ball_point from a suitable implementation of a k-d tree. We can go even further if the range is an object formed by the union of a sequence of different balls. The same attribute gets the job done, as the following code illustrates:

In [23]: points = np.random.rand(320, 2); 
   ....: range_points = np.random.rand(5, 2); 
   ....: range_radii = 0.1 * np.random.rand(5)
In [24]: tree = cKDTree(points); 
   ....: result = set()
In [25]: for k in range(5):
   ....:     point  = range_points[k]
   ....:     radius = range_radii[k]
   ....:     partial_query = tree.query_ball_point(point, radius)
   ....:     result = result.union(set(partial_query))
   ....:
In [26]: print result
set([130, 3, 166, 231, 40, 266, 2, 269, 120, 53, 24, 281, 26, 284])
In [27]: fig = plt.figure(); 
   ....: plt.axes().set_aspect('equal')
In [28]: for point in points:
   ....:     plt.plot(point[0], point[1], 'ko')
   ....:
In [29]: for k in range(5):
   ....:     point = range_points[k]
   ....:     radius = range_radii[k]
   ....:     circle = plt.Circle(point, radius, fill=False)
   ....:     fig.gca().add_artist(circle)
   ....:
In [30]: plt.show()

This gives the following diagram, where the small dots represent the locations of the search space, and the circles are the range. The query is the set of points located inside of the circles, computed by our algorithm:

Problems in this setting vary from trivial to extremely complicated, depending on the input object types, range types, and query types. An excellent exposition of this subject is the survey paper Geometric Range Searching and its Relatives, published by Pankaj K. Agarwal and Jeff Erickson in 1999, by the American Mathematical Society Press, as part of the Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational geometry.