computational-geometry - 凸包的 Delaunay 三角剖分

Question

我需要编写一些关于计算几何的代码并使用openMP将它们并行化。到目前为止，我已经完成了凸包和最近的一对点。我需要编写delaunay三角剖分和征服代码。但我没有太多时间。我读了如果可以计算凸包，则可以轻松实现delaunay三角剖分。因此，如果有人可以为我提供DT的串行代码或至少让我知道如何从凸包生成delaunay三角剖分，我可以编写代码并并行化尽快。

Answer 1

我在某处读到，如果可以计算凸包，则可以轻松实现 delaunay 三角剖分。

这是真的，但准确的说法是，如果3D 凸包实现可用，则可以轻松构建2D Delaunay 三角剖分。了解 2D 船体对构建 Delaunay 三角剖分 (DT) 没有多大帮助，除了给您一些 DT 的边（每个船体边都是 DT 的边）。

假设您还没有实现 3D 船体（这很棘手），那么您需要单独攻击 Delaunay 三角剖分。

Answer 2

QHull 几乎是许多人使用的标准库：http ://www.qhull.org/html/qhull.htm 如果您真的想重新实现它，也许您可​​以将它用作参考实现。