点の多角形内外判定

点から $x$ 軸の正の向きに半直線を伸ばし、多角形の辺と交わる回数が奇数なら内部、偶数なら外部です。半直線が頂点を通るときに二重に数えないよう、各辺は $y$ 座標が小さい方の端点を含み、大きい方の端点を含まないものとして扱います。座標が整数なら、すべて整数のまま計算できます。

• cross(a, b, c): ベクトル $\overrightarrow{ab}$ と $\overrightarrow{ac}$ の外積
• point_in_polygon(ps, p): 頂点を順に並べた多角形 ps（自己交差がなければ凸でなくてもよく、時計回りでも反時計回りでもよい）に対して、点 $p$ が内部なら $2$、辺上なら $1$、外部なら $0$ を返す。 $O(N)$
• point_in_convex(ps, p): 反時計回りに頂点を並べた凸多角形 ps（3 頂点以上で、どの 3 頂点も一直線上にない）に対して、同じく $2$, $1$, $0$ のどれかを返す。頂点 ps[0] から見た向きで二分探索する。 $O(\log N)$

点はタプル (x, y) で表します。point_in_convex には、凸包 の convex_hull(ps)（include_collinear=False）の結果をそのまま渡せます。

コード

def cross(a, b, c):
    # ベクトル ab と ac の外積
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def point_in_polygon(ps, p):
    # 多角形 ps（頂点を順に並べたもの）に対して、点 p が内部なら 2、辺上なら 1、外部なら 0
    x, y = p
    inside = False
    for i in range(len(ps)):
        a, b = ps[i - 1], ps[i]
        c = cross(a, b, p)
        if (c == 0 and min(a[0], b[0]) <= x <= max(a[0], b[0])
                and min(a[1], b[1]) <= y <= max(a[1], b[1])):
            return 1
        if (a[1] > y) != (b[1] > y) and (c > 0) == (b[1] > a[1]):
            inside = not inside
    return 2 if inside else 0


def point_in_convex(ps, p):
    # 反時計回りに頂点を並べた凸多角形 ps（3 頂点以上、どの 3 頂点も一直線上にない）に対して、内部なら 2、辺上なら 1、外部なら 0
    n = len(ps)
    a = ps[0]
    c1 = cross(a, ps[1], p)
    c2 = cross(a, ps[-1], p)
    if c1 < 0 or c2 > 0:
        return 0
    lo, hi = 1, n - 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if cross(a, ps[mid], p) >= 0:
            lo = mid
        else:
            hi = mid
    c = cross(ps[lo], ps[hi], p)
    if c < 0:
        return 0
    if c == 0 or (lo == 1 and c1 == 0) or (hi == n - 1 and c2 == 0):
        return 1
    return 2