使用自定义（大圆）距离的 Voronoi 图

Question

我想在几对纬度/纵向上创建一个Voronoi图，但要使用它们之间的圆形距离，而不是（不准确的）毕达哥拉斯的距离。

我可以让 qhull/qvoronoi 或其他 Linux 程序执行此操作吗？

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

1]我意识到两个纬度/纵向之间的3D距离（“通过地球”路径）与大圆距离并不相同，但是很容易证明这种转换保留了相对距离，这很重要用于Voronoi图。

Answer 1

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

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

如果您使用像 qvoronoi 这样的程序，理论上您应该只需要无限超平面数据（由 Fo）。这给出了平面的方程及其对应的两个点。通常您只需要使用 voronoi 图来测试区域内的包含情况，超平面应该足以满足这一要求。

Answer 2

另请参阅这个问题： 计算球体上的 Voronoi 图的算法？