多個緯度/經度點的半徑

Question

我有一個程序，需要輸入一個緯度/長點的數組。我需要對該陣列執行檢查，以確保所有點都在特定半徑內。因此，例如，我允許的最大半徑是100英里。給定一個經緯度數組（來自MySQL數據庫，可能是10點可能是10000）我需要弄清楚它們是否都適合一個半徑爲100英里的圓。

有點難倒如何解決這個問題。任何幫助將不勝感激。

Answer 1

查找the smallest circle containing all points，其半徑出答案比較100

Answer 2

檢查到this question。它提供了一種方法來測量任意兩個（經緯度）點之間的距離。然後使用smallest enclosing circle algorithm。

我懷疑找到一個最小的封閉圓可能在一個平面上足夠困難，所以爲了消除處理經緯度和球面幾何的細微之處，您應該考慮將您的點映射到XY平面。這會導致一定程度的失真，但如果您的預定比例是100英里，那麼您可以忍受這一點。一旦你在XY平面上有一個圓圈和中心，你總是可以映射回地球球體並重新檢查你的距離。

Answer 3

對我來說，解決這個問題最簡單的方法是將座標轉換爲（X，Y，Z），然後找到沿着球體的距離。

假設地球是一個球體（完全不真實）半徑爲R ...

X = R * cos（長）* COS（LAT）

Y = R * SIN（長）* COS （LAT）

Z = R * SIN（LAT）

此時，可以近似使用用於三維空間勾股定理的延長線上的點之間的距離：

dist = sqrt（（x1-x2）^ 2 +（y1-y2）^ 2 +（z1-z2）^ 2）

但是要找到沿表面的實際距離，您需要知道從原點（地球中心）兩點對着的角度。

代表作爲矢量的位置V1 =（X1，Y1，Z1）和V2 =（X2，Y2，Z2），該角度是：

角=反正弦（（V1 X V2）/（| V1 || V2 |）），其中x是叉積。

的距離，則：

DIST =（地球的周長）*角度/（2 * PI）

當然，這沒有考慮到在高程帳戶更改或一個事實，即地球在赤道更寬。

不要在LaTeX寫我的數學道歉。

Answer 4

下面的答案涉及假裝地球是一個完美的球體，應該給出比將平面視爲平面更準確的答案。

要確定一組經緯度點的半徑，首先必須確保您的一組點是「半球」，即。所有的點都可以適合你的完美球體的任意一半。

請參閱Gupta和Saluja在論文「Optimal algorithms for some proximity problems on the Gaussian sphere with applications」中的第3節。我沒有特定的鏈接，但我相信你可以在網上免費找到一份副本。本文不足以實施解決方案。 Ha和Yoo還需要附錄1中的「近似球形多邊形的最大交點的質心」。

我不會使用Megiddo的算法來完成半球測試的線性編程部分。相反，使用Seidel的算法來解決線性規劃問題，如Raimund Seidel的「Small-Dimensional Linear Programming and Convex Hulls Made Easy」所述。另請參見Kurt Mehlhorn的「Seidel的隨機線性規劃算法」和Christer Ericson的「實時碰撞檢測」第9.4節。

一旦你確定你的點是半球形的，移動到Gupta和Saluja的論文的第4部分。這部分展示瞭如何實際得到點的「最小封閉圓」。

要做所需的二次規劃，請參閱N.D.Botkin撰寫的論文「解決二次規劃的隨機算法」。 This tutorial是有幫助的，但本文使用（1/2）x^T G x - g^T x和Web教程使用（1/2）x^T H x + c^T x。一個增加了術語和其他減法，導致符號相關的問題。 Also see this example 2D QP problem。提示：如果你使用C++，Eigen庫是非常好的。

這種方法比上面的一些2D方法稍微複雜一點，但它應該給你比只是完全忽略地球曲率更準確的結果。這種方法也具有O（n）時間複雜度，這可能是漸近最優的。

注意：上述方法可能無法很好地處理重複數據，因此您可能希望在查找最小的封閉圓之前檢查重複的經緯度點。