在Python中用两个点找到图中最远的两个点 [英] Finding two most far away points in plot with many points in Python

问题描述

我需要找到距离最远的两个点. 如屏幕截图所示，我有一个包含其他两个数组的数组.一个用于X坐标，一个用于Y坐标.确定数据中最长的线的最佳方法是什么?通过这样说，我需要选择情节中两个最遥远的点.希望你们能提供帮助.以下是一些屏幕快照，可以帮助您解释该问题.

I need to find the two points which are most far away from each other. I have, as the screenshots say, an array containing two other arrays. one for the X and one for the Y coordinates. What's the best way to determine the longest line through the data? by saying this, i need to select the two most far away points in the plot. Hope you guys can help. Below are some screenshots to help explain the problem.

推荐答案

通过观察距离最远的两个点将作为凸包中的顶点出现，可以避免计算所有成对距离.然后，您可以计算较少点之间的成对距离.

You can avoid computing all pairwise distances by observing that the two points which are furthest apart will occur as vertices in the convex hull. You can then compute pairwise distances between fewer points.

例如，在一个单位正方形中有100,000个点均匀分布，在我的实例中，凸包中只有22个点.

For example, with 100,000 points distributed uniformly in a unit square, there are only 22 points in the convex hull in my instance.

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]

如果数据是二维的，则可以计算 时间，其中<​​c1>是点数.通过测量集中，此方法对于许多常见分布的性能会随着尺寸数量的增加而降低

If your data is 2-dimensional, you can compute the convex hull in O(N*log(N)) time where N is the number of points. By concentration of measure, this method deteriorates in performance for many common distributions as the number of dimensions grows.

这篇关于在Python中用两个点找到图中最远的两个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！