球面上（经度，纬度）点的凸包

Question

标准的凸包算法无法用于经纬度坐标点，因为标准算法假定您要计算笛卡尔坐标点集的凸包。经纬度点不是笛卡尔坐标系，因为经度在反子午线（+/- 180度）处“环绕”。也就是说，比经度179东两度的是-179。

因此，如果您的点集恰好跨越了反子午线，您将计算出伸展到错误位置的虚假凸包。

有没有什么技巧可以应用到标准凸包算法中来纠正这个问题，或者有关"geospherical"凸包算法的指导？

现在我认为还有更有趣的情况需要考虑，比如围绕地球的一个"带"——它的凸包将没有东/西边界。甚至更进一步，{(0,0), (0, 90), (0,-90), (90, 0), (-90, 0), (180, 0)}的凸包是什么？——它似乎包含整个地球表面，那么哪些点处于其周边缘？

- Maxy-B

---

对于一个伟大的、引人深思的问题，点赞👍。 - Li-aung Yip

请查看此处：https://dev59.com/MWHVa4cB1Zd3GeqPlERR#9612324 - TreyA

Answer 1

标准的凸包算法不是被地球表面坐标的环绕所击败，而是被一个更根本的问题所击败。 球体的表面（让我们忘记地球的不完全球形）不是欧几里得空间，因此欧几里得几何无法使用，而假设基础空间是欧几里得空间的凸包例程（请向我展示一个不这样做的例程）将无法工作。

球体表面符合椭圆几何的概念，其中线是大圆，对极点被视为同一点。 您已经开始体验到尝试将欧几里得凸性概念应用于椭圆空间时出现的问题。

您可以采用测地线凸性的定义并实现测地线凸包例程。 这看起来相当困难。 而且它可能无法产生符合您（通常是欧几里得的）期望的结果。 在许多情况下，对于3个任意点，凸包结果是整个球体表面。

另一种方法，被导航员和制图师采用了很久，是将球面的一部分（包含所有点的部分）投影到欧几里得空间中（这是地图投影的主题，我不会打扰你参考广泛的文献），并计算出投影点的凸包。将你感兴趣的区域投影到平面上，并调整坐标，使它们不会绕过；例如，如果你对法国感兴趣，你可以通过添加30度来调整所有经度，以便整个国家都由正数协调。

当我写这篇文章时，@Li-aung Yip提出的使用三维凸包算法的想法让我觉得是错误的。球面点集的三维凸包将包括位于球内部的点、边和面。它们在二维球面上实际上不存在，只会将你从在二维上处理不太正确的概念转变为在三维上完全错误的概念。此外，我从我引用的维基百科文章中了解到，一个封闭的半球体（即包括其“赤道”的半球体）在球面几何中不是凸的。

- High Performance Mark

---

我主要建议使用3D凸包算法作为思路启发。如果原帖的作者可以提供更多有关数据的信息（在一个国家内的点？世界各地所有首都城市的列表？），那可能会有所帮助。 - Li-aung Yip

感谢您给出的绝佳答案。测地凸性非常有趣，其他向非欧几里得情境推广凸性的概念也同样如此。然而对于我的直接需求来说，只需对纬度/经度点应用一些简单的线性变换，使其永远不跨越本初子午线即可。 - Maxy-B

Answer 2

与其将您的数据视为经度-纬度数据，不如将其视为三维空间中的数据，并应用三维凸包算法? 您可以通过分析三维凸包来找到所需的二维凸包。

这将使您回到已知的笛卡尔三维凸包算法（尽管在三维中），并且不会出现坐标环绕问题。

或者，您也可以参考这篇论文：计算球面上简单多边形的凸包(1996)，该文章似乎处理了一些您正在处理的问题（坐标环绕等）。

- Li-aung Yip

---

谢谢您提供 PDF 链接，但它看起来更像是一篇演讲摘要（PDF 本身），而不是一篇完整的论文。 - Maxy-B

关于3D外壳的想法——因为所有的3D点（根据定义）都位于球体表面上，无论它们在哪里，它们都将被包含在生成的3D凸包中，这样的外壳不会提供任何信息。 - Maxy-B

是的，所有点都将是凸包的一部分 - 但请注意，3D凸包可能具有特定的形状（例如半球）。找到在半球“边缘”上的点集可能会很有用。 - Li-aung Yip

在制作3D外壳之前，您可以添加（0,0,0）以抵消@High Performance Mark提出的（有效）点。仅使用（0,0,0）作为顶点的外壳面，并从中选择不与（0,0,0）相遇的一条边。这些边，投影回球体上，形成原始数据集的2D球形外壳。但是，仅当（0,0,0）位于3D笛卡尔外壳中时才有效；也就是说，如果所有点都在一个半球上。看起来效果很好。 - BlackShift

Answer 3

这个问题早就有答案了，但我想总结一下我的研究结果。

球形凸包基本上只适用于非对踵点。假设所有点都在同一个半球上，你可以通过两种主要方式计算它们的凸包：

1. 使用测地线/中心投影将点投影到平面上，并应用平面凸包算法。参见Lin-Lin Chen，T.C. Woo，“球面计算几何及其在自动化加工中的应用”（1992）。如果这些点在已知半球上，则可以硬编码在哪个平面上将点投影。
2. 将平面凸包算法适应于球体。参见C. Grima和A. Marquez，“表面计算几何：在圆柱、球体、环面和圆锥上执行计算几何”，Springer（2002）。此参考文献似乎提供了与Li-aung Yip上面引用的摘要类似的方法。

作为参考，在Python中我正在实现自己的代码，目前仅适用于北半球上的点。

请参考 Math Overflow 上的 这个问题。

- Yellows

Answer 4

如果你的所有点都在半球内（也就是说，如果你可以找到一个通过地球中心的切割平面将它们全部放在一侧），那么你可以从地球中心进行中央投影，即gnomic投影，在垂直于切割平面的平面上进行。然后在投影中，所有大圆变成直线，因此在投影中的凸包将映射回地球上的正确凸包。你可以通过查看“Gnomonic Projection”部分 here 中的纬线来了解纬度/经度点有多错误（请注意，经线保持直线）。

（将地球视为球体仍不完全正确，但这是一个很好的第二近似。我认为在更现实的地球上（例如 WGS84），真正的最短距离路径上的点通常不位于通过中心的平面上。也许假装它们位于该平面上会给你比使用球体得到的更好的近似值。）

- FutureNerd

Answer 5

FutureNerd:

你说得非常正确。我为我的应用程序解决了与Maxy-B完全相同的问题。首先，我将（lng，lat）视为（x，y）并运行标准的2D算法。只要没有人过于仔细地查看，这个方法就可以正常工作，因为我的所有数据都在美国本土。但是，在第二次迭代中，我使用了你的方法并证明了这个概念。

这些点必须在同一个半球内。事实证明，选择这个半球并不容易（它不仅仅是点的中心，正如我最初猜测的那样）。为了说明这一点，请考虑以下四个点：赤道上的(0,0), (-60,0), (+60,0)以及北极的(0,90)。无论您如何选择定义“中心”，它们的中心都位于北极，因为通过对称性，所有四个点都在北半球。然而，如果我们用冰岛的(-19, 64)替换第四个点，那么它们的中心就不在北极了，而是向着冰岛不对称地绘制。然而，所有四个点仍然在北半球。此外，由北极唯一定义的北半球是它们所共享的唯一半球。因此，计算这个“极点”变得算法化，而不是代数化。

请查看我的代码库获取Python代码： https://github.com/VictorDavis/GeoConvexHull

- Victor Alyn Davis

Answer 6

球面凸包的所有边缘都可以被视为大圆（类似地，在欧几里得空间中，凸包的所有边缘都可以被视为线而不是线段）。每个大圆将球体分成两个半球。因此，您可以将每个大圆构想为一个约束条件。在凸包内的点将位于由每个约束条件定义的每个半球上。

原多边形的每条边都是凸包的候选边缘。要验证它是否确实是凸包的边缘，您只需要验证多边形的所有节点是否位于通过所讨论的边缘的两个节点的大圆所定义的半球上。但是，我们仍然需要创建新的边缘来超越多边形的凹节点。

但是让我们来捷径/蛮力解决这个问题： 在多边形的每对节点之间绘制一条大圆弧。这样做有两种方向（即连接A到B的大圆和连接B到A的大圆）。对于一个有N个节点的多边形，你会得到N^2个大圆。每个大圆都是一个候选约束条件（即凸多边形的候选边缘）。其中一些大圆将与原多边形的边重叠，但大多数不会。现在，再次记住：每条大圆都是将球体约束在一个半球面上的约束条件。现在验证一下原多边形的所有节点是否满足约束条件（即所有节点是否都在由大圆定义的半球面上）。如果是，则该大圆是凸壳的边缘。然而，如果原多边形的任何一个节点不满足约束条件，则该大圆不是凸壳的边缘，可以将其丢弃。

这个方法的美妙之处在于，一旦你将纬度和经度转换为指向单位球面上的笛卡尔向量，它只需要点积和叉积即可完成以下操作： - 通过叉积找到穿过球面上两点的大圆 - 如果点积大于（或等于）0，则一个点位于由大圆定义的半球上。 因此，即使对于具有大量边缘的多边形，这种暴力方法也应该可以正常工作。

- Niklas Griessbaum