回答編集履歴
1
追記
test
CHANGED
|
@@ -1,2 +1,46 @@
|
|
|
1
1
|
詳細未検証ですが[Max Distance between 2 points in a data set and identifying the points](https://stackoverflow.com/a/60955825)の回答を参照の上、利用できるか検討ください。
|
|
2
2
|
上記の回答では3D座標が対象ですが、2Dでも同様にできるかと思います。
|
|
3
|
+
|
|
4
|
+
## 追記
|
|
5
|
+
検証してみました。
|
|
6
|
+
求めたい２点は、その性質上、対象となる点群の凸包を構成する点のはずです。
|
|
7
|
+
そこで`scipy.spatial`で凸包の点群＝距離を計算すべき点を抽出します。
|
|
8
|
+
これらの数は元の数よりも大幅に少ないので計算量をかなり減らせ、提示の条件でも一瞬で求まりました。
|
|
9
|
+
参考：[PythonでConvex-Hull(凸包)を用いたバウンディングボックスを求める](https://betashort-lab.com/%E3%83%87%E3%83%BC%E3%82%BF%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9/convex-hull%E3%82%92%E7%94%A8%E3%81%84%E3%81%9Fboundingbox%E3%81%AE%E6%B1%82%E3%82%81%E6%96%B9/)
|
|
10
|
+
```Python
|
|
11
|
+
import numpy as np
|
|
12
|
+
from scipy.spatial import ConvexHull
|
|
13
|
+
from scipy.spatial.distance import cdist
|
|
14
|
+
|
|
15
|
+
# テストデータ
|
|
16
|
+
np.random.seed(110)
|
|
17
|
+
N = 2*10**5
|
|
18
|
+
points = np.random.rand(N, 2)
|
|
19
|
+
points = points * (2*10**5) - 10**5
|
|
20
|
+
print(points.shape) # (200000, 2)
|
|
21
|
+
|
|
22
|
+
# Convex-Hull(凸包)を構成する点群を抽出する
|
|
23
|
+
hull = ConvexHull(points)
|
|
24
|
+
hullpoints = points[hull.vertices,:]
|
|
25
|
+
print(hullpoints.shape) # (26, 2)
|
|
26
|
+
|
|
27
|
+
# 上記の点群の各距離を求める
|
|
28
|
+
hdist = cdist(hullpoints, hullpoints, metric='euclidean')
|
|
29
|
+
print(hdist.shape) # (26, 26)
|
|
30
|
+
|
|
31
|
+
# 最大距離をとる２点の位置を得る
|
|
32
|
+
bestpair = np.unravel_index(hdist.argmax(), hdist.shape)
|
|
33
|
+
print(bestpair) # (6, 17)
|
|
34
|
+
|
|
35
|
+
# 点の位置
|
|
36
|
+
best_points = np.array([hullpoints[bestpair[0]], hullpoints[bestpair[1]]])
|
|
37
|
+
print( best_points)
|
|
38
|
+
#[[-99966.6622684 99769.28800939]
|
|
39
|
+
# [ 99704.49893665 -99985.9459651 ]]
|
|
40
|
+
|
|
41
|
+
# 最大距離
|
|
42
|
+
best_dist = cdist(best_points, best_points, metric='euclidean')
|
|
43
|
+
print(best_dist[0][1]) # 282437.11887281504
|
|
44
|
+
```
|
|
45
|
+
|
|
46
|
+
|