二维几何基础

What · 是什么

二维计算几何基础是用坐标与向量表示点、线、多边形并在此基础上进行几何运算的模板代码族。核心原语包括：点积 dot(a,b)=x1x2+y1y2（衡量投影与垂直），叉积 cross(a,b)=x1y2-x2y1（衡量有向面积与旋转方向，其符号决定三点 (o,a,b) 的转向），多边形面积 S=1/2|Σ v_i×v_{i+1}|（有向面积），线段相交判定（快速排斥实验+跨立实验），两直线交点（叉积比例），以及点在多边形内的射线法/回转数判定。几乎一切计算几何（凸包、旋转卡壳、半平面交、最近点对等）都构建在这一层原语之上。

Why · 为什么

How · 实现

伪代码

# 基础原语（假设点 = (x,y) 元组）
dot(u,v)  = u.x*v.x + u.y*v.y
cross(u,v)= u.x*v.y - u.y*v.x

# 三点方向判定 (o -> a -> b)
turn(o,a,b) = cross(a-o, b-o)
# >0 左转 / <0 右转 / =0 共线

# 多边形有向面积 (p0..pn-1 按序)
area2 = Σ_i cross(p_i, p_{i+1})   # 结果 = 2*有向面积
area  = |area2| / 2

# 线段相交判定：快速排斥 + 跨立
if 快速排斥失败(包围盒不相交): return False
if cross(a,b,c)*cross(a,b,d) <= 0 and cross(c,d,a)*cross(c,d,b) <= 0:
    return True   # 注意共线退化要用 on_segment 特判

# 两直线交点: 直线 l1 = p1 + t*d1, l2 = p2 + s*d2
den = cross(d1, d2); 若 |den|≈0 → 平行
 t  = cross(p2-p1, d2) / den
return p1 + t*d1

Python 实现

# -*- coding: utf-8 -*-
import math


def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]


def cross_vec(u, v):
    return u[0]*v[1] - u[1]*v[0]


def turn(o, a, b):
    return cross_vec((a[0]-o[0], a[1]-o[1]), (b[0]-o[0], b[1]-o[1]))


def polygon_area(poly):
    s = 0.0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        s += x1*y2 - x2*y1
    return abs(s) / 2.0


def on_segment(p, a, b):
    return (min(a[0], b[0])-1e-12 <= p[0] <= max(a[0], b[0])+1e-12 and
            min(a[1], b[1])-1e-12 <= p[1] <= max(a[1], b[1])+1e-12)


def seg_intersect(a, b, c, d):
    o1 = turn(a, b, c)
    o2 = turn(a, b, d)
    o3 = turn(c, d, a)
    o4 = turn(c, d, b)
    if o1*o2 < 0 and o3*o4 < 0:
        return True
    if abs(o1) < 1e-12 and on_segment(c, a, b):
        return True
    if abs(o2) < 1e-12 and on_segment(d, a, b):
        return True
    if abs(o3) < 1e-12 and on_segment(a, c, d):
        return True
    if abs(o4) < 1e-12 and on_segment(b, c, d):
        return True
    return False


def line_intersect(p1, d1, p2, d2):
    den = cross_vec(d1, d2)
    if abs(den) < 1e-15:
        return None
    t = cross_vec((p2[0]-p1[0], p2[1]-p1[1]), d2) / den
    return (p1[0]+t*d1[0], p1[1]+t*d1[1])


def pip_ray(p, poly):
    x, y = p
    inside = False
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        if (y1 > y) != (y2 > y):
            xi = x1 + (x2-x1)*(y-y1)/(y2-y1)
            if x < xi:
                inside = not inside
    return inside


if __name__ == '__main__':
    sq = [(0, 0), (4, 0), (4, 4), (0, 4)]
    assert abs(polygon_area(sq) - 16.0) < 1e-9
    assert abs(polygon_area(sq[::-1]) - 16.0) < 1e-9
    assert seg_intersect((0, 0), (4, 4), (0, 4), (4, 0))
    assert not seg_intersect((0, 0), (1, 0), (2, 0), (3, 0))
    p = line_intersect((0, 0), (1, 1), (0, 1), (1, 0))
    assert p and abs(p[0]-1.0) < 1e-9 and abs(p[1]-1.0) < 1e-9
    p = line_intersect((0, 0), (1, 1), (0, 1), (1, -1))
    assert p and abs(p[0]-0.5) < 1e-9 and abs(p[1]-0.5) < 1e-9
    assert pip_ray((2, 2), sq) is True
    assert pip_ray((5, 2), sq) is False
    assert turn((0, 0), (1, 0), (1, 1)) > 0
    assert turn((0, 0), (1, 0), (1, -1)) < 0
    print('2d-geometry all tests passed')

易错点

• 叉积为 0 是共线而非'不相交'，线段相交必须额外处理三点共线+on_segment
• 面积公式结果是有向面积，凹多边形也需取绝对值
• 浮点比较不要用 ==，统一 sgn(x)=(-1/0/1) 配合 eps
• 射线法遇射线穿过顶点/平行边会出错，用无理数斜率或特殊处理规避
• cross(a,b) 与 cross(o,a,b) 参数形式混用导致方向颠倒
• 点坐标大时叉积可能溢出 int，用 long long/Python 大整数

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/geometry/2d.md
• CP-Algorithms✓ https://cp-algorithms.com/geometry/basic-geometry.html
• CP-Algorithms✓ https://cp-algorithms.com/geometry/area-of-simple-polygon.html
• CP-Algorithms✓ https://cp-algorithms.com/geometry/oriented-triangle-area.html
• CP-Algorithms✓ https://cp-algorithms.com/geometry/segment-to-line.html
• 书籍✓ CPH ch29