通过大量纬度/经度坐标优化搜索以找到匹配项 [英] 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. 二分查找；需要按 lat 对坐标列表进行排序，然后按 long 排序 - 但可能会加快速度
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屋！