円と直線の交点 計算幾何学

円と直線の交点

円と直線の交点
Feb. 2, 2020, 1:52 p.m.

目次

解説

円の中心座標を$C$、半径を$R$、直線$l$が通る2点を左から$p_1$, $p_2$とおく.
円と直線の交点を$a$、$b$とおく.

交点を求めるには以下3つの情報があれば良い.

  1. 円Cから直線$l$への垂線と直線$l$との交点$p$.
  2. 直線$l$上の単位ベクトル$\vec{e}$.
  3. 線分$ab$の長さ.

1〜3の情報から、交点$p$から$\vec{e}$のプラスマイナスの方向へ長さ$\frac{ab}{2}$だけ進んだ点2つが解となる.

1. 交点$p$を求める

射影の公式を使って求める.

1
2
3
4
Vector2 project(Vector2 p1, Vector2 p2, Vector2 c) {
    Vector2 v = p2 - p1;
    return p1 + v * (v.dot(c - p1) / v.norm());
}

2. 単位ベクトル$\vec{e}$を求める

単位ベクトルはベクトルをその長さで割ると求められる.

1
2
3
Vector2 unitVec(Vector2 v) {
  return v / v.length();
}

3. 線分$ab$の長さを求める

$C$から直線$l$へ垂線を引き$l$との交点を$p$とおく.
この時、点$p$は線分$ab$を2等分する点である.
また、$\angle{Cpb}$は直角三角形である.
線分$ap$と$pb$の長さは三平方の定理より、

$$
ap = pb = \sqrt{R^2 - |\vec{Cp}|^2}
$$

4. 交点を求める

$$
a, b = \vec{p} + \vec{e} \cdot \pm ap
$$

コード全体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
double R;
Vector2 C, p1, p2;

Vector2 project(Vector2 p1, Vector2 p2, Vector2 c) {
    Vector2 v = p2 - p1;
    return p1 + v * (v.dot(c - p1) / v.norm());
}

Vector2 unitVec(Vector2 v) {
  return v / v.length();
}

pair<Vector2, Vector2> crossPoints() {
  Vector2 p = project(p1, p2, C);
  Vector2 e = unitVec(p2 - p1);
  double len = sqrt(R*R - (p - C).norm());
  Vector2 a = p + e * (-len);
  Vector2 b = p + e * len;
  if (fabs(a.x) < EPS) a.x = 0.0;
  if (fabs(a.y) < EPS) a.y = 0.0;
  if (fabs(b.x) < EPS) b.x = 0.0;
  if (fabs(b.y) < EPS) b.y = 0.0;
  if (a < b) return make_pair(a, b);
  return make_pair(b, a);
}