Нахождение двух наиболее удаленных точек на графике с множеством точек в Python

Question

Мне нужно найти две точки, которые находятся наиболее далеко друг от друга.У меня, как говорят скриншоты, есть массив, содержащий два других массива.один для X и один для Y-координат.Каков наилучший способ определить самую длинную линию по данным?сказав это, мне нужно выбрать две самые дальние точки на графике.Надеюсь, вы, ребята, можете помочь.Ниже приведены некоторые скриншоты, чтобы помочь объяснить проблему.

Answer 1

Вы можете избежать вычисления парных расстояний, наблюдая, что две точки, которые находятся дальше друг от друга, будут иметь вид вершин в выпуклой оболочке.Затем вы можете вычислить попарные расстояния между меньшим количеством точек.

Например, с 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 - этоколичество баллов.При концентрации меры этот метод ухудшает производительность для многих распространенных распределений по мере увеличения числа измерений.