緯度/経度空間を適切なサイズのセルに分割し、それらのセルに位置を並べ替えます。
次に、ルートに沿った各ポイントについて、セル間で外側に向かってらせん状の検索を行い、最近傍を見つけます。
PSスパイラル検索。このように、正方形、レンガ、または六角形で行うことができます。タイルがいくつかの点を含むのに十分な大きさであるが、多すぎない場合、隣接点がすぐに見つかる場合。
緯度と経度を上記の座標系に変換し、それらを最も近い中心に丸めて、各セルのバケットを作成するだけです。次に、検索ポイントを取り、そのバケットを見つけます。バケットに有用なものが見つからない場合は、半径 1 の 6 つのバケットを検索し、適切な近隣のコレクションが見つかるまで同様に検索し、最適なものを選択します。0,0 が開始セルであると仮定すると、セルのシーケンスは次のようになります。
look in 0,0
++x
++y
--x
--x,--y
--y
++x
++y,x+=2
++y twice
--x twice
--x,--y twice
--y twice
++x twice
++x,++y
++y,x+=2
etc. etc.
編集：それを行うためのいくつかのC++コード
// for each point x,y, do this (d is diameter of a cell)
double x1 = (x + y/2)/d; // transform x coordinate
double y1 = (y / 0.866)/d; // transform y coordinate (it's shortened a bit)
int ix = (int)floor(x1 + 0.5); // find corresponding bucket
int iy = (int)floor(y1 + 0.5);
// then put point into bucket at ix,iy
// to search, enumerate over the cells
// first at distance 0, then 1, then 2, etc.
bool bPointsFound = false;
// collect points in bucket at 0,0
if (/* there are any points in the collection */){
bPointsFound = true;
}
for (n = 1; n < upper_limit && !bPointsFound; n++){
iy = 0; ix = n;
// upper right edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
iy++;
}
// top edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
ix--;
}
// upper left edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
ix--; iy--;
}
// lower left edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
iy--;
}
// bottom edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
ix++;
}
// lower right edge
for (i = 0; i < n; i++){
// collect points in bucket at ix, iy
ix++; iy++;
}
if (/* there are any points in the collection */){
bPointsFound = true;
}
}
// pick the closest point in the collection
追加: 六角形の端のすぐ外側の点は角のすぐ内側の点よりも近い可能性があるため、最も近い点ではない点が取得される可能性がわずかにあります。それが懸念される場合は、余分なレイヤーに出てください。