在给定地球上的坐标时，计算一个矩形边界框。

Question

我有一组包含n个地理坐标的数据，需要计算该数据的边界框（即找到最东、最西、最北和最南的位置），但不能依赖用户输入（程序没有用户界面）。简单粗暴的方法是“取纬度的最大值和最小值，经度的最大值和最小值，就可以了”——但当这组数据跨越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中，但并未得到解决。

以下方法都行不通：

• 查看其他人的做法（Leaflet也有同样的问题，如上所述）
• 列举可能出现的问题（例如，“如果其中一个坐标接近180度子午线”）——对于边界框横跨但不接近国际日期变更线（IDL）的点，这种方法无法解决（例如日本和夏威夷）
• 遍历所有坐标，并标记是否跨越180度子午线（取决于排序方式）

- Piskvor left the building

---

我并不真正需要一个特定的编程语言的解决方案：由于这是一个空间算法，无论语言的具体细节如何，都应该可以很容易地进行计算。 - Piskvor left the building

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，这将在此处给出不正确的结果。

- Orabîg

Answer 2

Leaflet文档中的https://leafletjs.com/reference-1.5.0.html#latlngbounds指出：

注意：如果区域跨越了反子午线（常常与国际日期变更线混淆），您必须指定位于[-180, 180]度经度范围之外的角落。

因此，例如，如果您想要一个跨越从40°到60°纬度，并且横跨反子午线从-160°到160°经度的区域，似乎您需要使用类似[40,200], [60,160]或[40,-160], [60,-200]的角落来指定该区域的边界。

- David Yockey

---

嗯，如果我手动设置坐标的话，“那就不要这样做”还有些用处。然而，我需要通过计算来确定边界框，即以编程方式。感谢您的努力... - Piskvor left the building

也许我漏掉了什么，但似乎如果程序知道坐标，它可以检查跨越国际日期变更线的条件，并通过将360加或减到其中一个经度坐标来计算可行的坐标。我肯定是太天真了。祝好运。 - David Yockey

那就是关键。如何确定边界框更适合跨越180°而不是其他情况？我的意思是，作为人类，有一种直觉上的“看一看”方法，但我很难将其形式化为一个算法。 - Piskvor left the building