算法確定重疊的地理區域

我有經度和緯度的點，然後我使用半徑計算圓來給出一個範圍。我也有一個地理區域的緯度和經度範圍（在這種情況下是一個州）。我試圖找出圓圈的任何區域是否與任何區域相交。算法確定重疊的地理區域

基本上，我要找的最終結果是，如果一個點（地理編碼地址）在任何狀態的x英里內，它將返回該狀態。

我確定有某種算法可以找到它，但我不知道從哪裏開始尋找。

2011-08-11 Josh

您如何表示狀態？ – Nobody

各州的數據來自Google的Geocode API。因此對於伊利諾斯州來說，數據將來自這個URL。 http://maps.googleapis.com/maps/api/geocode/xml?address=IL,%20United%20States&sensor=false – Josh

http://en.wikipedia.org/wiki/Quad_tree

這對任何種2-d的空間關係有點兒東西一個很好的起點。

來源

2011-08-11 18:31:10 joshx0rfz

地球不是2D歐幾里德空間，所以四叉樹不適合這個。 – tskuzzy

使用Haversine formula：

a = sin²(Δlat/2) + cos(lat1)*cos(lat2)*sin²(Δlong/2) 
c = 2*atan2(√a, √(1−a)) 
d = R*c

的JavaScript：

var R = 6371; // km 
var dLat = (lat2-lat1)*Math.PI/180; 
var dLon = (lon2-lon1)*Math.PI/180; 
var lat1 = lat1*Math.PI/180; 
var lat2 = lat2*Math.PI/180; 

var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

這會給你任何兩點間的大圓距離。其餘依賴於你如何表示狀態。

來源

2011-08-11 18:38:26 tskuzzy

這是一些瘋狂的公式。我從來沒有想過地球的曲率，並將它近似爲平坦，但這絕對是真棒。爲你+1。 – Mike

我檢索爲近似矩形邊界的國家，它沒有100％準確，但谷歌的地理編碼API返回的範圍爲： 36.9702980 -91.5130789 42.5083379 -87。0199349 我不相信Haversine會在這種情況下工作，因爲我不是要確定點之間的距離，而是如果給定半徑內的*任意點落入矩形範圍內。 – Josh

@Josh：你可以測試點到矩形每個點的距離，如果每個點你都可以測試，如果點在矩形內（如果兩個都失敗了，你可以測試）你計算點給定距離你的點，並從你的角度正好位於北，南，西和東，並測試它們是否位於矩形內。如果所有這些測試都失敗了，那麼狀態不在您的觀點範圍內。如果一個沒有失敗，那麼狀態在該範圍內。 – Nobody

-2

如果您試圖查看單個點是否在一個圓圈內，可以使用Pythagoras的theoy。在下面的代碼中，傳遞你的圓的centre_x，centre_y和半徑，然後傳遞你正在評估的點的x，y。

def in_circle(centre_x, centre_y, radius, x, y): 
    square_dist = (centre_x - x) ** 2 + (centre_y - y) ** 2 
    return square_dist <= radius ** 2

來源

2011-08-11 18:40:40 Ina

這沒有考慮地球的曲率。 – tskuzzy

如果你的職位將與Java，而不是用PHP進行標記，我不會試圖重新發明輪子，但只使用JTS（Java的拓撲套件），創建一個幾何形狀和調用方法

public boolean intersects(Geometry g)

我不太瞭解PHP，所以我不能告訴你是否有類似PHP的庫。

幾何從哪裏來？如果您的幾何存儲在類似PostGIS的數據庫中，您也可以嘗試調用一些底層函數（例如數據庫調用）

來源

2011-08-11 22:55:49 EPSG31468

算法確定重疊的地理區域

回答

相關問題