Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 ยท Sparse, Spatial and Image Data

Spatial Algorithms

Find nearest neighbors with KDTree, build distance matrices with cdist, compute hulls, Delaunay and Voronoi diagrams, rotate in 3D and cluster hierarchically.

Many problems are really about points in space: which store is closest to this customer, what is the outline of this cloud of GPS fixes, how do I rotate a 3D object by 40 degrees, which measurements belong together. scipy.spatial collects the standard answers. It gives you fast neighbor search, distance computations, computational geometry (hulls and triangulations), 3D rotations, and, via scipy.cluster.hierarchy, a way to group points by distance.

Points are always stored as an array of shape (n_points, n_dimensions): one row per point. If you need a reminder about shapes, see NumPy Refresher for SciPy.

flowchart LR
    P["Points<br/>shape (n, d)"] --> K["KDTree<br/>neighbor queries"]
    P --> D["cdist / pdist<br/>distance matrices"]
    P --> G["ConvexHull, Delaunay,<br/>Voronoi"]
    P --> H["linkage + fcluster<br/>hierarchical clusters"]

One array of points feeds all the tools in this lesson.

Nearest neighbors with KDTree

Finding the closest point by comparing against every point costs O(n) per query. A k-d tree splits the space into boxes once, after which a query only has to look at a few boxes, which is roughly O(log n). Building the tree is the one-time cost, so it pays off when you ask many questions about the same points.

tree.query(x, k=3) returns the distances and indices of the 3 nearest neighbors. tree.query_ball_point(x, r) returns every point within radius r.

Python KDTree queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

query accepts an array of points and answers them all in one call, which is far faster than a Python loop. Use p=1 for Manhattan distance or p=np.inf for Chebyshev distance. For geographic latitude and longitude, convert to 3D unit-sphere coordinates first; a k-d tree measures straight Euclidean distance.

KDTree and cKDTree are now the same fast, C-backed implementation. Old code that imports cKDTree still works, but new code can use KDTree.

Distance matrices with cdist and pdist

Sometimes you want all distances, not just the nearest. cdist(A, B) returns the matrix of distances between every row of A and every row of B. pdist(A) returns distances within one set in a compact condensed form (only the upper triangle, as a flat vector), and squareform converts between the condensed vector and a full symmetric matrix.

Python cdist, pdist and squareform

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A full distance matrix needs nยฒ numbers, so it is fine for a few thousand points and hopeless for a million. Beyond that, use a KDTree and ask only for neighbors you care about (the sparse output of tree.sparse_distance_matrix is another option).

Convex hull, Delaunay and Voronoi

Three classical geometric structures come from the same library (Qhull).

  • The convex hull is the smallest convex shape containing all points: stretch a rubber band around the nails and let go.
  • The Delaunay triangulation connects the points into triangles so that no point lies inside any triangle's circumscribed circle. It avoids long, skinny triangles and is the basis of many meshes.
  • The Voronoi diagram assigns each point the region of space closer to it than to any other point. It is the geometric dual of the Delaunay triangulation.
Python Hull, triangulation and Voronoi

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For ConvexHull in two dimensions the attribute volume is the area and area is the perimeter; in 3D they are volume and surface area. Delaunay.find_simplex is a handy point-location tool and returns -1 for points outside the triangulation. Delaunay triangles are also the basis of linear interpolation of scattered data, a topic you will meet in Multidimensional and Scattered-Data Interpolation.

3D rotations with Rotation

Rotations in 3D are surprisingly tricky. Euler angles depend on conventions and suffer from gimbal lock, and rotation matrices have nine numbers for three degrees of freedom. scipy.spatial.transform.Rotation hides all this behind one object that you can create from any representation and convert to any other.

  • Rotation.from_euler("z", 90, degrees=True) uses a lowercase axis string for extrinsic rotations (about fixed axes) and uppercase for intrinsic ones.
  • r.apply(vectors) rotates one or many vectors.
  • r1 * r2 composes rotations: r2 is applied first, then r1.
  • r.as_matrix(), r.as_quat(), r.as_rotvec() and r.as_euler(...) convert to other forms; r.inv() is the inverse.
Python Composing and converting rotations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Prefer quaternions or rotation objects over raw Euler angles for anything beyond reading a value: you can chain, invert and interpolate them without worrying about axis order. Notice that the * operator reads right to left, just like matrix multiplication.

Hierarchical clustering

Hierarchical clustering starts with every point as its own cluster and repeatedly merges the two closest clusters, recording each merge in a table called the linkage matrix. You then cut the tree at a chosen height or number of clusters.

  • linkage(points, method="ward") builds the tree. "single", "complete", "average" and "ward" define how the distance between two clusters is measured.
  • fcluster(Z, t=3, criterion="maxclust") cuts the tree into at most 3 clusters and returns a label for each point.
  • dendrogram(Z) draws the tree.
Python Clustering three blobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dendrogram shows how far apart the merged groups were: when the last two merges are far taller than all the earlier ones, as here, the data contains three well-separated groups. Ward linkage tends to give compact, similarly sized clusters; single linkage can chain points together into long strings (in the loop above it merges everything into one cluster at height 2.5, because single linkage only looks at the closest pair of points between two clusters, and straggling points of neighboring blobs come within that distance). The same threshold therefore means different things for different methods. Hierarchical clustering needs the distances between all points, so, like pdist, it suits thousands of points, not millions. For the k-means alternative, see Special Functions and Clustering.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the shape convention for a set of points in scipy.spatial?

    Each row is one point and each column one coordinate, so 200 points on a plane have shape (200, 2).
  2. 2. Why build a KDTree instead of calling np.linalg.norm against all points for every query?

    The tree is built once and then answers queries by examining only nearby regions, which is far faster when you ask many questions about the same points.
  3. 3. For a 2D ConvexHull, what does the attribute volume hold?

    Qhull's terms are dimension-generic: in 2D, volume is the enclosed area and area is the perimeter.
  4. 4. In r1 * r2 with two Rotation objects, which rotation is applied to a vector first?

    Composition works like matrix multiplication: r2 acts first, then r1, so (r1 * r2).apply(v) equals r1.apply(r2.apply(v)).
  5. 5. What does fcluster(Z, t=3, criterion='maxclust') return?

    fcluster cuts the linkage tree and returns one integer label per original observation.

Summary

  • Points live in arrays of shape (n_points, n_dimensions).
  • KDTree answers query (k nearest) and query_ball_point (within radius) quickly after a one-time build.
  • cdist and pdist/squareform produce distance matrices in many metrics; they grow quadratically, so use trees for large data.
  • ConvexHull, Delaunay and Voronoi come from Qhull; in 2D, ConvexHull.volume is the area.
  • Rotation converts between matrices, quaternions, rotation vectors and Euler angles, composes with * and interpolates with Slerp.
  • linkage + fcluster + dendrogram perform hierarchical clustering.

Next up: grids of pixels instead of clouds of points, in Image Processing with scipy.ndimage.