Pythonで点がポリゴンの内側または境界上にあるかどうかを判定するプログラム

問題の概要

直交座標系の点のリスト [(x1, y1), (x2, y2), ..., (xn, yn)] が1つのポリゴン(多角形)を表しているとします。ここに、判定対象となる点 (x, y) が与えられたとき、その点がこのポリゴンの内側、あるいは境界上に存在するかどうかを判定するのが本記事のテーマです。

例として、次のような入力を考えてみましょう。

points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)

この場合、点 (3, 1) はポリゴンの内部にあるため、出力は True となります。

解決のアプローチ

この問題は、よく知られた「レイキャスティング法(偶奇ルール)」と呼ばれるアルゴリズムで解くことができます。考え方としては、判定したい点から水平方向に半直線を伸ばし、それがポリゴンの辺と何回交差するかを数えます。交差回数が奇数であれば点は内側、偶数であれば外側と判断できます。

具体的な手順は以下の通りです。

• ans := False で初期化する
• i を 0 から「ポリゴンの頂点数 - 1」まで繰り返す:
  • (x0, y0) := polygon[i](現在の辺の始点)
  • (x1, y1) := polygon[(i + 1) mod 頂点数](現在の辺の終点)
  • pt[1] が min(y0, y1) より大きく max(y0, y1) 以下の範囲にない場合は、次の反復へスキップ
  • pt[0] < min(x0, x1) の場合も、次の反復へスキップ
  • cur_x := x0(x0 と x1 が等しい場合)、そうでなければ x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)(辺と水平線の交点の x 座標)
  • ans := ans XOR(pt[0] > cur_x が真なら 1、偽なら 0)
• 最後に ans を返す

ポイントは、各辺について「点の高さ(y座標)がその辺のy範囲に含まれているか」を先に確認し、該当する辺だけについて交点のx座標を計算して左右関係を判定するところです。XOR を使うことで、交差のたびに内外の状態が反転し、最終的に内外の判定が得られます。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, polygon, pt):
        ans = False
        for i in range(len(polygon)):
            x0, y0 = polygon[i]
            x1, y1 = polygon[(i + 1) % len(polygon)]
            if not min(y0, y1) < pt[1] <= max(y0, y1):
                continue
            if pt[0] < min(x0, x1):
                continue
            cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
            ans ^= pt[0] > cur_x
        return ans

ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

入力

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

出力

True

まとめ

このアルゴリズムの計算量は O(n)(n はポリゴンの頂点数)であり、凸多角形・凹多角形のどちらにも対応できる汎用的な手法です。なお、点がちょうど辺や頂点上にある場合の扱いは実装によって挙動が異なる場合があるため、厳密な境界判定が必要なケースでは注意が必要です。ゲーム開発での当たり判定や地理情報システム(GIS)など、幅広い分野で応用される基本的な幾何計算なので、ぜひ理解しておきましょう。