Python3で座標(x,y)がリスト形式で与えられたとき、２点間の距離で最長のものを求めたい。

Question

リスト形式でN個の座標[x,y]が与えられたとき、すべての２点間の距離の中で最長になるユークリッド距離を求めるため、以下のプログラムを書いてみました。

出力は最長距離の２乗になっています。

このプログラムではnumpyをつかって求めていますが、他に計算時間を短縮できるような良いプログラムがあればご教授いただけないでしょうか。

よろしくお願い致します。

<制約>
座標x,yは、-10 ** 5<=x,y<=10 ** 5 の範囲
与えられる座標の数 N は, 1<=N<=2*10**5 の範囲

import numpy as np

N = int(input())
nodes = np.array([list(map(int,input().split())) for _ in range(N)])

longest = 0

nodes_diff = np.expand_dims(nodes,axis=0) - np.expand_dims(nodes,axis=1)
nodes_diff = np.reshape(nodes_diff,(-1,2))
for a,b in nodes_diff:
    distance = a**2 + b**2
    if dist > longest:
        longest = distance

print(longest)

Answer 1

詳細未検証ですがMax Distance between 2 points in a data set and identifying the pointsの回答を参照の上、利用できるか検討ください。
上記の回答では3D座標が対象ですが、2Dでも同様にできるかと思います。

追記

検証してみました。
求めたい２点は、その性質上、対象となる点群の凸包を構成する点のはずです。
そこでscipy.spatialで凸包の点群＝距離を計算すべき点を抽出します。
これらの数は元の数よりも大幅に少ないので計算量をかなり減らせ、提示の条件でも一瞬で求まりました。
参考：PythonでConvex-Hull(凸包)を用いたバウンディングボックスを求める

import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.distance import cdist

# テストデータ
np.random.seed(110)
N = 2*10**5
points = np.random.rand(N, 2)
points = points * (2*10**5) - 10**5
print(points.shape) # (200000, 2)

# Convex-Hull(凸包)を構成する点群を抽出する
hull = ConvexHull(points)
hullpoints = points[hull.vertices,:]
print(hullpoints.shape) # (26, 2)

# 上記の点群の各距離を求める
hdist = cdist(hullpoints, hullpoints, metric='euclidean')
print(hdist.shape) #  (26, 26)

# 最大距離をとる２点の位置を得る
bestpair = np.unravel_index(hdist.argmax(), hdist.shape)
print(bestpair) # (6, 17)

# 点の位置
best_points = np.array([hullpoints[bestpair[0]], hullpoints[bestpair[1]]])
print( best_points)
#[[-99966.6622684   99769.28800939]
# [ 99704.49893665 -99985.9459651 ]]

# 最大距離
best_dist = cdist(best_points, best_points, metric='euclidean')
print(best_dist[0][1]) # 282437.11887281504

Comments

[tajama3]

回答ありがとうございます。

凸包について無知だったので調べてみると、面白いものですね。
勉強になりました。

Answer 2

計算時間を短縮できるかは未確認ですが、
Pythonでxy座標上の2点間の距離をforループを使わずに計算する方法
の「degree_distance」の最大値を計算すれば求まると思います

出力は最長距離の２乗

でよければnp.sqrt()は要らなくなります

　
ただし、

与えられる座標の数 N は,1<=N<=2*10**5 の範囲

の最大の場合は、「degree_distance」の要素数は
(2*10**5)**2=40000000000個
になり、必要なメモリー量は(もちろん変数の型によりますが)かなり大きくなります

さらに、「all_diffs」の要素数は「degree_distance」より多いし、計算過程で要素数がそれらと同じくらいの配列が一時的に作られると思うので、トータルで必要なメモリー量は相当なものになると思います

なので、この方法は座標数が多い場合はコンピュータの実メモリー量が多くないと計算できません
多少メモリーが足りなくても仮想記憶で計算できるかもしれませんが、その場合は計算が遅くなります