100种算法【Python版】第56篇——Delaunay三角剖分之增量法
本文目录
- 1 增量算法的步骤
- 2 算法示例
- 3 python代码
Delaunay三角剖分的增量算法（Incremental Algorithm）是一种逐步构建三角剖分的方法。
1 增量算法的步骤
（1）初始化：
- 准备一个空的三角剖分集合。
- 创建一个包含所有输入点的“超级三角形”（super triangle），确保这个- 三角形包含所有待插入的点。
（2）逐点插入：
- 对于每一个待插入的点，执行以下步骤：
- 查找包含该点的三角形：遍历当前三角剖分，找到一个三角形，该三角形的外接圆包含待插入的点。
- 删除受影响的三角形：找到所有包含新点的三角形，并将它们从三角剖分中删除。
- 构建新三角形：用新点和被删除三角形的边界边构建新的三角形，形成空腔。
- 处理边界：确定新三角形的边界，确保不会生成重复的边。
（3）清理：
- 在插入所有点后，移除包含超级三角形顶点的任何三角形。