7 基本几何运算

查看大图

计算几何适合用图来理解，关键是把几何对象、关系判断和算法边界放在一起看。阅读时可以按「几何运算概述 -> 点的运算 -> 点的加法和减法 -> 示例」建立结构，再回到正文里的代码、案例或指标做验证。

查看大图

读完后，用一个真实小任务复查：输入是什么，处理环节在哪里，输出是否可验收；失败时先查「几何运算概述」，再查「点的运算」。

在前一篇中，我们探讨了基础概念之多边形与多面体，理解了何为多边形和多面体，它们在计算几何中的重要性。接下来，我们将进一步深入，学习一些基本的几何运算，这些运算对后续的几何算法和空间划分算法都是非常重要的基础。

1. 几何运算概述

基本几何运算主要包括：

• 点的运算
• 线段的运算
• 多边形的运算
• 多面体的运算

这些运算将为我们处理复杂的几何问题奠定基础。

2. 点的运算

2.1 点的加法和减法

在二维空间中，我们可以定义点的加法和减法。设点 $A(x_1, y_1)$ 和点 $B(x_2, y_2)$，则它们的加法和减法可以定义为：

• 加法：$C = A + B \Rightarrow C(x_1 + x_2, y_1 + y_2)$
• 减法：$D = A - B \Rightarrow D(x_1 - x_2, y_1 - y_2)$

2.2 示例

def add_points(p1, p2):
    return (p1[0] + p2[0], p1[1] + p2[1])

def subtract_points(p1, p2):
    return (p1[0] - p2[0], p1[1] - p2[1])

A = (1, 2)
B = (3, 4)

C = add_points(A, B) # C = (4, 6)
D = subtract_points(A, B) # D = (-2, -2)

3. 线段的运算

3.1 线段的定义

线段是由两个端点定义的。例如，线段 $AB$ 由点 $A(x_1, y_1)$ 和点 $B(x_2, y_2)$ 定义。

3.2 计算中点

线段的中点 $M$ 可以通过线段的两个端点计算得出：

$M = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)$

3.3 示例

def mid_point(A, B):
    return ((A[0] + B[0]) / 2, (A[1] + B[1]) / 2)

A = (1, 2)
B = (3, 4)

M = mid_point(A, B) # M = (2.0, 3.0)

4. 多边形的运算

查看大图

学习基本几何运算时，先确认坐标系、点线表示、方向约定和边界条件。约定不清，结果很容易错。

4.1 多边形的定义

多边形是由一系列顶点及其连接的边组成的闭合图形。假设我们有一个多边形 $P$，由 $n$ 个顶点 $P_1, P_2, \ldots, P_n$ 定义。

4.2 多边形的面积计算

对于简单多边形，面积可以通过以下行列式公式计算：

$\text{Area}(P) = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - y_i x_{i+1}) \right|$

其中，$P_{n+1} = P_1$。

4.3 示例

def polygon_area(vertices):
    n = len(vertices)
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += vertices[i][0] * vertices[j][1]
        area -= vertices[i][1] * vertices[j][0]
    return abs(area) / 2.0

vertices = [(1, 1), (5, 1), (4, 4), (1, 3)]
area = polygon_area(vertices)  # 结果应是 11.0

4.4 多边形的结合与相交

我们还可以定义多边形的合并和相交操作。假设我们有两个多边形 $P$ 和 $Q$。

查看大图

学《基本几何运算》时，可以先找一个自己能复现的小场景，再看相关概念和练习步骤，读完后用自己的例子复述一遍。

• 合并：对于两个相交的多边形，可以用布尔运算得到一个新的多边形。

• 相交：只有当两个多边形有重叠部分时，才能定义它们的交集。

4.5 示例

对多边形的合并和交集操作，通常需要使用计算几何库例如 Shapely。以下是基本的使用示例：

from shapely.geometry import Polygon

P = Polygon([(0, 0), (2, 0), (1, 1)])
Q = Polygon([(1, 0), (3, 0), (2, 1)])

union_poly = P.union(Q) # 合并
intersection_poly = P.intersection(Q) # 交集

5. 多面体的运算

与二维情况类似，多面体的运算涉及到多边形的集合。

5.1 多面体体积计算

使用“点积”或“行列式”方法计算体积，适用于特定的几何形状，例如四面体。

查看大图

如果《基本几何运算》还没完全消化，可以从这张卡片的四个动作重新走一遍。

查看大图

回看《基本几何运算》时，不必一次做大项目，先用一条简单样例确认主线是否清楚。

6. 小结

通过学习基本的几何运算，我们为后续的空间划分算法打下了坚实的基础。在下一篇文章中，我们将探讨几何算法中的空间划分算法，包括例如 BSP树、八叉树等概念。这些算法将帮助我们在更高维度和更复杂情况中处理几何数据。