0

我需要创建一个页面

  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 示例照顾。

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

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

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

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

4

2 回答 2

1

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.

enter image description here

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.

于 2013-08-09T09:28:53.407 回答
0

您可以使用空间索引并搜索二维范围，即边界框。例如使用 MySQL 空间扩展。您也可以试试我的希尔伯特曲线类 (phpclasses.org)，它使用四键和范围搜索，它是一个纯 php 解决方案。您也可以尝试四叉树，它比 r-tree 具有更好的性能。

于 2013-08-09T11:13:44.727 回答