Convex Hull

A convex hull is the smallest polygon that encloses all the given points.

Use the ConvexHull() method to construct a convex hull.

Example

Generate a convex hull for the following points:

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt

points = np.array([
  [2, 4],
  [3, 4],
  [3, 0],
  [2, 2],
  [4, 1],
  [1, 2],
  [5, 0],
  [3, 1],
  [1, 2],
  [0, 2]
])

hull = ConvexHull(points)
hull_points = hull.simplices

plt.scatter(points[:,0], points[:,1])
for simplex in hull_points:
  plt.plot(points[simplex,0], points[simplex,1], ‘k-‘)

plt.show()

Result:

KDTrees

KDTrees are data structures optimized for nearest neighbor queries. For example, in a set of points, KDTrees allow efficient retrieval of the nearest points to a given point.

The KDTree() method returns a KDTree object, while the query() method provides the distance to the nearest neighbor and the location of the neighbors.

Example

Determine the nearest neighbor to the point (1, 1).

from scipy.spatial import KDTree

points = [(1, –1), (2, 3), (-2, 3), (2, –3)]

kdtree = KDTree(points)

res = kdtree.query((1, 1))

print(res)

Result:

(2.0, 0)