c++ - 球形空间约束的Delaunay三角剖分

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

3年前关闭。



Improve this question




为了在球体上实现高性能动态寻路算法(在C++中)，我对在球体表面执行增量约束Delaunay三角剖分感兴趣。现有的库似乎还不够用-到目前为止，我能找到的最接近的库是CGAL，它的拓 flutter 空间正确，而度量空间错误。

该库应具有:

合理的性能(我有大约10万个得分)

球形拓 flutter 和度量空间(老实说，此规则大范围否决了＃1)

增量点插入和删除(供以后的算法使用)

目前，我唯一的真实选择似乎是近似的(通过在2D欧式度量空间上进行投影并在Delaunay保证提供的折衷方案中进行权衡)或编写我自己的选择，其中包括所有麻烦。在球形度量空间中是否存在用于约束Delaunay三角剖分的库？

最佳答案

由于现在已将其标记为脱机主题(由于垃圾邮件？)，所以我也至少给出一个全面的答案。

据我所知-截至2017年7月-有两种方法可以计算球体上点的约束Delaunay三角剖分。

第一个是libdts2(1)。它基于CGAL 2D delaunay三角剖分算法，并使用完全在球面上的有理点。不在球面上的点将捕捉到恰好在球面上的近似有理点(2)。
它的缺点是始终使用4个辅助点，这些辅助点始终是三角剖分的一部分。也不可能插入非常接近北极的任何点。相交约束的计算要么非常缓慢，要么仅是近似的。

另一个选择是实现(3)中提出的算法。在这种方法中，点不必完全在球面上。不幸的是，尽管有计划将其集成到CGAL(4)中，但尚无可用的代码。

因此，最好的选择是使用libdts2，直到GeometryFactory / INRIA释放其代码为止。因为libdts2的接口(interface)在大多数方面都类似于CGAL三角剖分算法的接口(interface)，所以这不会造成太大的问题。

如果对libdts2感兴趣，则可以期望以下内容:

使用大约170 MiB Ram(单线程，Core i7-4700MQ)在Saarland的OpenStreetMap数据集中的所有街道(309K节点，324K段)的CDT计算大约需要16秒。

在谓词

上评估谓词

如果将无限面算作三角剖分面，则它具有球形拓 flutter

可以插入/删除，因为它基于CGAL 2D三角剖分算法

引用文献:

libdts2在GitHub上可用

“Rational Points on the Unit Sphere: Approximation Complexityand Practical Constructions”

“Robust and Efficient Delaunay triangulations of points on or close to a sphere”

CGAL Google Summer of Code Project Ideas