点-多角形包含判定

説明

点が多角形の内部/境界/外部のどこにあるかを判定する．

その点を通る半直線を引き，それが多角形の辺と何回交差するかを数える．一回交差するたびに内外が切り替わる．半直線として x 軸に平行で正の無限大方向に伸びるものを取れば，交差判定は y 座標の比較と外積の符号判定で行える．

上の判定と同時に線上判定を行うことで境界判定も行う．

計算量

O(n)．

ソースコード

#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
enum { OUT, ON, IN };
int contains(const polygon& P, const point& p) {
  bool in = false;
  for (int i = 0; i < P.size(); ++i) {
    point a = curr(P,i) - p, b = next(P,i) - p;
    if (imag(a) > imag(b)) swap(a, b);
    if (imag(a) <= 0 && 0 < imag(b))
      if (cross(a, b) < 0) in = !in;
    if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
  }
  return in ? IN : OUT;
}

Verified

• UVA 109 (SCUD Busters), 6 MS, -- KB