chan算法和fang算法的代码

Chan算法和Fang算法都是求凸包的算法，下面分别给出它们的Python代码实现。

Chan算法：

import math

def jarvis(points, n):
    hull = []
    left = 0
    for i in range(n):
        if points[i][0] < points[left][0]:
            left = i
    p = left
    while True:
        hull.append(points[p])
        q = (p + 1) % n
        for i in range(n):
            if (points[i][1] - points[p][1]) * (points[q][0] - points[i][0]) > (points[i][1] - points[q][1]) * (points[p][0] - points[i][0]):
                q = i
        p = q
        if p == left:
            break
    return hull

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

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

def sub(a, b):
    return (a[0] - b[0], a[1] - b[1])

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def norm(a):
    return math.sqrt(a[0] ** 2 + a[1] ** 2)

def angle(a, b):
    return math.acos(dot(a, b) / (norm(a) * norm(b)))

def dist(a, b):
    return norm(sub(a, b))

def polar_angle(p, p0):
    return angle(sub(p, p0), (1, 0))

def graham_scan(points):
    n = len(points)
    p0 = min(points, key=lambda x: (x[1], x[0]))
    sorted_points = sorted(points, key=lambda x: polar_angle(x, p0))
    stack = [sorted_points[0], sorted_points[1]]
    for i in range(2, n):
        while len(stack) > 1 and cross(sub(stack[-1], stack[-2]), sub(sorted_points[i], stack[-2])) <= 0:
            stack.pop()
        stack.append(sorted_points[i])
    return stack

def get_tangent(p, hull):
    n = len(hull)
    l, r = 0, n-1
    while l < r:
        mid = (l + r) // 2
        if cross(sub(hull[mid], hull[mid+1]), sub(p, hull[mid+1])) < 0:
            r = mid
        else:
            l = mid + 1
    return l

def merge_hulls(hulls):
    hull = []
    for h in hulls:
        hull.extend(h)
    n = len(hull)
    hull = graham_scan(hull)
    if len(hull) == n:
        return hull
    m = len(hulls)
    while m > 1:
        m = (m + 1) // 2
        hulls_new = []
        for i in range(0, len(hulls), m):
            hulls_new.append(graham_scan(hulls[i:i+m]))
        hull = merge_hulls(hulls_new)
    return hull

def chan(points):
    n = len(points)
    k = int(math.ceil(math.sqrt(n)))
    hulls = []
    for i in range(0, n, k):
        hulls.append(graham_scan(points[i:i+k]))
    hull = merge_hulls(hulls)
    while True:
        m = len(hull)
        if m < k:
            hull = merge_hulls(hulls)
        else:
            tangents = []
            for p in hulls:
                tangents.append(get_tangent(p, hull))
                tangents.append(get_tangent(p[::-1], hull[::-1]))
            tangents = list(set(tangents))
            tangents.sort()
            m = len(tangents)
            best = (dist(hull[i], hull[j]), i, j) = float('inf'), -1, -1
            for i in range(m):
                j = (i + 1) % m
                a, b = tangents[i], tangents[j]
                ab = sub(hull[b], hull[a])
                max_distance = 0
                for k in range(m):
                    d = cross(ab, sub(hull[tangents[k]], hull[a]))
                    if d > max_distance:
                        max_distance = d
                        c = k
                if max_distance < best[0]:
                    best = (max_distance, a, b)
                    c_best = c
            if best[0] == float('inf'):
                break
            h1 = hull[best[1]:best[2]+1]
            h2 = [hull[i] for i in range(best[2], m)] + [hull[i] for i in range(0, best[1]+1)]
            hulls = [h1, h2, hull[tangents[c_best]:tangents[(c_best+1)%m]+1][::-1], hull[tangents[(c_best-1)%m]:tangents[c_best]+1][::-1]]
            hull = merge_hulls(hulls)
    return hull

Fang算法：

from collections import deque
import math

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

def sub(a, b):
    return (a[0] - b[0], a[1] - b[1])

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def norm(a):
    return math.sqrt(a[0] ** 2 + a[1] ** 2)

def dist(a, b):
    return norm(sub(a, b))

def tangent(hull, p):
    n = len(hull)
    if n == 1:
        return hull[0]
    l, r = 0, n-1
    while r - l > 1:
        mid = (l + r) // 2
        if cross(sub(hull[mid+1], hull[mid]), sub(p, hull[mid])) < 0:
            l = mid
        else:
            r = mid
    if cross(sub(hull[l+1], hull[l]), sub(p, hull[l])) < 0:
        return hull[l]
    elif cross(sub(hull[r], hull[r-1]), sub(p, hull[r])) < 0:
        return hull[r]
    else:
        return hull[l]

def fang(points):
    n = len(points)
    points.sort()
    upper = deque([points[0], points[1]])
    for i in range(2, n):
        while len(upper) > 1 and cross(sub(upper[-1], upper[-2]), sub(points[i], upper[-2])) < 0:
            upper.pop()
        upper.append(points[i])
    lower = deque([points[-1], points[-2]])
    for i in range(n-3, -1, -1):
        while len(lower) > 1 and cross(sub(lower[-1], lower[-2]), sub(points[i], lower[-2])) < 0:
            lower.pop()
        lower.append(points[i])
    hull = list(upper) + list(lower)[1:-1][::-1]
    hull = [hull[i] for i in range(len(hull)) if i == 0 or dist(hull[i], hull[i-1]) > 1e-8]
    hull.sort()
    m = len(hull)
    for i in range(m):
        hull[i] = (hull[i][1], -hull[i][0])
    hull.sort()
    for i in range(m):
        hull[i] = (-hull[i][1], hull[i][0])
    hull = hull[::-1]
    hull = [hull[i] for i in range(len(hull)) if i == 0 or dist(hull[i], hull[i-1]) > 1e-8]
    m = len(hull)
    for i in range(m):
        hull[i] = (hull[i][1], -hull[i][0])
    hull.sort()
    for i in range(m):
        hull[i] = (-hull[i][1], hull[i][0])
    hull = hull[::-1]
    m = len(hull)
    i0 = hull.index(min(hull))
    hull = hull[i0:] + hull[:i0]
    for i in range(m):
        hull[i] = (hull[i][0], -hull[i][1])
    hull.sort()
    for i in range(m):
        hull[i] = (hull[i][0], -hull[i][1])
    hull = hull[::-1]
    for i in range(m):
        hull[i] = (hull[i][1], hull[i][0])
    hull = hull[::-1]
    while len(hull) > 2:
        m = len(hull)
        hull_new = [hull[0]]
        for i in range(1, m-1):
            if cross(sub(hull[i], hull[0]), sub(hull[i+1], hull[0])) < 0:
                continue
            if cross(sub(hull[i], hull[0]), sub(hull_new[-1], hull[0])) < 0:
                hull_new.pop()
            hull_new.append(hull[i])
        hull_new.append(hull[-1])
        if len(hull_new) == len(hull):
            break
        hull = hull_new
    m = len(hull)
    for i in range(m):
        hull[i] = (hull[i][1], hull[i][0])
    hull.sort()
    for i in range(m):
        hull[i] = (hull[i][1], hull[i][0])
    hull = hull[::-1]
    for i in range(m):
        hull[i] = (hull[i][1], hull[i][0])
    hull = hull[::-1]
    hull = [(hull[i][1], hull[i][0]) for i in range(len(hull))]
    return hull

这两个算法的实现并不简单，需要理解算法的原理和细节才能正确实现。