線分の交点 外積 geometry

線分の交点

線分の交点
Feb. 2, 2020, 1:51 p.m.

目次

解説

2つの線分の交点を求める.

線分を$S1(p_0, p_1)$, $S2(p_2, p_3)$とおく.
S1を底辺とみなすと、$p_2$と$p_3$をそれぞれ頂点として三角形が2つ出来る.
これらの高さをそれぞれ$h_1$, $h_2$とおく.

高さは、三角形の面積と底辺の長さで求まる.
底辺の長さは$|\vec{p_0 p_1}|$.
面積は外積の絶対値の二分の一なので、$\vec{p_0 p_1} \cross \vec{p_0 p_2}$.

さて、交点を$p$とおくと、求める$p$は始点$p_2$から長さ$|\vec{p_2 p}|$だけ$p_3$に向けて進んだ位置にある.
その長さが分かれば解が求まる.
長さは以下の比を満たす.

$$
|\vec{p_2 p}| : |\vec{p_2 p_3}| = h_1 : h_1 + h_2
$$

求める長さについて変形して、

$$
l = |\vec{p_2 p}| = \frac{|\vec{p_2 p_3}| \times h_1}{h_1 + h_2}
$$

よって、

$$
\vec{p_2 p} = \vec{p_2 p_3} \times l
$$

求めるのはベクトル$\vec{p_2 p}$ではなく点$p$なので、始点を加えてやって

$$
p = p_2 + \vec{p_2 p}
$$

最後に$p.x, p.y$が0の誤差範囲内であれば0と出力することを忘れずに.

コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Vector2 crossPoint(Vector2 &p0, Vector2 &p1, Vector2 &p2, Vector2 &p3) {
  Vector2 baseSeg = p1 - p0;
  Vector2 crossSeg = p3 - p2;
  double h2 = fabs(baseSeg.cross(p2 - p0)) / (baseSeg.length() * 2);
  double h3 = fabs(baseSeg.cross(p3 - p0)) / (baseSeg.length() * 2);
  Vector2 p = p2 + crossSeg * h2 / (h2 + h3);
  if (fabs(p.x) < EPS) p.x = 0.0;
  if (fabs(p.y) < EPS) p.y = 0.0;
  return p;
}