math - 使用自定义(大圆)距离的 Voronoi 图

Question

我想在几对上创建一个 Voronoi 图
纬度/经度，但想使用大圆距离
它们之间，而不是(不准确的)毕达哥拉斯距离。

我可以让 qhull/qvoronoi 或其他一些 Linux 程序做到这一点吗？

我考虑将点映射到 3D，让 qvoronoi 创建一个 3D
Voronoi 图[1]，并将结果与​​单位球面相交，但
我不确定这很容易。

[1] 我实现了两个纬度/经度之间的 3D 距离(
“穿过地球”路径)与大圆距离不同，
但很容易证明这种转换保留了相对
距离，这对 Voronoi 图来说很重要。

Answer 1

我假设您已经找到 this article .由此看来，您使用 3D 嵌入的想法是正确的。你的问题是如何将结果与球体相交。

首先，您需要考虑如何表示 voronoi 图。如果您想在 2D 平面中使用经纬度坐标，那么您的 voronoi 图将包含弯曲的边缘，因此最好仅使用 3D 表示。

如果你使用像 qvoronoi 这样的程序，理论上你应该只需要无限超平面数据(由 Fo 生成)。这为您提供了平面的方程及其对应的两个点。通常你只需要使用 voronoi 图来测试区域内的包含，超平面应该足够了。