通过观察最远的两个点在凸包中作为顶点出现,可以避免计算所有成对距离。然后,您可以计算更少点之间的成对距离。
例如,在一个单位正方形中有100,000个点均匀分布,在我的实例中,凸包中只有22个点。
import numpy as np
from scipy import spatial
# test points
pts = np.random.rand(100_000, 2)
# two points which are fruthest apart will occur as vertices of the convex hull
candidates = pts[spatial.ConvexHull(pts).vertices]
# get distances between each pair of candidate points
dist_mat = spatial.distance_matrix(candidates, candidates)
# get indices of candidates that are furthest apart
i, j = np.unravel_index(dist_mat.argmax(), dist_mat.shape)
print(candidates[i], candidates[j])
# e.g. [ 1.11251218e-03 5.49583204e-05] [ 0.99989971 0.99924638]
如果数据是二维的,则可以及时计算凸包,O(N*log(N))
其中N
点数是。通过集中精力,随着维数的增加,此方法在许多常见分布中的性能都会下降。