2つの座標間の距離を扱う最も効率的な方法は何ですか？

Question

私は2063の場所をmysqlテーブルに格納しています。私のプロセスの1つでは、特定の結果を、ある特定の起点からどのくらい離れているかに基づいて除外する必要があります。問題は、私は一度に数百、おそらく数千の結果をフィルタリングする必要があるということです。

距離計算を行うにはどうすればよいでしょうか。実行時に実行する必要がありますか？

1. Find all points connecting to my point of origin 
2. loops through the connecting points 
3. calculate the distance between the point of origin and the connecting point 
4. exclude the connecting point if the distance if too great 

のいずれかである必要があります。 p1とp2の間の距離はp2とp1の間の距離と同じになるので、重複する行は避けることができますが、それでもテーブルには数百万行もあります。

またはそれを実行するさらに良い方法はありますか？

Answer 1

MySQLの空間拡張を使用して距離を計算し、データにRツリーインデックスを作成して、ある範囲内のポイントのルックアップを最適化することもできます。

詳細については、MySQLの空間的な拡張のためのドキュメントを参照してください。

 
1. Loop through all points: 
    2. If abs(a-b) < distance && abs(a-b) < distance then: 
    3. Do the fancy distance calculation between a and b. 

すなわち：これについて http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html

Answer 2

方法興味のある距離で定義された「ボックス」の外側にあると仮定した場合、ステップ2でほとんどの点を素早くフィルタリングし、実際の距離を計算することができます。

Answer 3

あなたのデータはmysqlテーブルに入っているので、本当にSQLがあなたを助けてくれる解決策が必要です。

各位置にx座標とy座標があるとします。これらをテーブルに別々のエントリとして格納します。

検索フィールドを目的のポイントを中心としたボックスにすばやく絞り込むことができます。 例えば

WHERE X > (MyPosX - Range) AND X < MyPosX + Range) 
AND Y > (MyPosY - Range) AND Y < MyPosY + Range) 

あなたが範囲内である可能性が高いアイテムの小さなセットを持っていたら、あなたは

編集より反復的なアプローチを使用することができます。実際の距離を作業するとき平方根の計算を避けますしかし、これらは高価です。代わりに

sqrt(x*x + y*y) < distance 

の例は、生成される実行可能ファイルサイズは面白いする必要があります...

(x*x + y*y) < distance*distance  
// distance*distance is a constant and can be calculated once