The convex hull of a set of points, is the smallest convex polygon for which each point in the set is either on the boundary of the polygon or in its interior.
We can visualize what the convex hull looks like by imagining that the points are nails sticking out of the plane. Take an elastic rubber band, stretch it around the nails and let it go. It will snap around the nails and assume a shape that minimizes its length. The area enclosed by the rubber band is called the convex hull of the points. This leads to an alternative definition of the convex hull of a finite set of points in the plane: it is the unique convex polygon whose vertices are points from and which contains all points.
Jarvis’s march computes the convex hull of a set Q of points by a technique also known as the gift wrapping algorithm. The algorithm was named after R. A. Jarvis, who published it in 1973.
The algorithm simulates wrapping a piece of paper around the set of points. We start by taping the end of the paper to the lowest point in the set, that is, the point with the lowest Y-coordinate, picking the leftmost such point in case of a tie. We know that this point must be a vertex of the convex hull. We pull the paper to the right to make it wrapping "tight" and then we pull it higher until it touches a point. This point must also be a vertex of the convex hull. Keeping the paper "tight", we continue in this way around the set of vertices until we come back to our original starting point.
The algoirhtm has an $O(n * h)$ asymptotic complexity, where $n$ is the number of points and $h$ is the number of points on the convex hull.
Given line (A, B) and point M, check whether M is left or right from the line, more precisely whether A -> B -> M is a closckwise or counter-clockwise turn?
$$det := (Bx - Ax) * (My - Ay) - (By - Ay) * (Mx - Ax)$$Graham’s scan solves the convex-hull problem by maintaining a stack of candidate points. It pushes each point of the input set onto the stack one time, and it eventually pops from the stack each point that is not a vertex of the convex hull. When the algorithm terminates, the stack contains exactly the vertices of the convex hull, in counter-clockwise order of their appearance on the boundary. The algorithm is named after Ronald Graham, who published the original version in 1972.
The algorithm consists of 3 steps:
The algorithm has an $O(n * log(n)$ asymptotic complexity. Thus, this algorithm is not output-sensitive (compare to Jarvis's march).
The Quickhull method uses the divide and conquer approach similar to that of Quicksort, from which its name derives. The original algorithm was described by Scott Greenfield in 1990. The algorithm was later extended to work in n-dimensional space.
The algorithm contains the following steps:
The asymptotic complexity of the algorithm is $O(n * log(r))$, where $r$ is the number of processed points.
Chan's algorithm is an optimal output-sensitive algorithm to compute the convex hull. It was named after Timothy M. Chan, who published the algorithm in 1996.
The algorithm combines Graham's scan (or other algorithm with $O(n * log(n))$ complexity) with Jarvis's march ($O(n*h)$), in order to obtain an optimal $O(n * log(h))$ complexity, where $n$ is the number of points and $h$ is the number of vertices of the output (the convex hull).
Read the hungary_cities.shp
shapefile located in the data
folder.
This dataset contains both scalar and spatial data of the Hungarian cities, and should be familiar from Chapter 15.
import geopandas as gpd
from scipy.spatial import ConvexHull
cities_gdf = gpd.read_file('../data/hungary_cities.shp')
display(cities_gdf)
Shapely can compute the convex hull of any geometry through the convex_hull
attribute.
The geometry
column of the GeoDataFrame contains Shapely points (see Chapter 11), but we need to create a MultiPoint of all cities to calculate their aggregated concex hull.
from shapely import geometry
multipoint = geometry.MultiPoint(cities_gdf.geometry)
hull = multipoint.convex_hull
print(hull)
Plot figure:
import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize=[15, 10])
# Add all points to plot
for point in cities_gdf.geometry:
plt.plot(point.x, point.y, color='black', marker='o', markersize=1)
# Fetch the list of X and Y coordinates of the convex hull
line_x, line_y = hull.exterior.xy
# Plot linestring
plt.plot(line_x, line_y, color='red')
# Display plot
plt.show()
As an alternative approach, we can use SciPy to cimpute the convex hull.
SciPy (pronounced "Sigh Pie") is library used for scientific computing and technical computing for mathematics, science, and engineering. SciPy is built on top of NumPy, Matplotlib and Pandas and are tightly integrated with them. It is one of the most widely used Python package in the scientific community.
If you have Anaconda installed, then scipy
was already installed together with it.
If you have a standalone Python3 and Jupyter Notebook installation, open a command prompt / terminal and type in:
pip3 install scipy
SciPy consists of sub-packages for various scientific areas. For us the spatial
package is in focus, which contains spatial algorithms, like the QuickHull or the KdTree (see Chapter 16).
import scipy.spatial
Fetch points for cities:
points = [(geom.x, geom.y) for geom in cities_gdf.geometry]
print("Number of points: {0}".format(len(points)))
Calculate convex hull:
hull = ConvexHull(points)
print("Number of vertices on hull: {0}".format(len(hull.vertices)))
print("Hull vertices: {0}".format(hull.vertices))
Plot figure:
import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize=[15, 10])
# Add all points to plot
for point in points:
plt.plot(point[0], point[1], color='black', marker='o', markersize=1)
# Calculate convex hull linestring
line_x = [points[idx][0] for idx in hull.vertices]
line_y = [points[idx][1] for idx in hull.vertices]
# Add first point of hull to the end, so the linestring will be closed.
line_x.append(points[hull.vertices[0]][0])
line_y.append(points[hull.vertices[0]][1])
# Plot linestring
plt.plot(line_x, line_y, color='red')
# Display plot
plt.show()