Delaunay32:比 Fade2D 快 4 倍的三角剖分库
Exact, parallel 2D Delaunay triangulation for int32 coordinates
Delaunay32 是一个基于 C++17 的高性能库,专为大规模离散 2D 点集(如像素、体素投影)设计。它利用精确整数谓词和 Morton 排序的分治算法,在保持确定性和鲁棒性的同时,实现了惊人的速度提升。基准测试显示,在处理百万级点集时,Delaunay32 比 Fade2D 快约 4 倍,比 delaunator-cpp 快超过 10 倍。该库支持直接传入浮点数并自动量化,同时提供约束三角剖分和带孔多边形处理功能,且无需外部依赖,是图形学和空间数据处理领域的强力工具。
对于大型点集,Delaunay32 的速度比 delaunator-cpp 快 10 倍以上,比 Fade2D 快 4 倍左右。
HN 评论区
24- rezaprima
官网原文:
> 对于大规模点集,Delaunay32 比 delaunator-cpp 快 10 倍以上,比 Fade2D 快约 4 倍。
- hingler36
很棒的项目!
顶点的插入和删除也支持或加速了吗?
是什么限制让这个项目只能做到 32 位?看起来增加位数可以减少量化误差,但如果你为了性能做了些手动 SIMD 优化,那坚持用 32 位我也能理解。
- MattCruikshank
不错,现在来个 3D Delaunay 四面体剖分吧! :)