本日数時間、線分・直線間の距離を求める問題にチャレンジしてみたけど、結果は散々だった。自分の考えを一度整理しないとね。

ACM問題はこれ、#10709 Intersection is Not that Easy。線分や直線間の距離を求める問題なので、中学校程度の数学を勉強したひとなら、誰でも簡単に計算できるはずだが、私にはまだ解けない。

混乱を避けるため、用語についてまずその定義をはっきりしておこう。

線分 (Line Segment) とは、XY平面上の両点を結む線のこと。両端点の間にしか存在しない。なお、両端点は異なるもの(同一点でないという意味)でないといけない。

直線 (Line) とは、XY平面上の両点を通る線のこと。直線上、端点となるものは存在せず、平面上無限に両側に伸びていく。なお、直線の通る両点は異なるものでないといけない。

線分間の距離、または、直線間の距離、または、直線・線分間の距離とは、 線分(または直線)上の任意の点から、もう片方の線分(または直線)上の任意の点までの直線距離のなかで、もっとも値の小さいもの。

The distance between 2 lines (or line-segments) is the minimal value of distance between any 2 points, p1 and p2, where p1 ranges over all points in the first line (or line-segment), and p2 ranges over all points in the second line (or line-segment).

ちなみに書くと、直線間の距離は2次元平面においてはあまり意味のないものかもしれない。なぜなら、2直線が平行していなければ、必ず交差するので、両平行直線のケース以外には、2直線間の距離は常にゼロだからだ。

しかし、線分のことが出てくると、平面においても、線分間の距離が現実的になってくる。というよりも、現実の世界ではここでいう直線というものは存在しないので、すべては線分と考えるほうがむしろ正しいだろう。

さて、自分もだいぶ混乱してたので、場合分けして、それぞれの距離を整理していく。

1.両直線間の距離

両直線が平行していなければ、必ず交差するので、距離はゼロになる。両直線の平行条件とは、つぎの通り。(点の座標は図の通り)。

(式1)  (y2-y1)*(x4-x3) = (y4-y3)*(x2-x1)   (両直線が平行である必要十分条件)

計算メモ⇒ 座標値が整数の場合には、計算誤差は一切発生しない。ただし、整数同士の乗算になるので、計算結果のオーバーフローには注意すべし。座標値が32ビット整数の場合では、64ビット整数変数(Gnu Cでは long long int)を使っても危険性あり。

さて、両直線が平行していれば、点(x1, y1) から相手直線に垂線を下ろすことができる。点(x1, y1) と垂線の足 (x, y) との距離が平行直線間の距離になるので、平行直線間の距離はつぎの計算式で求められる。(^2 は2乗の意。sqrt はルート(平方根)計算。)

(式2)  Us = (x1-x3)*(x4-x3)+(y1-y3)*(y4-y3)
(式3)  Ub = (x4-x3)^2+(y4-y3)^2

(式4)  x = x3 + (x4-x3) * Us/Ub
(式5)  y = y3 + (y4-y3) * Us/Ub

(式6)  距離 dist = sqrt((x1-x)^2 + (y1-y)^2)

計算メモ⇒ 式2 において、Us の値が0であれば、式4・式5では、x = x3, y = y3 になる。また、Us = Ubであれば、x = x4, y = y4 になる。
 計算誤差のことを検討すると、式4と式5では除算が入って来るので、左辺の x と y は、一般的に整数ではなくなり、式6は誤差が伴うものになり、注意すべし。なお、直線という定義に満たすものであれば、式3がゼロになることはありえない、安心して式4と式5が使えるだろう。

では、最後に擬似コードを使って、まとめておこう。

 if 式1が偽 then
   distance = 0    /* 両直線は平行せず */
 else
   distance = 式6  /* 両直線は平行 */
 end.

2.線分間の距離
 とてもややしくなり、数個の数式で終わる話しではない。

2.1 両線分が交差するケース

ここでいう交差とは、向きの異なる両線分が、両端点の間(両端点を含まない)のところで交差することをいう。線分は一部または全部が重なることや、端点がもう片方の線分上にあるようなケースは含まれない。

両線分が交差する場合は、両線分間の距離がゼロになる。両線分が交差する条件とは以下の通り。

両線分交差の必要十分条件 =式11
(式7)   t1 = (y1-y3)*(x3-x4)-(x1-x3)*(y3-y4)
(式8)   t2 = (y2-y3)*(x3-x4)-(x2-x3)*(y3-y4)
(式9)   t3 = (y3-y1)*(x1-x2)-(x3-x1)*(y1-y2)
(式10)   t4 = (y4-y1)*(x1-x2)-(x4-x1)*(y1-y2)
(式11)   t1*t2 < 0 かつ t3*t4 < 0

計算メモ⇒ 座標値が整数であれば、計算誤差は一切発生しない。しかし、計算結果のオーバーフローに注意すべし。

2.2 両線分が互いに重なったり、タッチするケース

基本的には、式7~式9の計算結果のいずれかがゼロになることが必要だが、昔に書いた記事(点が線分上にあるかどうかの判定法)で正確に判定してくれる。

つまり、次の流れで判定を行う。
  1.点(x1, y1) が線分(x3, y3)-(x4, y4) 上にあるかどうかを判定する。
    線分上にあると判定すれば、6へ。
  2.点(x2, y2) が線分(x3, y3)-(x4, y4) 上にあるかどうかを判定する。
    線分上にあると判定すれば、6へ。
  3.点(x3, y3) が線分(x1, y1)-(x2, y2) 上にあるかどうかを判定する。
    線分上にあると判定すれば、6へ。
  4.点(x4, y4) が線分(x1, y1)-(x2, y2) 上にあるかどうかを判定する。
    線分上にあると判定すれば、6へ。
  5.本ケース(両線分が互いに重なったり、タッチするケース)に相当しないと判定し、7へ。
  6.本ケースに相当すると判定。7へ。
  7.判定終了。

両線分が互いに重なったり、タッチする本ケースでは、両線分間の距離はゼロである。

2.3 両線分が離れているケース
 さらに場合わけが必要かな。苦しい。。。

2.3.1 垂線の足が線分上に存在するケース
 線分の両端点のどれかが、もう片方の線分に垂線を下ろしたとき、その交点(垂線の足)が相手線分上にあるケース。

図にある青い線は垂線のこと。点線で描かれた垂線はその足が相手線分の外側になってしまうので、最短距離の計算には使えない。

垂線の足4本すべてが相手線分の外側にあるケースはつぎの 2.3.2 で考える。

左側に図示したケースのように、2端点ペア各々の距離よりも、点(x1, y1)と垂線の足(x, y) との距離のほうが短いので、垂線の長さが線分間の距離になる。しかし、右側ケースのように、必ずしも垂線の長さが最短ではない!

ということで、本ケースでは、線分間の距離とは以下の値のなかの最小値である。

 垂線の長さ。垂線の足が相手線分上にある場合はすべて算出しないといけない。最大4本。
 端点間、つまり、(x1,y1)と(x3,y3)ペア、(x2,y2)と(x3,y3)ペア、(x1,y1)と(x4,y4) ペア、(x2, y2)と(x4,y4)ペアの4ペア、の距離。

垂線の足が相手線分上にあるかどうかの判定は、上記の式2と式3を利用すればできる。
つまり、
       0≦Us≦Ub      ⇔  垂線の足が線分上にある
   Us < 0 または Us > Ub ⇔  垂線の足が線分の外側にある

また、点(x1,y2)から垂線の足 (x, y) までのの距離は上記の式6で計算できる。

2.3.2 垂線の足が線分の外側に存在するケース
 線分の両端点のどれもが、もう片方の線分に垂線を下ろしたとき、その交点(垂線の足)が相手線分の外側にあるケース。

本ケースでは、線分間の距離とは端点間(4ペア、以下)の距離のなかからの最小値である。

 端点間の距離、つまり、(x1,y1)と(x3,y3)ペア、(x2,y2)と(x3,y3)ペア、(x1,y1)と(x4, y4)ペア、(x2,y2)と(x4,y4)ペアの4ペア間の距離。

3.直線と線分間の距離
 上の2を理解しておけば、直線と線分との間の距離は問題なく計算できるはず。つまり、線分と直線とは交差するかしないか、線分の両端点からの垂線の長さはどうかで距離が判る。詳しい説明は省略していいだろう。

最後に、C言語ソースプログラムを載せておく。ACM問題を解答するものだが、重要な部分はそのまま利用できるだろう。

p10709.c

○ ○ ○

上の文章を書いている内に、自分がどこで過ちを犯したのか、気づいたので、プログラムのほうはすんなり書けた。文章に纏めることが、私にとって最善の整理法なのかもしれないね。

Comments are closed.

Post Navigation