在Python中用许多点找到两个最远点的点

发布时间：2020-12-16 23:10:15 所属栏目：Python 来源：网络整理

导读：我需要找到距离彼此最远的两个点. 正如屏幕截图所示,我有一个包含其他两个数组的数组.一个用于X,一个用于Y坐标.确定数据中最长线的最佳方法是什么？通过这样说,我需要选择情节中最远的两个点.希望你们能帮忙.下面是一些帮助解释问题的截图. 解决方法您可以

我需要找到距离彼此最远的两个点.
正如屏幕截图所示,我有一个包含其他两个数组的数组.一个用于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]

如果数据是二维的,你可以在O(n * log(n))时间compute凸包,其中n是点数.不幸的是,随着维度数量的增加,性能提升消失了.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!