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"