任意の 2 つの線の間の最も近い/最短の距離を取得する関数を作成したいと考えています (交差しないと仮定します)。点と線の間の最短距離に関する投稿がいくつかあることは知っていますが、2 つの線については見つかりませんでした。
私はいくつかの数学とベクトルの学習サイトに相談し、以下のアルゴリズムを解読することができました. それは答えを与えますが、正しいものではありません。たとえば、次の間の最短距離を見つける場合:
l1 = [(5,6),(5,10)]
l2 = [(0,0),(10,10)]
print _line2line(l1,l2)
...答えは...
5.75223741636
2 本の線のグラフ (1 単位ごとに目盛りが付いた 10x10 フレームを示しています) に見られるように、理論的に言えば、点 (6,5) と (5, 5)。
だから、誰かが私のコードで間違っていることを見つけられるかどうか疑問に思っていますか? （可能であれば、2本の線が最も近い実際のポイントを取得する方法も知りたいです...）
以下のコードに関する注意: L1 と L2 は line1 と line2 を表し、x/y1 と x/y2 はそれぞれ各線の始点と終点です。接尾辞 dx と dy は、デルタまたは x と y を表します。つまり、原点が 0,0 の場合はベクトルです。
def _line2line(line1, line2):
"""
- line1 is a list of two xy tuples
- line2 is a list of two xy tuples
References consulted:
http://mathforum.org/library/drmath/view/51980.html
and http://mathforum.org/library/drmath/view/51926.html
and https://answers.yahoo.com/question/index?qid=20110507163534AAgvfQF
"""
import math
#step1: cross prod the two lines to find common perp vector
(L1x1,L1y1),(L1x2,L1y2) = line1
(L2x1,L2y1),(L2x2,L2y2) = line2
L1dx,L1dy = L1x2-L1x1,L1y2-L1y1
L2dx,L2dy = L2x2-L2x1,L2y2-L2y1
commonperp_dx,commonperp_dy = (L1dy - L2dy, L2dx-L1dx)
#step2: normalized_perp = perp vector / distance of common perp
commonperp_length = math.hypot(commonperp_dx,commonperp_dy)
commonperp_normalized_dx = commonperp_dx/float(commonperp_length)
commonperp_normalized_dy = commonperp_dy/float(commonperp_length)
#step3: length of (pointonline1-pointonline2 dotprod normalized_perp).
# Note: According to the first link above, it's sufficient to
# "Take any point m on line 1 and any point n on line 2."
# Here I chose the startpoint of both lines
shortestvector_dx = (L1x1-L2x1)*commonperp_normalized_dx
shortestvector_dy = (L1y1-L2y1)*commonperp_normalized_dy
mindist = math.hypot(shortestvector_dx,shortestvector_dy)
#return results
result = mindist
return result