YouTip

Spatial data, also known as geometric data, is used to represent information such as the position, shape, size distribution of objects, for example, points on coordinates. SciPy handles spatial data through the scipy.spatial module, such as determining whether a point is within a boundary, calculating the nearest point to a given point, and finding all points within a given distance. ### Triangulation Triangulation in trigonometry and geometry is a method of measuring the distance to a target point by measuring the angle between the target point and the known endpoints of a fixed baseline. Triangulation of a polygon divides the polygon into multiple triangles, and we can use these triangles to calculate the area of the polygon. A well-known fact in topology tells us that: any surface has a triangulation. Assuming there is a triangulation on a surface, we denote the total number of vertices of all triangles as p (shared vertices count as one), the number of edges as a, and the number of triangles as n, then e=p-a+n is the topological invariant of the surface. That is, no matter what triangulation, e always gets the same value. e is called the Euler characteristic. The method for triangulating a series of points is Delaunay() triangulation. ## Example Create triangles from the given points: import numpy as np from scipy.spatial import Delaunay import matplotlib.pyplot as plt points = np.array([ [2,4], [3,4], [3,0], [2,2], [4,1] ]) simplices = Delaunay(points).simplices# Indices of triangle vertices plt.triplot(points[:,0], points[:,1], simplices) plt.scatter(points[:,0], points[:,1], color='r') plt.show() The output is as shown in the figure below: !(#) **Note:** The triangle vertex IDs are stored in the simplices attribute of the triangulation object. ### Convex Hull Convex Hull is a concept in computational geometry (computer graphics). In a real vector space V, for a given set X, the intersection S of all convex sets containing X is called the convex hull of X. The convex hull of X can be constructed using convex combinations of all points (X1, ...Xn) within X. We can use the ConvexHull() method to create a convex hull. ## Example Create a convex hull from the given 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() The output is as shown in the figure below: !(#) ### K-D Tree kd-tree (abbreviation for k-dimensional tree) is a tree data structure used to store points in k