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

Question

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

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

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

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

Answer 1

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

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

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