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

问题描述

我需要创建一个页面，

1. 需要2个地址（来回地址），


2. 绘制该路线1英里范围内的路线和区域，然后找出是否有任何数千个经纬度线的预定列表落入该区域内w / 1英里，沿着路线）

我使用google-maps v3 api和routeboxer类。

以下是一个很好的示例： http://google-maps-utility-library-v3.googlecode.com/svn/trunk/routeboxer/examples/routeboxer-v3.html

正如你所看到的，＃1和＃2基本上由这个路由器例子照顾。

我的问题是关于如何有效地处理＃3。
Routeboxer提供了一系列箱型坐标（东北经纬度/西南经/长角）。我可以逐个循环，然后在每个预定义纬度/长度坐标内循环，以查看列表中是否有任何坐标位于路径框的区域内，但这是一个漫长而低效的过程。

我正在寻找一种方法来优化此（＃3）搜索部分。
一些想法：

1. 二分查找;需要按纬度排序坐标列表，然后长 - 但可能会加快速度


2. mySQL查询：这会将用户PC的处理过程放到我们的服务器上;
   我会查询每个routeBox：
   select * from myListOfLatLongs where lat box_latwest && lng box）lngsouth

哪一种更适合速度&稳定性？有更好的想法/最优化吗？
底线是如果没有优化，理论上这会返回很多方块，然​​后每个方块都需要与数千个坐标进行比较 - 这可能会变成一个漫长的过程。任何帮助表示赞赏

解决方案

将纬度/长度空间细分为适当大小的单元格，并将位置分类到这些单元格中。 / p>

然后，对于沿路线的每个点，在单元格之间进行螺旋搜索以找到最近的邻居。

PS螺旋搜索。你可以在正方形，砖块或六边形这样做。如果瓷砖足够大以容纳一些点但不是太多，如果能够迅速找到邻居。

只需将经纬度转换为上述坐标系，将它们绕到最近的中心，为每个细胞制作一个桶。
然后把你的搜索点，找到它的桶。
如果在其桶中找不到任何有用的东西，则搜索半径为1的六个桶，依此类推，直到找到合适的邻居集合，并选择最好的一个。
假设0,0是起始单元格，单元格的顺序如下所示：

 查找0,0 
 ++ x 
 
 ++ y 
 --x 
 --x， -  y 
 --y 
 ++ x 
 ++ y，x + = 2 
 
 ++ y两次
 --x两次
 --x， -  y两次
 --y两次
 ++ x两次
 ++ x，++ y 
 ++ y，x + = 2 
 
等等
  

编辑：一些C ++代码来完成它

  //对于每个点x，y，执行此操作（d是单元格的直径）
 double x1 =（x + y / 2）/ d; //变换x坐标
 double y1 =（y / 0.866）/ d; //变换y坐标（缩短了一点）
 int ix =（int）floor（x1 + 0.5）; //找到相应的桶
 int iy =（int）floor（y1 + 0.5）; 
 //然后在ix处将点放入桶中，iy 
 
 //搜索，枚举单元格
 //首先在距离0处，然后是1，然后是2等。
 bool bPointsFound = false; 
 //在0,0 
处收集点数如果（/ *集合中有任何点数* /）{
 bPointsFound = true; 
} 
（n = 1; n  iy = 0; ix = n; 
 //右上边
 for（i = 0; i  //在ix处收集桶中的点数，iy 
 iy ++; 
} 
 //顶边
 for（i = 0; i  //在ix上收集点数，iy 
 ix - ; 
} 
 //左上角
（i = 0; i  //在ix桶中收集点数，iy 
 ix--; iy--; 
} 
 //左下边
 for（i = 0; i  //在ix上收集点数，iy 
 iy--; 
} 
 //底边
 for（i = 0; i  //在ix处收集桶中的点数，iy 
 ix ++ ; 
} 
 //右下边缘
 for（i = 0; i  //在ix处收集点数，iy 
 IX ++; IY ++; 
} 
 if（/ *集合中有任何点* /）{
 bPointsFound = true; 
 
 
 //选择集合中最近的点
  

ADDED：获得不是最接近的点的可能性很小，因为六角形边缘外的点可能比角落内的点更近。如果这是一个问题，出去一个额外的层。

I need to create a page that

1. takes 2 addresses (to and from),
2. plots the route AND areas within 1 mile of this route,
3. THEN figure out if any of a predefined list of thousands of lat/long coords falls within this area (w/ 1 mile, along the route)

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.

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.

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

1. a binary search; would require sorting the coord list by lat, then long - but would likely speed things up
2. mySQL query: this takes processing off the usersPC and puts it onto our servers; I would query for each 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.

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.

EDIT: 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屋！