我需要找到彼此距离最远的两个点。 正如屏幕截图所示，我有一个包含另外两个数组的数组。一个用于 X 坐标，一个用于 Y 坐标。确定数据中最长线的最佳方法是什么？通过这样说，我需要选择图中最远的两个点。希望大家能帮忙。以下是一些屏幕截图，可帮助解释问题。
您可以通过观察相距最远的两个点将作为凸包中的顶点出现来避免计算所有成对距离。然后，您可以计算更少的点之间的成对距离。
例如，在一个单位正方形中均匀分布 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]
如果您的数据是二维的，您可以compute中的凸包O(N*log(N))时间 地点N是点数。经过测量浓度，随着维数的增加，这种方法对于许多常见分布的性能会下降。