计算几何

引言

计算几何是计算机科学的一个分支，它研究可以用几何方式描述的算法。它是计算机科学中包含算法的设计、分析和实现以解决几何问题的分支。

• 点定位： 在有限的几何空间中查找点的过程。
• 几何搜索： 按其几何身份的某个方面对集合中的示例进行排序，或搜索几何对象或其组件的任务。
• 邻近问题： 在数据集中或两组点之间查找最近的点或最近的邻居。
• 相交问题： 一些任务包括确定几何形状是否相交，以及如果相交，它们在哪里相交。
• 三角剖分： 将多边形分割成不重叠的三角形。
• 凸包： 具体问题是找到给定点集中最小的凸包。

重要性和应用

计算几何因高效算法可以解决高难度几何问题，因此在许多领域都有广泛的应用。

1. 计算机图形学
   
   • 渲染：二维和三维对象的实际实现算法。
   • 建模：几何建模和对象变换、设计。
   • 动画：对象的移动，平移过程的速度和流畅度的控制。
2. 机器人技术
   
   • 运动规划：为机器人规划路径，然后避开路径中存在的对象。
   • 碰撞检测：确定机器人系统中物体可能发生碰撞的情况和地点。
3. 地理信息系统 (GIS)
   
   • 地图叠加：此外，还可以可视化多个数据层，最终生成地图。
   • 地形建模：研究感兴趣区域的地理形状和起伏。
4. 计算机辅助设计 (CAD)
   
   • 设计优化：在对几何特征进行评估后，为产品设计状态进行优化。
   • 仿真：如前所述，几何模型使我们能够在截然不同的条件下测试设计。
5. 医学影像
   
   • 图像重建：前一方法的扩展，它涉及从相机或扫描仪获得的图像切片创建三维模型。
   • 形状分析：使用生物结构的形状作为研究对象来诊断疾病。
6. 机器学习
   
   • 支持向量机 (SVM)：对数据进行排序，并在相同数据上应用几种几何概念。
   • 聚类算法：点或数据点的分类，以使其根据欧几里得距离进行分组。

计算几何中的术语

点

点是几何中一个本质上没有维度的元素；它实际上是一个无量纲对象。在大多数情况下，它只是一个位置；它可以被数学地表示为坐标系统中的一个点。例如，二维空间中的一个点有两个坐标值，如 x 和 y，而在三维空间中，一个点有三个值：x、y 和 z。

线

线是一个直线图形，只有长度，并沿两个相反方向无限延伸。它通过两个点来描述。平面上直线的线性方程可以用多种方式表示，其中一些重要的形式是斜截式，用方程 y = mx + c 表示，或者点斜式，用方程 (y - y1) = m (x - x1) 定义。

平面

平面是一个二维表面，它是完全平坦的，没有厚度；此外，它的尺寸是无限的。在三维空间中，平面通常由该空间中的一个点和垂直于该平面的向量表示，或者由三个不共线的点表示。因此，在 3D 中，平面的一般方程可以写为，给定常数 A、B、C 和 D，其形式为 Ax + By + Cx + D = 0。

多边形

多边形定义为由直线组成的封闭图形。多边形根据形状周围的角度或边的数量进行区分。

• 三角形（3条边）
• 四边形（4条边）
• 五边形（5条边）
• 六边形（6条边）

凸多边形和凹多边形 这是基于形状外围的两种多边形形式。

多面体

多面体是指由平面多边形、直线边以及顶点或角组成的三维几何图形。

• 四面体（4个面）
• 立方体（6个面）
• 八面体（8个面）
• 十二面体（12个面）
• 二十面体（20个面）

多面体还可以分为凸多面体和非凸多面体（也称为凹多面体）。可访问空间中的凸多面体具有一个性质，即连接多面体中任意两点的线段将完全位于构成的空间或多面体的图上。凹多面体是指其内部不朝任何特定方向的多面体；它们不具备此性质。

凸包

凸包是复杂度最小的几何形状，它包含一组点的所有顶点。用橡皮筋套住平面上的一组点并将点连接起来所得到的就是这些点的凸包。凸包在计算几何应用的各种算法中都很重要，包括碰撞检测和模式识别。

Voronoi 图

DG Voronoi 图是一种根据与一组基本点集之间的距离将平面分解为区域的技术。

Voronoi 图的性质

• 每个 Voronoi 单元都是一个凸多边形。
• 也就是说，Voronoi 单元的边是种子之间线段的垂直平分线的一部分。

Delaunay 三角剖分

Delaunay 三角剖分是点的集合的三角剖分，其中任何三角形的外接圆内都不包含任何点。它是 Voronoi 图的对偶图，并且该图保证了所有可以形成的三角形都不是非常细长。

Delaunay 三角剖分的性质

• 唯一性：给定点集的 Delaunay 三角剖分取决于点的性质，因此没有 4 个点共圆。

计算几何中的算法

1. 线段相交

暴力破解法

处理线段相交时最先想到的方法是通常且笨拙地称为“蛮力法”，即检查每一对线段是否重叠。这种方法非常简单，运行时间为 O(n2)，假设有 (n) 条线段。

算法

• 在接下来的过程中，对于要比较的每一对线段，必须首先确定它们是否相交。
• 如果单独的公式得出正值，则线段相交，这可以通过应用任何方向方法或交叉积方法来确认。
• 优点： 对于管理员来说，使用非常方便。
• 缺点： 在处理大量数据的情况下效率不高。

扫描线算法

扫描线算法被证明是一种快速识别线段集形成的所有交点的技术。正在使用的活动结构是一组通过平衡树协调的平面扫描排序的线段集合。

算法

• 对线段的所有端点进行排序。
• 取一条垂直线并将其扫过该平面，因此，我们得到一个活动的线段条集。
• 因此，可以使用平衡树来实现活动线段的排序，然后识别交点。
• 优点： 其时间复杂度优化为 O(n log n + k log n)，其中 (k) 是交点的数量。
• 缺点： 与简化算法相比，由于其复合结构，实现起来相对更复杂。

2. 凸包算法

Graham 扫描法

Graham 扫描法是一种可以在处理点时帮助识别凸包的算法。它将点按与起始点的角度排序，然后处理它们以形成凸包。

算法

• 确定列表中某一点（枢轴点）的最低 y 值。
• 根据点到枢轴点的距离（通过与极轴的角度测量）对点进行聚类。
• 遍历此排序列表中的点以构建凸包。
• 优点： 使用相对简单。
• 缺点： 发生排序步骤，时间复杂度为 O(n log n)。

Jarvis March (包围法)

Jarvis March，或称包围法算法，通过围绕点集来找到凸包。

算法

• 始终从条的末端开始，即最左端的点。
• 选择距离当前位置最远的点，以便以逆时针方向朝北。
• 继续直到回到起点。
• 优点： 文章中使用的语言易于理解且非常通用。
• 缺点： 该算法需要 O(nh) 的时间来查找点集的凸包，对于大型数据集效率不高。

3. 多边形三角剖分

耳切法

耳切法是一种简单的算法，用于对简单多边形进行三角剖分，算法通过从多边形中移除“耳朵”或小三角形来完成。

算法

• 确定多边形中的耳朵在哪里。
• 逐个取出耳朵并形成三角形。
• 一直进行，直到多边形中没有循环的部分已被三角剖分。
• 优点：易于使用且非常容易执行。
• 缺点：效率不高，时间复杂度为 O(n2)。

单调多边形三角剖分

单调多边形三角剖分引入了单调多边形的分解，并且每个单调部分的三角剖分都很简单。

算法

• 通过将多边形分成两组整数和一个两个整数图像来创建 Y-单调片段。
• 应注意，每个单调片段都应使用基于堆栈的方法进行三角剖分。
• 优点：适应性强，时间复杂度为 O(log n)。
• 缺点：与耳切法相比，这种方法更复杂。

几何数据结构

KD 树

• KD 树是一种二叉搜索树类型的数据结构，旨在组织 k 维空间中的点。KD 树的一个有价值的应用是在多维搜索问题中用于范围搜索和最近邻搜索。
• 该树通过根据某些度量在点集上进行二元分割来构建。在每个级别，从集合中选择一个点作为枢轴，然后将点分割成小于枢轴的部分和大于枢轴的部分。分割维度是 k 个维度的索引，它会循环。
• KD 树经常应用于计算机图形学中，例如光线追踪、机器人学中的路径查找以及机器学习中的最近邻搜索功能。

范围树

• 范围树是一种特殊的二叉搜索树，用于快速搜索和检索由多个范围定义的对象的组。
• 该树的构建方法是首先根据一个坐标对点进行排序，然后形成一棵二叉树。同样，主树中的每个节点都带有一个第二棵树，该树根据键的下一个维度来存储点。
• 范围树用于数据库中的多维索引、GIS 中的空间数据访问以及计算几何中的高效范围搜索。

双连边表 (DCEL)。

• 双连边表 (DCEL) 使我们能够描述平面到多边形的镶嵌。它们有效地处理与细分的面、边和顶点相关的查询集。
• DCEL 的记录是为每个顶点、边和面指定的。每条边都有指向起始顶点、孪生边（方向相反）、下一条面边和前一条面边的链接。每个顶点都连接到其相邻边之一，每个面都与其周围边之一相关联。
• DCEL 用于计算机图形学中的网格表示操作、地理信息系统中使用的地图叠加，以及计算几何中的平面图算法操作。

四边形边数据结构

• 四边形边数据结构是一种通用的结构，用于表示平面细分，其许多应用在今天的拓扑和几何操作中仍然具有相关性。
• 该结构使得边的插入、删除和遍历快速简便，也使得顶点和面的访问和修改快速简便。

段树

• 段树是一种特殊的二叉树，用于存储线段的区间。它使我们能够轻松搜索哪些线段包含特定点。
• 它将区间分成子区间，并在其上递归构建树。树的叶子包含区间的最小线段，树的每个节点表示更高层级的线段。

结论

计算几何领域旨在提供必要的、基于数据结构的信息和算法，这些数据结构是解决各种几何任务的核心。从 KD 树到区间树，这些结构改进了图形学、机器人学和 GIS 领域的解决方案。这些概念被认为是必要的，因为工程职业涉及几何的应用以及在计算中使用空间数据。