通过经纬度坐标的大列表优化搜索以找到匹配 [英] Optimizing search through large list of lat/long coords to find match

问题描述

我需要创建一个

I need to create a page that

1. 需要 2 个地址(往返)，
2. 绘制该路线 1 英里范围内的路线和区域，
3. 然后确定数千个经纬度坐标的预定义列表中是否有任何位于该区域内(沿路线 1 英里)

我正在使用 google-maps v3 api 和 routeboxer 类.
这是一个很好的例子:http://google-maps-utility-library-v3.googlecode.com/svn/trunk/routeboxer/examples/routeboxer-v3.html
如您所见，#1 和 #2 基本上由这个 routeboxer 示例处理.

I'm using google-maps v3 api and the routeboxer class.
Here is a good example: http://google-maps-utility-library-v3.googlecode.com/svn/trunk/routeboxer/examples/routeboxer-v3.html
As you can see, #1 and #2 are basically taken care of by this routeboxer example.

我的问题是关于如何有效地处理 #3.Routeboxer 提供了一系列箱形坐标(东北纬度/经度到西南纬度/长角).我可以逐个框循环，然后在每个预定义的纬度/经度坐标内循环，以查看列表中的任何坐标是否落在 routeBoxes 的区域内，但这是一个冗长且低效的过程.

My question is about handling #3 EFFICIENTLY. Routeboxer provides a series of box-coords (North East lat/long to South West lat/long corners). I can loop box by box and then loop within each of the predefined lat/long coords to see if any coord in the list falls within the area of the routeBoxes, but this is a lengthy, inefficient process.

我正在寻找优化此 (#3) 搜索部分的方法.一些想法:

I am looking for a means to optimize this (#3) search portion. Some ideas:

1. 二分查找；需要按纬度对坐标列表进行排序，然后按长排序 - 但可能会加快速度
2. mySQL 查询:这将处理用户 PC 并将其放到我们的服务器上；我会查询每个 routeBox:
   select * from myListOfLatLongs where lat box_latwest && lng box)lngsouth

哪个更适合速度&稳定?有没有更好的想法/优化?最重要的是，如果不进行优化，理论上这可以返回许多框，然后每个框都需要与数千个坐标进行比较——这可能会成为一个漫长的过程.任何帮助表示赞赏

Which is more ideal for speed & stability? Are there any better ideas/opimizations? The bottom line is that without optimization, this can theoretically return MANY boxes, and each box would then need to be compared against thousands of coords -- which can become a lengthy process. Any help appreciated

推荐答案

将您的经纬度空间细分为适当大小的单元格，并将位置分类到这些单元格中.

Subdivide your lat/long space into cells of some appropriate size, and sort the locations into those cells.

然后，对于路线上的每个点，在单元格中向外进行螺旋搜索以找到最近的邻居.

Then, for each point along your route, do a spiral search outward among the cells to find the nearest neighbors.

附言螺旋搜索.你可以像这样在正方形、砖块或六边形上进行.如果图块足够大，可以包含一些点但又不是太多，则可以快速找到邻居.

P.S. Spiral search. You can do it on squares, bricks, or hexagons like this. If the tiles are big enough to contain some points but not too many, if finds neighbors quickly.

只要将经纬度转化为上述坐标系，四舍五入到最近的中心，为每个单元格做一个桶.然后找到您的搜索点并找到它的存储桶.如果在它的桶中没有找到任何有用的东西，则搜索半径 1 处的六个桶，依此类推，直到找到合适的邻居集合，然后选择最好的一个.单元格序列如下所示，假设 0,0 是起始单元格:

Just transform the latitude and longitude into the above coordinate system, round them to the nearest center, and make a bucket for each cell. Then take your search point and find its bucket. If nothing useful is found in its bucket, search the six buckets at radius 1, and so on, until a suitable collection of neighbors is found, and pick the best one. The sequence of cells looks like this, assuming 0,0 is the starting cell:

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++ 代码来做到这一点

some C++ code to do it

// 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

添加:有一点可能会得到一个不是最近的点，因为六边形边缘外的点可能比角内的点更近.如果这是一个问题，请多加一层.

ADDED: There is a slight possibility of getting a point which is not the closest, because a point just outside the edge of a hexagon might be closer than a point just inside the corner. If that's a concern, go out to an extra layer.

这篇关于通过经纬度坐标的大列表优化搜索以找到匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！