algorithm - ポイントがどの経度と緯度の範囲にあるかをすばやく判断する方法

Question

(lng, lat) 座標があるとします。範囲の大きなリストもありますが、

[ { 北東: {lng, lat}, 南西: {lng, lat} } ... ]

(lng、lat) ポイントが入るバケットを最も効率的に判断するにはどうすればよいですか?

また、デザインの観点から。「範囲のリスト」が mysql、monodb などのデータベース、または memcached、redis などのデータベースにある方が理にかなっていますか?

ありがとうございました。

Answer 1

範囲のリストを細分化する必要があります。クワッドキーを調べることができます。四分木に似ています。モートン曲線を使用しています。範囲とポイントのクワッドキーを非常に高速に計算できます。しかし、長方形の木を試すこともできます。インターバル ツリーを使用することもできます。