6 计算几何教程：基础概念之多边形与多面体

查看大图

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

查看大图

读完后，用一个真实小任务复查：输入是什么，处理环节在哪里，输出是否可验收；失败时先查「多边形」，再查「定义」。

在计算几何的领域中，多边形和多面体是基本且重要的几何形状。理解这些概念对后续的几何算法设计和实现至关重要。本文将介绍多边形与多面体的基本概念，并通过示例加以说明。

多边形

定义

查看大图

学习多边形与多面体时，先拆出顶点、边、面和内部区域。结构清楚，面积、碰撞和包含关系才容易计算。

多边形是平面中的一种封闭形状，由一系列线段连接而成，这些线段称为“边”，相邻的边的交点称为“顶点”。多边形的顶点数目决定了它的类型，例如：

• 三角形：3个顶点
• 四边形：4个顶点
• 五边形：5个顶点
• 以此类推。

特性

1. 简单多边形与自交多边形：简单多边形指的是边没有相交的多边形，而自交多边形是指边相交的多边形。
2. 凸多边形与凹多边形：凸多边形的任何两点连线都在多边形内部，而凹多边形至少存在一条连线在多边形外部。

示例

下面是一个简单多边形（三角形）与自交多边形的示例：

• 简单多边形：三角形的顶点可以表示为(0, 0)、(1, 0)和(0, 1)。
• 自交多边形：一个形似“蝴蝶”的自交多边形的顶点可以为(0, 0)、(1, 1)、(1, 0)、(0, 1)。

# 示例代码：绘制一个简单的三角形
import matplotlib.pyplot as plt

# 定义三角形的顶点
triangle = [(0, 0), (1, 0), (0, 1), (0, 0)]  # 封闭曲线

# 解压顶点为x和y值
x, y = zip(*triangle)

# 绘制三角形
plt.plot(x, y)
plt.fill(x, y, alpha=0.3)
plt.title("简单多边形: 三角形")
plt.show()

多面体

定义

查看大图

阅读《计算几何教程：基础概念之多边形与多面体》前，可以先用配图确认主线；读完后再检查哪些步骤能直接操作，哪些还需要补资料。

多面体是三维空间中的一种封闭形状，由多个多边形面组成。每个多边形面都称为“面”，而面与面相交的线称为“棱”，邻接的面交汇的点称为“顶点”。

特性

1. 凸多面体与凹多面体：类似于多边形，凸多面体的任何两点之间的线段都在多面体内部，而凹多面体则可能会在外部。
2. 欧拉公式：对于任何有限的凸多面体，顶点数目（$V$）、棱数目（$E$）和面数目（$F$）满足公式：$V - E + F = 2$。

示例

考虑一个立方体作为多面体的例子：

• 立方体有8个顶点、12条棱和6个面，可以验证欧拉公式：

  $$8 - 12 + 6 = 2$$

应用案例

在计算机图形学和CAD（计算机辅助设计）领域，多边形与多面体的相关算法被广泛应用，例如：

• 碰撞检测：多边形被用于碰撞检测的算法中，判断物体是否相交。
• 网格生成：多面体用于创建三维网格，为更复杂的形状提供基础。

代码示例

下面的代码展示了如何在Python中生成和可视化一个立方体：

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np

# 定义立方体的顶点
vertices = np.array([[0, 0, 0],
                     [1, 0, 0],
                     [1, 1, 0],
                     [0, 1, 0],
                     [0, 0, 1],
                     [1, 0, 1],
                     [1, 1, 1],
                     [0, 1, 1]])

# 定义立方体的棱
edges = [[vertices[i] for i in [0, 1, 2, 3, 0]],
         [vertices[i] for i in [4, 5, 6, 7, 4]],
         [vertices[i] for i in [0, 4]],
         [vertices[i] for i in [1, 5]],
         [vertices[i] for i in [2, 6]],
         [vertices[i] for i in [3, 7]]]

# 绘制立方体
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
for edge in edges:
    ax.plot(*zip(*edge), color='b')

ax.set_title("多面体: 立方体")
plt.show()

查看大图

学完《计算几何教程：基础概念之多边形与多面体》后，不妨换一个自己的场景试一次，重点观察输入、处理和输出是否能对应起来。

查看大图

如果想把《计算几何教程：基础概念之多边形与多面体》用到自己的任务里，可以先缩小场景，只验证一个最关键的判断点。

总结

在本篇中，我们介绍了多边形和多面体的基础概念、特性以及应用示例。这些知识为后续的几何算法之基本几何运算打下基础。在理解了多边形和多面体之后，我们将继续探索更复杂的几何运算。