Check if a point is inside a convex polygon

概要

凸多角形 \(P = (v_1, v_2, ..., v_N)\) に点 \(w\) が含まれているかを判定する。

外積による判定

各辺に対し、同じ側に含まれているかを判定する。

具体的には、全ての \(1 \le i \le N\) について外積 \((v_{i+1} - v_i) \times (w - v_i)\) が同じ符号(0含む)になるかを確認する。

計算量: \(O(N)\)

二分探索による判定

凸多角形 \(P\) を \(v_1v_iv_{i+1}\) (\(2 \le i \le N-2\)) の \(N-2\)個の三角形に分割し、点\(w\)がどの三角形に含まれるかを外積 \((v_i - v_1) \times (w - v_1)\) の符号によって判定しながら二分探索し、包含判定を行う。

計算量: \(O(\log N)\)

実装

凸多角形の頂点は反時計回りのリストとして持つとする。

# cross product: (b - a)×(c - a)
def cross3(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

# O(N)
def inside_convex_polygon0(p0, qs):
    L = len(qs)
    D = [cross3(qs[i-1], p0, qs[i]) for i in range(L)]
    return all(e >= 0 for e in D) or all(e <= 0 for e in D)

# O(log N)
def inside_convex_polygon(p0, qs):
    L = len(qs)
    left = 1; right = L
    q0 = qs[0]
    while left+1 < right:
        mid = (left + right) >> 1
        if cross3(q0, p0, qs[mid]) <= 0:
            left = mid
        else:
            right = mid
    if left == L-1:
        left -= 1
    qi = qs[left]; qj = qs[left+1]
    v0 = cross3(q0, qi, qj)
    v1 = cross3(q0, p0, qj)
    v2 = cross3(q0, qi, p0)
    if v0 < 0:
        v1 = -v1; v2 = -v2
    return 0 <= v1 and 0 <= v2 and v1 + v2 <= v0

qs = [(-2, 0), (0, -2), (2, 0), (0, 2)]
print(inside_convex_polygon((0, 0), qs))
# => "True"
print(inside_convex_polygon((1, 1), qs))
# => "True"
print(inside_convex_polygon((2, 2), qs))
# => "False"

Verified

  • AOJ: "2827: Industrial Convex Pillar City": source (Python3, 16.71sec)

参考