特定の周囲にある座標を見つける最も速い方法は何ですか？

Question

私は100,000座標のデータベースを持っているとしましょう。 特定の座標から1マイル未満離れているものを見つける必要があります。

Answer 1

はまず、我々は2点間の距離を計算するための基本的な機能を記述する必要があります（任意の言語で）これを行うための最も効率的な方法何：この例では

function distance(lat1, lon1, lat2, lon2) {} 

を？最初に、デルタ（緯度と緯度の間の距離）と平均緯度（緯度の平均）を計算する必要があります。

var dLat = lat1 - lat2; 
var dLon = lon1 - lon2; 
var mLat = (lat1 + lat2)/2; 
var earthRadius = 3959; //in miles 

その後、我々はd=180/PI radを使用してラジアンにそれらを変換します。

dLat = dLat * 180/3.1415926535; 
dLon = dLon * 180/3.1415926535; 
mLat = mLat * 180/3.1415926535; 

今、私たちは距離に私たちのデータを変換するための式を使用します。

var distance = earthRadius * (dLat * dLat + Math.pow(Math.cos(mLat) * dLon, 2)); 

と距離に

return distance; 

を返します

今、すべてのポイントとchを繰り返し処理するだけです距離がそれぞれの場合はOKです。ポイントは、このように記述されているとしましょう：

var p = { 
    lat = ... 
    lon = ... 
} 

そしてポイントのリスト（例えば、名前のポイント）と（例えば、名前のREF）基準点があると仮定。

var result = [] 
points.forEach(function (d) { 
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) { 
     result.push(d); 
    } 
}; 

また、緯度の境界ボックスを確認することもできます - longtitudeにはもっと複雑な計算が必要で、時間がかかるだけです。あなたは度でのマイルが1/69 deg/mile（約0.1449度）であると判断できます。だから、この境界ボックスの外側である点をチェックすることができます。

var result = [] 
var maxLat = ref.lat + 0.1449; 
var minLat = ref.lat - 0.1449; 
points.forEach(function (d) { 
    if (d.lat > maxLat || d.lat < minLat) continue; 
    if (distance(d.lat, d.lon, ref.lat, ref.lon) <= 1) { 
     result.push(d); 
    } 
}; 

その後、仕上げは基準点から1マイルよりも近い点の配列を持つ必要があります。

数式に間違いがあるかもしれません（私は、数学者よりもプログラマーに似ています）。だから、Wikipediaの記事にリンクしているかどうかを確認してください。