特定の点がポリゴン（多角形）の内側にあるかどうかを判定するアルゴリズム

問題の概要

この問題では、1つの多角形（ポリゴン）と1つの点Pが与えられます。求めるのは、点Pが多角形の内側にあるのか、それとも外側にあるのかという判定です。

アプローチ：レイキャスティング法

この問題を解くために、点Pから無限遠まで伸びる半直線を引くことを考えます。この直線は水平方向、すなわちx軸に平行なものとします。

次に、この半直線が多角形の辺と何回交差するかを数えます。交差回数が奇数であれば点は多角形の内側にあり、偶数であれば外側にあると判定できます。なお、点Pが多角形のいずれかの辺上に乗っている特殊なケースについては、別途チェックを行い「内側」として扱います。

この手法は「レイキャスティング法（Ray Casting）」または「交差数アルゴリズム」と呼ばれ、GISやコンピュータグラフィックスの分野でも広く利用されている基本的な手法です。

入力と出力

入力:
多角形の頂点 {(0, 0), (10, 0), (10, 10), (0, 10)}、判定する点 P (5, 3)

出力:
Point is inside.

アルゴリズム

checkInside(Poly, n, p)

入力: 多角形の頂点の配列、頂点の個数n、判定対象の点p

出力: pが多角形の内側にあればtrue、そうでなければfalse

開始
    もし n < 3 ならば
        false を返す（頂点が3未満では多角形を構成できない）
    点pから無限遠へ伸びる直線 exLine を作成する（傾きは0°、x軸に平行）
    count := 0、i := 0 とする
    繰り返し:
        poly[i] から poly[(i+1) mod n] への線分 side を作成する
        もし side と exLine が交差するならば:
            もし side と exLine が同一直線上にあるならば:
                もし点pが side 上にあるならば true を返す
                そうでなければ false を返す
            count := count + 1
        i := (i + 1) mod n
    （i が 0 に戻るまで繰り返す）
    count が奇数であれば true を返す
終了

C++による実装例

以下は、上記のアルゴリズムをC++で実装した例です。コードを理解するうえで重要な補助関数は次の3つです。

• onLine: 点が線分上に存在するかどうかを判定します。
• direction: 3点の位置関係をもとに、進行方向が「時計回り」「反時計回り」「同一直線上」のいずれであるかを返します。
• isIntersect: 2つの線分が交差しているかどうかを判定します。

#include<iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

// 点pが線分l1上にあるかどうかを判定する
bool onLine(line l1, Point p) {
    if(p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
       (p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y)))
        return true;
    return false;
}

// 3点a, b, cの位置関係を求める（0: 同一直線上, 1: 時計回り, 2: 反時計回り）
int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;    // 同一直線上（コリニア）
    else if(val < 0)
        return 2;    // 反時計回り
    return 1;        // 時計回り
}

// 2つの線分l1とl2が交差しているかどうかを判定する
bool isIntersect(line l1, line l2) {
    // 各線分に対して、相手の端点がどちら側にあるかを求める
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);

    if(dir1 != dir2 && dir3 != dir4)
        return true;    // 交差している
    if(dir1==0 && onLine(l1, l2.p1))    // l2の端点がl1上にある場合
        return true;
    if(dir2==0 && onLine(l1, l2.p2))    // l2のもう一方の端点がl1上にある場合
        return true;
    if(dir3==0 && onLine(l2, l1.p1))    // l1の端点がl2上にある場合
        return true;
    if(dir4==0 && onLine(l2, l1.p2))    // l1のもう一方の端点がl2上にある場合
        return true;
    return false;
}

// 点pが多角形poly（頂点数n）の内側にあるかどうかを判定する
bool checkInside(Point poly[], int n, Point p) {
    if(n < 3)
        return false;                 // 頂点が3未満なら多角形ではない
    line exline = {p, {9999, p.y}};   // 点pと同じy座標の無限遠の点への半直線
    int count = 0;
    int i = 0;
    do {
        line side = {poly[i], poly[(i+1)%n]};   // 隣接する2頂点から辺を作る
        if(isIntersect(side, exline)) {         // 辺が半直線と交差する場合
            if(direction(side.p1, p, side.p2) == 0)
                return onLine(side, p);         // 点が辺上にあるかを確認
            count++;
        }
        i = (i+1)%n;
    } while(i != 0);
    return count&1;                   // 交差回数が奇数なら内側
}

int main() {
    Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    Point p = {5, 3};
    int n = 4;

    if(checkInside(polygon, n, p))
        cout << "Point is inside.";
    else
        cout << "Point is outside.";
}

実行結果

Point is inside.

計算量

このアルゴリズムは、多角形のすべての辺を一度ずつ調べるため、時間計算量はO(n)（nは頂点の数）です。また、追加の記憶領域をほとんど必要としないため、空間計算量はO(1)となります。頂点数が多い多角形に対しても効率的に動作するのが特徴です。