二点P1、P2 を通る 直線L があり、また他に二点 A、B があるとする。

A と B が直線の同一側、あるいは、反対側にあるかどうかの判定方法。

各点の座標: P(x1, y1)、 P2(x2, y2)、 A(xA, yA)、 B(xB, yB) とする。

P1、P2を通る直線Lの方程式は

   (y-y1) / (x-x1) = (y2-y1) / (x2-x1)

であり、分母を払うと、

   (x2-x1) * (y-y1) + (y2-y1) * (x1-x) = 0

となる。x と y に、A点とB点をそれぞれ代入し、左辺の値だけを計算する。

   SA = (x2-x1) * (yA-y1) + (y2-y1) * (x1xA)
   SB = (x2-x1) * (yB-y1) + (y2-y1) * (x1xB)

得られた SAとSBが違う符号であれば、直線の反対側にあり、同符号であれば、同一側にある。

         SA * SB &lt 0 ⇔ 反対側
         SA * SB &gt 0 ⇔ 同一側

直線が水平であろうと、垂直でろうと、気にする必要は全くない。なお、SA または SB は値がゼロの時には、その点が直線上にあることになる。

本判定法は整数同士の減算と乗算だけでできるので、誤差はなく、高速である。

Comments are closed.

Post Navigation