morishuz/delaunay32 来源：https://github.com/morishuz/delaunay32 # Delaunay32 高速、并行的二维 Delaunay 三角剖分，使用精确整数谓词，并支持直接输入浮点数。 多边形字母域内使用蓝噪声点进行三角剖分，并带有约束的外边界和孔洞边界 Delaunay32 是一个 C++17 库，用于对大型离散二维点集进行三角剖分：像素、栅格采样、体素投影、定点几何以及其他量化空间数据。有限的 float 点也可以直接传入；库会在内部对它们进行量化，同时输出的索引继续引用原始坐标。它将精确整数谓词与 Morton 序分治算法、紧凑的双 dart 拓扑结构以及可选的多线程相结合。其结果是一个确定性的、稳健的，并且在大点集上特别快速的三角剖分器。 对于大型点集，Delaunay32 比 delaunator-cpp（https://github.com/delfrrr/delaunator-cpp）快 10 倍以上，比 Fade2D（https://www.geom.at/products/fade2d/）快约 4 倍。 ## 亮点 - 精确的朝向（orientation）和圆内（in-circle）谓词，适用于经过认证的坐标范围 - 有符号 32 位整数输入，包括负坐标和大偏移量 - 串行和共享内存并行执行 - 对重复点的确定性处理 - 适用于非交叉整数线段的约束 Delaunay 三角剖分 - 三角形索引引用原始输入，在三角剖分网格上按逆时针方向排列 - 可选的对边（halfedge）邻接、凸包和重复点代表映射 - 自动、固定步长或固定比例的浮点量化，具有精度限制和冲突策略 - 可选的 delaunay32::extras 配套目标，用于点采样、Delaunay32 几何 JSON、域查询和 SVG 导出 - 正常库使用 MIT 许可且无依赖 ## 文档 - 使用指南：完整的 API、类型、精确性、量化、线程和错误契约 - 变更日志：发布说明和破坏性 API 变更 - 贡献指南：错误报告、验证和拉取请求预期 - 安全策略：受支持的版本和私有报告 - 浮点 SVG 示例：带 QuantizationReport 的端到端浮点输入 - 约束 SVG 示例：相同固定几何的普通和约束三角剖分 - 多边形 SVG 示例：一个带有三个孔洞的凹整数域，以及因域裁剪而省略的点 - 多边形标志 SVG 示例：十个 JSON 定义的多边形字形域内的新蓝噪声点 - 整数 SVG 示例：生成的或 JSON 整数输入 ## 何时使用 Delaunay32 适用于已经是离散的、或可以容忍高分辨率均匀量化的数据。典型示例包括图像空间几何、栅格和高度场采样、投影体素数据、定点地图、图形以及投影空间数据集。 对于大多数不需要精确边拓扑的图形、制图、可视化和通用网格生成应用，直接浮点输入都很实用。triangulate_float() 保持源坐标不变，并返回原始输入的索引。只有边决策使用内部量化的整数坐标。生成的网格通常会非常接近直接根据源值计算出的网格，但其边不保证完全相同。差异最可能出现在几乎重合、共线或共圆的点附近。当需要原始浮点坐标的精确 Delaunay 拓扑时，请使用自适应精确三角剖分器。 ## 性能 以下结果总结了使用一百万个点的 Release 构建基准测试。Delaunay32 自动多线程模式是 1.0× 基线，数值越低越好：4.0× 表示该实现花费的时间大约是基线的四倍。每次比较都使用相同的输入点，并针对每个库分别运行。结果是所测点分布（对于约束三角剖分，还包括若干代表性约束布局）的舍入平均值。 | 工作负载 | Delaunay32 | Fade2D | delaunator-cpp | |:–|–:|–:|–:| | 无约束 Delaunay | 1.0× | ~4.5× | ~11× | | 约束 Delaunay | 1.0× | ~4.3× | — | delaunator-cpp（https://github.com/delfrrr/delaunator-cpp）不支持约束三角剖分，因此约束行中没有显示其结果。Fade2D（https://www.geom.at/products/fade2d/）的结果是使用 Fade2D 2.17.3 及其批量插入 API 测量的。delaunator-cpp 仅作为可选的基准测试子模块包含在内。Delaunay32 本身不依赖它。 这些比值有意保持近似，并且仍然取决于机器和工作负载。仓库中包含一个详细的基准测试，比较了不同点分布下无约束 Delaunay32 与 delaunator-cpp 的性能。请在您自己的机器上运行以获得更详细的性能信息。 ## 快速开始 克隆仓库并初始化可选的基准测试依赖： sh git submodule update --init --recursive cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build -j ctest --test-dir build --output-on-failure 对于仅构建库的情况，不需要 Delaunator： sh cmake -S . -B build \ -DCMAKE_BUILD_TYPE=Release \ -DDELAUNAY32_BUILD_BENCHMARKS=OFF \ -DDELAUNAY32_BUILD_TESTS=OFF \ -DDELAUNAY32_BUILD_EXAMPLES=OFF cmake --build build -j 单独链接的 extras 配套库在默认情况下会构建。添加 -DDELAUNAY32_BUILD_EXTRAS=OFF 可进行严格的仅核心构建。安装命令： sh cmake --install build ### Windows 上的 MSVC 安装带有 使用 C++ 的桌面开发 工作负载的 Visual Studio，以及 Git 和 CMake。在 PowerShell 中使用多配置 Visual Studio 生成器，如下所示： powershell git submodule update --init --recursive cmake -S . -B build cmake --build build --config Release --parallel ctest --test-dir build -C Release --output-on-failure cmake --install build --config Release 与单配置的 Linux 和 macOS 构建不同，Visual Studio 在构建、测试和安装时选择配置。因此，生成的可执行文件位于 build\Release\ 下，例如 build\Release\delaunay_benchmark.exe。 导出的 CMake 目标为 delaunay32::delaunay32（用于三角剖分）和 delaunay32::extras（用于可选的配套工具）。extras 目标链接到核心目标；核心目标从不链接到 extras。 ## 使用方法 ### 整数输入 cpp #include #include int main() { std::vector points = { {0, 0}, {100, 0}, {100, 100}, {0, 100}, {48, 37}, }; // 1 选择串行路径；0 选择硬件线程数。 delaunay32::Triangulator triangulator(0); const std::vector triangles = triangulator.triangulate_int(points); for (const auto& triangle : triangles) { // i0、i1 和 i2 按逆时针顺序索引原始点向量。 } } ### 浮点输入 直接传递有限的 float 坐标作为 FloatPoint 值。无需手动转换或量化： cpp std::vector points = { {0.125F, 0.25F}, {5.5F, 0.1F}, {6.0F, 4.5F}, {-1.0F, 5.0F}, }; const std::vector triangles = triangulator.triangulate_float(points); // 三角形索引指向未更改的 FloatPoint 向量。 for (const auto& triangle : triangles) { const auto& a = points[triangle.i0]; const auto& b = points[triangle.i1]; const auto& c = points[triangle.i2]; // 使用带有原始浮点坐标的 a、b 和 c。 } 当需要量化细节、邻接关系、凸包或代表映射时，请使用 triangulate_float_full(points)。其 quantization 字段报告网格步长、测量的坐标误差和点冲突。QuantizationOptions 可以提供跨独立批次的稳定映射： cpp delaunay32::QuantizationOptions options; options.mode = delaunay32::QuantizationMode::FixedScale; options.origin_x = 0.0; options.origin_y = 0.0; options.scale = 1000.0; const auto triangles = triangulator.triangulate_float(points, options); 返回的顶点保留其原始精度。连接关系是在内部整数网格上计算的，因此边选择可能与原始浮点值的精确 Delaunay 三角剖分不同，尤其是在几何退化附近。 ### 约束整数输入 将边作为同一整数点向量的索引对传递： cpp std::vector constraints = { {0, 2}, {2, 4}, }; const std::vector triangles = triangulator.triangulate_constrained_int(points, constraints); 结果会对整个凸包进行三角剖分，同时将每个约束保留为网格边；如果现有点位于线段上，则保留为网格边链。在远离现有点处的正确交叉会被拒绝。 ### 带孔洞的多边形输入 多边形环是同一顶点向量的索引。闭合边是隐式的，但在末尾重复第一个索引也是可接受的： cpp std::vector outer = {0, 1, 2, 3}; std::vector> holes = { {4, 5, 6, 7}, }; const std::vector triangles = triangulator.triangulate_polygon_int(points, outer, holes); 该调用会规范化环的绕向，将每个边界恢复为约束边链，并且只返回 outer 内部且位于所有孔洞外部的三角形。位于该域之外的点仍然是有效输入，但不会出现在结果中。环必须是简单的，且不得相互交叉或接触。孔洞必须严格位于外环内部，且不得重叠或嵌套。实现不会插入交点或 Steiner 点。 Triangulator 可以在多次调用之间重复使用，以保留工作存储和工作线程。单个实例不得并发调用；单独的实例相互独立。 ### 完整结果 当需要遍历或输入对应关系时，使用可选的结果 API： cpp const delaunay32::TriangulationResult result = triangulator.triangulate_int_full(points); // result.triangles 面索引，与 triangulate_int() 中相同 // result.halfedges 相对的扁平化边，在凸包上为 -1 // result.hull 逆时针的原始输入索引 // result.representatives 输入索引 -> 保留的代表索引 结果还报告谓词宽度和实际线程数。浮点结果包含其 QuantizationReport。仅返回三角形的 API 不会构造任何额外字段。 ### 可选的 extras 库 当应用程序还需要可复用的夹具和可视化工具时，链接 delaunay32::extras： cpp #include #include delaunay32::extras::UniformIntOptions sampling; sampling.point_count = 10000; sampling.bounds = {0, 9999, 0, 9999}; sampling.seed = 42; const auto points = delaunay32::extras::generate_uniform_int_points(sampling); const auto triangles = triangulator.triangulate_int(points); delaunay32::extras::write_mesh_svg("mesh.svg", points, triangles); read_geometry_json() 和 write_geometry_json() 实现了文档化的 Delaunay32 几何模式，用于点、约束和多边形环。它们刻意与模式相关，并非通用的 JSON API。sample_polygon_interiors() 为一个或多个索引多边形域提供边界感知的最佳候选蓝噪声风格采样。 完整的 extras API 请参阅使用指南。 使用指南 给出了精确的整数跨度限制，解释了每个 QuantizationReport 字段，列出了所有重载和异常，并涵盖了重复点、共线输入、绕向、线程和平台差异。 ## 工作原理 在高层面上，Delaunay32： 1. 按输入最小值平移坐标，并认证谓词宽度； 2. 生成 Morton 键并对站点进行基数排序； 3. 使用精确的朝向和圆内谓词构建小型分治叶节点； 4. 通过紧凑的原始边环（primal edge rings）合并相邻三角剖分； 5. 可选地使用就地边翻转恢复约束线段，并合法化每一条无约束边； 6. 可选地填充多边形外部和孔洞，而不跨越其约束边界； 7. 标记外面（outer face），并生成在三角剖分坐标中为逆时针的索引。 对于大型输入，基数排序、独立子树、合并层级和三角形导出共享一个保留的工作线程团队。小型输入保持串行以避免同步开销。 该架构属于成熟的分治 Delaunay 家族，特别是： - L. Guibas 和 J. Stolfi，用于操作一般细分和计算 Voronoi 图的原语（1985） - R. A. Dwyer，一种更快的分治算法，用于构建 Delaunay 三角剖分（1987） ## 运行基准测试 sh ./build/delaunay_benchmark ./build/delaunay_benchmark --quick ./build/delaunay_benchmark --reuse ./build/delaunay_benchmark --format markdown ./build/delaunay_benchmark --format csv ./build/delaunay_benchmark --sizes 1000,10000,1000000 每种情况在计时之前都会与 Delaunator 进行检查。验证首先尝试精确的无方向三角形集合匹配。在共圆点允许不同有效对角线的情况下，它改为要求三角形数量相等，并检查流形边关联和精确的局部 Delaunay 合法性。基准测试会轮换实现顺序并报告中位数。数据集生成、种子、验证和计时边界在 benchmarks/benchmark.cpp 和 benchmarks/support.hpp 中定义。 完整运行使用 11 个样本（最高 10,000 个点）、7 个样本（100,000 个点）和 5 个样本（100,000 个点以上）。--quick 使用 3 个样本。默认的 --fresh 模式为每个测量样本构造并销毁一个 Triangulator，包括工作存储和线程池生命周期。--reuse 通过一个保留的实例来模拟重复三角剖分。 ## SVG 示例 ### 随机浮点点 delaunay_float_example 是一个紧凑的量化的浮点 API 端到端示例。它生成 5,000 个确定性的随机 FloatPoint 值，使用 QuantizationReport 进行三角剖分，打印映射和精度信息，并使用返回的三角形索引所寻址的未更改源坐标写入 SVG。 sh cmake -S . -B build-debug -DCMAKE_BUILD_TYPE=Debug cmake --build build-debug --target delaunay_float_example --parallel ./build-debug/delaunay_float_example float-mesh.svg 在 macOS 上，使用以下命令查看结果： sh open float-mesh.svg 该示例将其点计数、种子和矩形浮点边界作为命名常量保留在 examples/delaunay_float_example.cpp 顶部附近，便于在不干扰 API 流程的情况下进行更改。 ### 约束整数比较 约束示例加载一个固定几何，计算普通和约束的 Delaunay 三角剖分，并将它们并排写入。请求的线段在普通网格上以虚线绘制，在恢复后的网格上以实线绘制。该夹具包含穿过现有点并在现有点处相交的线段。 普通 Delaunay 三角剖分与约束结果并排，请求的线段以红色突出显示 sh cmake --build build-debug --target delaunay_constrained_example --parallel ./build-debug/delaunay_constrained_example \ examples/data/constrained.json constrained.svg 示例代码位于 delaunay_constrained_example.cpp，其可编辑点集位于 constrained.json。 ### 带孔洞的多边形 多边形示例读取索引化的外环和孔洞环，执行约束 Delaunay 三角剖分和域过滤，并同时渲染保留的和省略的输入点。空心红点位于孔洞内部，因此不会出现在任何返回的三角形中。