我想在几对纬度/经度上创建一个 Voronoi 图，但想使用它们之间的大圆距离，而不是（不准确的）毕达哥拉斯距离。
我可以让 qhull/qvoronoi 或其他一些 Linux 程序这样做吗？
我考虑将点映射到 3D，让 qvoronoi 创建一个 3D Voronoi 图[1]，并将结果与单位球体相交，但我不确定这是否容易。
[1] 我意识到两个纬度/经度之间的 3D 距离（“通过地球”路径）与大圆距离不同，但很容易证明这种变换保留了相对距离，这很重要对于 Voronoi 图。
user354134
问问题
864 次
2 回答
2
我假设你已经找到了这篇文章。由此看来，使用 3D 嵌入似乎是正确的想法。那么你的问题是如何将结果与球体相交。
首先，您需要考虑如何表示 voronoi 图。如果您想在 2D 平面中使用纬度/经度坐标，那么您的 voronoi 图将包含弯曲的边缘，因此最好只使用 3D 表示。
如果您使用像 qvoronoi 这样的程序，理论上您应该只需要无限超平面数据（由 生成Fo）。这给了你平面的方程和它对应的两个点。通常你只需要使用 voronoi 图来测试区域内的包含，超平面应该足够了。
于 2010-07-04T19:27:56.917 回答
2
另请参阅此问题：在球体上计算 Voronoi 图的算法？
于 2010-07-04T19:29:53.057 回答