geospatial - 给定地球上的坐标，计算矩形边界框

Question

我有一套n地球表面上的地理坐标，我想计算一个边界框(找到最东、最西、最北和最南的位置)，而不会退回到用户输入(程序没有 UI)。天真的方法是“取纬度的最大值和最小值，经度的最大值和最小值，完成”-但是当集合跨越第 180 条子午线时，这显然会返回次优结果(例如，类似情况参见斐济:https://www.openstreetmap.org/relation/571747#map=2/-16.6/0.0 不应缩小到整个星球，因为两半实际上是相邻的)。

这在多种解决方案中得到承认，例如在 Algorithm for determining minimum bounding rectangle for collection of latitude/longitude coordinates ，但没有解决。

什么不起作用:

检查其他人如何做到这一点(传单有同样的问题，见上文)

枚举陷阱(例如“如果一个坐标接近第 180 条子午线”) - 不适用于边界框跨越但不接近 IDL(例如日本和夏威夷)的点

检查坐标并标记是否超过 180(取决于订购)

Answer 1

我认为这里有一条简单的路径。我只会考虑经度，因为纬度不会引起任何问题。这个解决方案提供了一个 O(NlogN)(由于排序)的解决方案，这意味着它比只检查最小值和最大值慢，但是在大多数机器上运行它，并且大多数编程语言少于 10^5 点应该花不超过几秒钟

很明显，从数学的角度来看，边界有几种解决方案，因为经度值可以取模 360。



正如我们在上面的示例图像中看到的那样。最好的选择是绿色框，因为它有最小尺寸和 包含所有点 .

找到包含所有点的最小框与相同的问题找到最大的不包含点的盒子



所以在这个简单的图像中，我们需要找到 D 极值的两个点

求D(及相关点)的算法需要按经度对点进行排序，所以在两个连续排序的点之间肯定不会有其他点；所以我们可以检查它们之间的距离(也是最后一个)。这里有一些伪代码

Let C = your set of points
Let N = length( C )
Let S = sort( C )
Let maximumDistance = 0
Let easternLongitudeForBoundingBox = undefined
Let westernLongitudeForBoundingBox = undefined
for i = 0 to N-1 :
   Let j = (i + 1) modulo N    # The index of the point "after" point(i)
   Let D = (S[j].longitude - S[i].longitude ) modulo 360
   if (D > maximumDistance) :
      maximumDistance = D
      easternLongitudeForBoundingBox = S[i].longitude
      westernLongitudeForBoundingBox = S[j].longitude

这完全未经测试，但如果我没有弄错，它应该可以工作。

警告 :当我使用“模”时，它是真正的数学运算符。在某些计算机语言中， (a - b) modulo 360应该写 (360 + a - b) % 360给出正确的结果，因为他们认为 -1 % 360 == -1这将在这里给出不正确的结果。)