What is Convex Hull ?

**Materials to read: **

P2742 圈奶牛Fencing the Cows /【模板】二维凸包 https://www.luogu.com.cn/problem/P2742

算法学习笔记(64): 极角排序 - https://zhuanlan.zhihu.com/p/338272449

(CF598C Nearest vectors) https://codeforces.com/contest/598/problem/C

(POJ1106 Transmitters) http://poj.org/problem?id=1106

OI Wiki - 凸包 https://oi-wiki.org/geometry/convex-hull/

Convex Hull - USACO Guide https://usaco.guide/plat/convex-hull?lang=cpp

Convex Hull Algorithm - Graham Scan and Jarvis March tutorial https://www.youtube.com/watch?v=B2AJoQSZf4M

计算几何-凸包(Convex Hull) https://zhuanlan.zhihu.com/p/75382349

凸包—graham scan算法 + 例题P2742 https://www.cnblogs.com/lifehappy/p/12687893.html

Solutions to Convex Hull

Graham Scan Algorithm

  • select a pivot point (with the least y coordinate)
  • sort by polar angle (the angle is calculated by arctan as $ tan\theta = y/x $)
  • test if a new point is to left or to right

Select a Pivot Point

points = sorted(points, key=lambda x: [x[1], x[0]])
start = points[0]

Sort by Polar Angle

直角坐标系$(x,y)$ 和 极坐标 $(\rho, \theta)$ 的转换:

\[tan\theta = \frac{y}{x}\]

要获得极坐标的 “鸡脚”

\[\arctan (y/x) = \theta\]

(什么素 拉格朗日中值定理？)

但是由于 $ arctan $ 的值域是 $(-\frac{\pi}{2}, \frac{\pi}{2})$,而且当 $x = 0$ 时无定义，所以需要复杂的分类讨论。

所幸，<cmath>中有一个atan2(y,x)函数，可以直接计算$(x,y)$的极角，值域是 $(-\pi, \pi)$，所以可以直接用，以x轴为正负的界限。

def polar(p):
    return np.arctan2(p[1] - start[1], p[0] - start[0])
sorted_points = [start] + sorted(points[1:], key=polar)

ToLeftTest

这是一个判断一个点在向量的左边还是右边的算法。 (Graham的思想是，凸包必定是左拐的，由于右拐证明之前的路径不对。 在判断左拐时，可以将 栈顶的两个点构成的向量 与 新的点 比较，看看新的点是在原有线路上左拐还是右拐。)

栈内 [b a], 要加入的点为 c

  • $a(x_a, y_a)$
  • $b(x_b, y_b)$
  • $c(x_c, y_c)$

则有向量

$ \vec{ab} = b - a = (x_b - x_a, y_b - y_a)$

$ \vec{ac} = c - a = (x_c - x_a, y_c - y_a)$

可得

\[\vec{ab} \times \vec{ac} = (x_b-x_a) (y_c-y_a) - (y_b-y_a)(x_c-x_a)\]

如果向量的叉乘是正数，夹角在 $(0, 2\pi)$ 之间。

否则向量的叉乘就是负数，这也就正好对应了 $c$ 点是在 $ab$ 向量的左侧还是右侧。

def cross(a, b, c):
    # 计算叉积，用于判断转向 
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

Graham’s Scan

The following code is generated by Cursor (AI copilt).

def cross(o, a, b):
    # 计算叉积，用于判断转向 # 
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def graham_scan(points):
    if len(points) < 3:
        return points
    # 1. 找到 y 最小的点（如果有多个，取 x 最小的）
    points = sorted(points, key=lambda x: [x[1], x[0]])
    start = points[0]
    # 2. 按极角排序
    def polar(p):
        return np.arctan2(p[1] - start[1], p[0] - start[0])
    sorted_points = [start] + sorted(points[1:], key=polar)
    # 3. Graham扫描
    hull = []
    for p in sorted_points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

Graham’s Scan with Visulization

With step by step visulization (yielding the results).

import random
import matplotlib.pyplot as plt
import numpy as np

def generate_points(n, seed=42):
    random.seed(seed)
    return [(random.randint(0, 100), random.randint(0, 100)) for _ in range(n)]

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

def graham_scan(points):
    # 1. 找到起点
    points = sorted(points, key=lambda x: [x[1], x[0]])
    start = points[0]

    # 2. 极角排序
    def polar(p):
        return np.arctan2(p[1] - start[1], p[0] - start[0])
    sorted_points = [start] + sorted(points[1:], key=polar)
    # 3. 扫描
    hull = []
    for p in sorted_points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
        yield hull, sorted_points  # 每一步都 yield，方便可视化
    return hull

def visualize(points):
    plt.figure(figsize=(8,8))
    plt.scatter(*zip(*points), color='blue')
    plt.title("Random Points")
    plt.show()

    # 动态可视化
    plt.ion()
    fig, ax = plt.subplots(figsize=(8,8))
    ax.scatter(*zip(*points), color='blue')
    for hull, _ in graham_scan(points):
        ax.clear()
        ax.scatter(*zip(*points), color='blue')
        hx, hy = zip(*hull)
        ax.plot(hx, hy, 'r-', lw=2)
        if len(hull) > 1:
            ax.plot([hx[-1], hx[0]], [hy[-1], hy[0]], 'r--', lw=1)  # 闭合
        plt.pause(0.5)
    plt.ioff()
    plt.show()

if __name__ == "__main__":
    points = generate_points(30)
    visualize(points)

Datasets

Each suburb is represented by a set of geographic coordinates (latitude and longitude) defining its boundaries. These points are then used to construct the convex hull.

https://github.com/aidanmorgan/aus_suburb_kml/tree/master

The backup git repository:

https://github.com/randoruf/aus_suburb_kml

For example, in Clayton suburb:

https://github.com/randoruf/aus_suburb_kml/blob/master/VIC/CLAYTON.kml

The first coordinate is 145.123481152,-37.9050731576, each pair is seperated by a blank space.