8.2 凸包演算法：Graham scan 與 QuickHull#

JarvisMarch(P):
    hull = [ 由 y 最小的點 start ]     # 若多個 y 相同，取 x 最小
    current = start
    repeat:
        next = 任意一點（不是 current）
        for p in P:
            if p == current: continue
            if (next == current) or (current, next, p 是左轉):
                next = p               # 想要「最靠右的」就會把所有別的點留在左邊
        hull.append(next)
        current = next
    until next == start
    return hull

GrahamScan(P):
    找 pivot p0（y 最小，若相同 x 最小）
    把其餘點 sorted by 極角 angle(p - p0)；角度相同時，先放距離小的
    stack = []
    for p in sorted:
        while stack.size >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()      # 右轉或共線 → 頂點是「拐進去」的
        stack.push(p)
    stack.push(p0)            # 收尾：回到起點
    return stack

# 08.2_graham_scan.py
import math

def cross(o, a, b):
    """cross o→a→b；>0 左轉、=0 共線、<0 右轉"""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def graham_scan(points):
    """Graham scan 凸包；回傳逆時針順序的頂點（不含重複尾端點）"""
    pts = sorted(set(points))               # 去重
    if len(pts) <= 2:
        return pts
    pivot = min(pts, key=lambda p: (p[1], p[0]))
    others = [p for p in pts if p != pivot]
    # 依極角排序；角度相同時，離 pivot 較近者先
    def angle_key(p):
        dx, dy = p[0] - pivot[0], p[1] - pivot[1]
        return (math.atan2(dy, dx), dx * dx + dy * dy)
    others.sort(key=angle_key)
    hull = [pivot]
    for p in others:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

if __name__ == "__main__":
    pts = [(0, 0), (1, 1), (2, 0), (2, 2), (0, 2), (1, -1), (2, 1),
           (3, 0), (1, 0), (1, 2), (3, 3), (0, 3), (3, 2)]
    print(graham_scan(pts))
    # 預期輸出：
    # [(0, 0), (1, -1), (3, 0), (3, 3), (0, 3)]

# 08.2_graham_scan_sympy.py
import math
import sympy as sp
from sympy.geometry import Point, Polygon

def cross_sympy(o, a, b):
    return sp.sign((a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x))

def graham_scan_sympy(points):
    pts = sorted(set(points), key=lambda p: (float(p.x), float(p.y)))
    pivot = min(pts, key=lambda p: (float(p.y), float(p.x)))
    others = [p for p in pts if p != pivot]
    def key(p):
        dx, dy = p.x - pivot.x, p.y - pivot.y
        return (math.atan2(float(dy), float(dx)), float(dx)**2 + float(dy)**2)
    others.sort(key=key)
    hull = [pivot]
    for p in others:
        while len(hull) >= 2 and cross_sympy(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return Polygon(*hull)

ps = [Point(0,0), Point(2,0), Point(2,2), Point(0,2), Point(1,1), Point(1,-1)]
print(graham_scan_sympy(ps))
# 預期輸出：
# Polygon(Point2D(0, 0), Point2D(1, -1), Point2D(2, 0), Point2D(2, 2), Point2D(0, 2))
print(graham_scan_sympy(ps).perimeter)
# 預期輸出：
# 4 + 2*sqrt(2)

# 08.2_monotone_chain.py

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def monotone_chain(points):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    lower, upper = [], []
    for p in pts:                    # 下段：往右走保持左轉不彈
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):          # 上段：往左走保持左轉不彈
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]   # 頭尾各扣一重複點

if __name__ == "__main__":
    pts = [(0, 0), (1, 1), (2, 0), (2, 2), (0, 2), (1, -1), (2, 1),
           (3, 0), (1, 0), (1, 2), (3, 3), (0, 3), (3, 2)]
    print(monotone_chain(pts))
    # 預期輸出：
    # [(0, 0), (1, -1), (3, 0), (3, 3), (0, 3)]

QuickHull(S, a, b):
    # 假設 a, b 已是凸包上的兩點，要解決「a、b 直線右側的點」
    找出距離 ab 直線最遠的點 c
    （若找不到 → 直接回傳空，即這一邊沒有點）
    hull 順序中放入 c
    QuickHull(S 中 ab 直線右側且 ac 直線右側的點, a, c)
    QuickHull(S 中 ab 直線右側且 cb 直線右側的點, c, b)

# 08.2_verify.py
import sympy as sp
from sympy.geometry import Point, Polygon, Segment, Line

ps = [Point(0,0), Point(2,0), Point(2,2), Point(0,2), Point(1,1), Point(1,-1)]
hull = Polygon(Point(0,0), Point(1,-1), Point(2,0), Point(2,2), Point(0,2))
for p in ps:
    print(p, "在 hull 之中嗎?", hull.encloses_point(p) or hull.on_boundary(p.__class__(p.x, p.y)))
# 預期輸出（在邊框上的點，內部則為 False）：
# 頂點會導致 on_boundary 為 True；內部點如 Point2D(1, 1) 則 encloses 為 True

# 08.2_convexity_check.py
from sympy.geometry import Point, Polygon

def is_convex_polygon(poly):
    """檢查多邊形頂點依序走來，每個轉角是否都是左轉（凸且逆時針） """
    vs = list(poly.vertices)
    n = len(vs)
    if n < 3:
        return True
    sign = 0
    for i in range(n):
        a, b, c = vs[i], vs[(i + 1) % n], vs[(i + 2) % n]
        val = ((b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x))
        cur_sign = 1 if val > 0 else (-1 if val < 0 else 0)
        if cur_sign == 0:
            return False
        if sign == 0:
            sign = cur_sign
        elif sign != cur_sign:
            return False
    return True

poly = Polygon(Point(0,0), Point(1,-1), Point(2,0), Point(2,2), Point(0,2))
print(is_convex_polygon(poly))
# 預期輸出：True
bad = Polygon(Point(0,0), Point(2,0), Point(1,1), Point(0,2))
print(is_convex_polygon(bad))
# 預期輸出：False（這是多個箭形，凹多邊形）