计算几何基础

计算几何基础是计算机科学中研究几何问题的算法设计与分析的领域，主要涉及点、线、多边形等几何对象的数学性质及其在计算机中的表示与操作。本页面将介绍基本概念、常用算法、代码实现及实际应用。

核心概念[编辑 | 编辑源代码]

几何对象表示[编辑 | 编辑源代码]

点：二维平面中用坐标 $(x, y)$ 表示，三维空间扩展为 $(x, y, z)$ 。
向量：具有方向和大小，可通过两点相减得到（如向量 $\vec{A B} = B - A$ ）。
线段：由两个端点定义，可参数化为 $P (t) = A + t (B - A), t \in [0, 1]$ 。
多边形：由有序顶点列表定义，分为凸多边形（所有内角 ≤180°）和凹多边形。

基本运算[编辑 | 编辑源代码]

点积（Dot Product）： $\vec{a} \cdot \vec{b} = | a | | b | \cos θ$ ，用于判断向量夹角或投影。
叉积（Cross Product）： $\vec{a} \times \vec{b} = | a | | b | \sin θ$ ，在二维中可判断点的相对位置（左转/右转）。

算法与实现[编辑 | 编辑源代码]

判断点在线段上[编辑 | 编辑源代码]

通过叉积和点积验证共线性和范围：

  
def is_point_on_segment(p, a, b):  
    cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)  
    dot = (p.x - a.x) * (b.x - a.x) + (p.y - a.y) * (b.y - a.y)  
    length_sq = (b.x - a.x)**2 + (b.y - a.y)**2  
    return abs(cross) < 1e-10 and 0 <= dot <= length_sq  

# 示例  
class Point:  
    def __init__(self, x, y):  
        self.x = x  
        self.y = y  

p = Point(2, 2)  
a = Point(1, 1)  
b = Point(3, 3)  
print(is_point_on_segment(p, a, b))  # 输出: True

线段相交检测[编辑 | 编辑源代码]

利用叉积判断方向变化：

  
def segments_intersect(a1, a2, b1, b2):  
    def ccw(A, B, C):  
        return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x)  
    return (ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0) and \  
           (ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0)  

# 示例  
a1, a2 = Point(1, 1), Point(4, 4)  
b1, b2 = Point(1, 4), Point(4, 1)  
print(segments_intersect(a1, a2, b1, b2))  # 输出: True

实际应用[编辑 | 编辑源代码]

凸包算法[编辑 | 编辑源代码]

Graham扫描法示例（时间复杂度 $O (n \log n)$ ）：

  
def convex_hull(points):  
    points = sorted(points, key=lambda p: (p.x, p.y))  
    lower = []  
    for p in points:  
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0:  
            lower.pop()  
        lower.append(p)  
    upper = []  
    for p in reversed(points):  
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:  
            upper.pop()  
        upper.append(p)  
    return lower[:-1] + upper[:-1]

应用场景[编辑 | 编辑源代码]

机器人路径规划：避免障碍物时计算最短路径。
地理信息系统（GIS）：处理地图多边形叠加或区域划分。
计算机图形学：三维模型碰撞检测或光线追踪。

可视化示例[编辑 | 编辑源代码]

总结[编辑 | 编辑源代码]

计算几何的基础在于理解几何对象的数学表示及其相互关系。通过点积、叉积等运算，可解决许多实际问题如碰撞检测、路径规划等。建议初学者从二维问题入手，逐步扩展到三维空间。