Python计算几何入门（从零开始掌握几何算法）

准备工作

我们主要使用 Python 内置功能，偶尔借助 math 模块。不需要安装复杂库，确保你已安装 Python（建议 3.6+）即可。

1. 表示点和向量

在几何中，点是最基本的元素。我们可以用元组或类来表示：

# 使用元组表示点point = (3, 4)# 或者定义一个 Point 类（更清晰）class Point:    def __init__(self, x, y):        self.x = x        self.y = y    def __repr__(self):        return f"Point({self.x}, {self.y})"# 创建点p1 = Point(1, 2)p2 = Point(4, 6)

2. 计算两点间距离

这是最基础的几何操作，使用欧几里得距离公式：

import mathdef distance(p1, p2):    """计算两个 Point 对象之间的欧几里得距离"""    return math.sqrt((p2.x - p1.x) ** 2 + (p2.y - p1.y) ** 2)# 示例p1 = Point(0, 0)p2 = Point(3, 4)print(distance(p1, p2))  # 输出: 5.0

3. 判断点是否在线段上

这需要用到向量的叉积和点积。如果三点共线且点在两点之间，则该点在线段上。

def cross_product(o, a, b):    """计算向量 OA 与 OB 的叉积"""    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)def dot_product(o, a, b):    """计算向量 OA 与 OB 的点积"""    return (a.x - o.x) * (b.x - o.x) + (a.y - o.y) * (b.y - o.y)def on_segment(p, q, r):    """判断点 q 是否在线段 pr 上"""    if cross_product(p, q, r) == 0:  # 共线        if min(p.x, r.x) <= q.x <= max(p.x, r.x) and \           min(p.y, r.y) <= q.y <= max(p.y, r.y):            return True    return False# 测试p = Point(0, 0)r = Point(4, 4)q = Point(2, 2)print(on_segment(p, q, r))  # 输出: True

4. 判断两条线段是否相交

这是 几何算法教程 中的经典问题。我们使用方向（orientation）方法结合叉积判断。

def orientation(p, q, r):    """    返回三点的方向：    0 -> 共线    1 -> 顺时针    2 -> 逆时针    """    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)    if val == 0:        return 0    return 1 if val > 0 else 2def segments_intersect(p1, q1, p2, q2):    """判断线段 p1q1 和 p2q2 是否相交"""    o1 = orientation(p1, q1, p2)    o2 = orientation(p1, q1, q2)    o3 = orientation(p2, q2, p1)    o4 = orientation(p2, q2, q1)    # 一般情况    if o1 != o2 and o3 != o4:        return True    # 特殊情况：共线且重叠    if (o1 == 0 and on_segment(p1, p2, q1)) or \       (o2 == 0 and on_segment(p1, q2, q1)) or \       (o3 == 0 and on_segment(p2, p1, q2)) or \       (o4 == 0 and on_segment(p2, q1, q2)):        return True    return False# 测试a1 = Point(0, 0)b1 = Point(4, 4)a2 = Point(0, 4)b2 = Point(4, 0)print(segments_intersect(a1, b1, a2, b2))  # 输出: True

小结

通过以上例子，你已经掌握了 Python计算几何 的几个核心基础操作。这些算法是更复杂应用（如碰撞检测、地图导航）的基石。对于 小白学计算几何 来说，关键是理解几何概念与代码的对应关系，多动手实践。

下一步你可以尝试：计算多边形面积、求凸包（Graham Scan）、或使用 matplotlib 可视化这些几何对象。坚持练习，你会发现 Python几何编程 既实用又有趣！

提示：所有代码均可直接复制到 Python 文件中运行，记得先定义 Point 类。