时间戳

首页 > 解决方案 > 给定地球上的坐标，计算一个矩形边界框

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

问题描述

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

这在多种解决方案中得到承认，例如在确定收集纬度/经度坐标的最小边界矩形的算法中，但未解决。

什么不起作用：

标签： geospatial

解决方案

我认为这里有一条简单的路径。我只会考虑经度，因为纬度不会引起任何问题。该解决方案提供了 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这里会给出不正确的结果。）

推荐阅读