外積 多角形の点内包判定 内積 計算幾何学

多角形の点内包判定

多角形の点内包判定
Feb. 2, 2020, 1:52 p.m.

目次

用途

多角形の頂点の座標と点が与えられて、その点が多角形に内包されるか否か、あるいは多角形の辺上に位置するかを判定するアルゴリズム.

アルゴリズム

多角形を$P$、点を$p$、点から辺$e$の始点終点へのベクトルを、$y$座標が小さい順に$\vec{a}$、$\vec{b}$とおく.

辺上に位置することの判定

多角形の辺上にあるのは以下の条件を満たす時である.
つまり、多角形の辺のうち、$\vec{a}$と$\vec{b}$が正反対を向くような辺$e$が存在する.

$$
\exists e {e \in P, \vec{a} \times \vec{b} = 0, \vec{a} \cdot \vec{b} < 0}
$$

内包判定

内包されているかどうかは点から右に半直線を出し、何回多角形の辺と交差するかで判定できる.
奇数回なら内包、偶数回なら内包されない.

半直線と辺が交差する判定は、以下2点を両方満たすかどうかでわかる.

  1. 辺の始点終点がそれぞれ半直線の上部と下部に分かれて位置する.
  2. 円と半直線の交点が$p$より右側にある.

1は単純にベクトルのy座標でわかる.
2は$\vec{b}$が$\vec{a}$の反時計回りの位置にあるかどうかで分かる.
反時計回りなら外積が正となる.

$$
|{e|e \in P, a.y \leq 0, b.y \geq 0, \vec{a} \times \vec{b}}| \equiv 1 (\mod 2)
$$

コード

N角形

返り値の仕様

  • 2: 内包
  • 1: 辺上
  • 0: 内包ではない
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Int contains(Vector2 polygon[], int N, Vector2 &point) {
  bool in = false;
  loop(n,0,N) {
    Vector2 a = polygon[n] - point;
    Vector2 b = polygon[(n+1) % N] - point;
    if (fabs(a.cross(b)) < EPS && a.dot(b) < EPS) return 1;
    if (a.y > b.y) swap(a, b);
    if (a.y < EPS && b.y > EPS && a.cross(b) > EPS) in = !in;
  }

  return in ? 2 : 0;
}