Convex Hull

Graham Scan — O(n log n)

0 points

About Convex Hull

Convex Hull is the smallest convex polygon containing all points. Graham Scan sorts points by angle, then uses a stack to check if each point makes a counter-clockwise turn. If not, it pops.

Sort

O(n log n)

Scan

O(n)

Total

O(n log n)

Applications

Collision detection, image processing, GIS, machine learning (SVM decision boundary).

convex_hull.py

from functools import cmp_to_key
import math

def graham_scan(points):
    # پیدا کردن pivot (پایین‌ترین نقطه)
    pivot = min(points, key=lambda p: (p.y, p.x))

    # مرتب‌سازی زاویه‌ای
    def angle_sort(a, b):
        angle_a = math.atan2(a.y-pivot.y, a.x-pivot.x)
        angle_b = math.atan2(b.y-pivot.y, b.x-pivot.x)
        return -1 if angle_a < angle_b else 1

    pts = [p for p in points if p != pivot]
    pts.sort(key=cmp_to_key(angle_sort))
    pts = [pivot] + pts

    # Graham Scan — stack
    stack = pts[:2]
    for p in pts[2:]:
        while len(stack) > 1 and cross(stack[-2],stack[-1],p) <= 0:
            stack.pop()     # چرخش ساعتگرد → Pop
        stack.append(p)     # چرخش پادساعتگرد → Push

    return stack  # O(n log n)