如何在一组纬度/经度坐标上执行走廊范围搜索 [英] How best to perform corridor range search over a set of latitude / longitude coordinates

问题描述

找到坐标集合的最佳方法是什么，从
约5,00开始，位于点的路径中，给定指定的宽度。
例如一架飞机在几个航点之后。

是否有一种很好的方法可以按照路线相同的顺序对它们进行排序。

计算速度比准确性更重要，因为我正在寻找生成建议列表的
。

我已经看过，我认为这不是直截了当，问题是
a有点宽泛，但任何建议/指针都会受到欢迎，例如：

1. 存储经纬度或使用球坐标的最佳方式
   
2. 在坐标集中添加更多的聚类信息
   
3. 可以使用某种变换来简化范围检查


4. 订购积分的最佳方式是什么？
   

这是一个更好的方法，比沿路径上的几个等距离
点进行圆形/方形检查更好。 解决方案

你可以做很多优化：

• 将点划分为固定大小的图块，因此您不必检查每个点（首先确定您所在的图块，以便可以跳过其他图块中的所有点）。在计算到每个点的距离时，通常使用毕达哥拉斯来获得距离。但是，如果您只想知道哪个点最接近，可以省略平方根，这是一项昂贵的操作（请参阅下面的示例代码）。

使用平面投影，而不是使用纬度/经度，或通过假设地球是平坦的近似计算距离。对于小距离（直到几公里），这通常足够准确，并且比使用WGS84坐标更快，更容易。
您可能必须转换所有的坐标，但预计算将在运行时节省大量CPU周期。

-

  // delphi代码可以遍历一组点以找到索引
 //距离提供的x / y最近的点
函数TMatcher.GetIndexOfClosest（X，Y：Double）：Integer; 
 var 
 i：整数; 
最近的：Double; 
距离：双倍; 
 begin 
最接近：= MaxInt; 
结果：= -1; 
 for i：= 0 to high（Points）do 
 begin 
 //取平方根在此不需要！ 
距离：= Sqr（X-Points [I] .X）+ Sqr（Y-Points [I] .Y）; 
 
如果距离<最近的
开始
最近的：=距离; 
结果：= i; 
 end; 
 end; 
 end; 
  

What would be the best approach to finding the set of coordinates, from say about 5,00, which lie within a path of points, given a specified width. eg an aircraft following several waypoints.

Is there a good way to also sort them in the same order as the route.

Calculation speed would be more important than accuracy, since I'm looking at producing a list of suggestions.

From what I've looked at, I presume it's not straightforward, and the question is a bit broad, but any suggestions/pointers would be welcome, eg for:

1. Best way to store lat / long, or use spherical coordinates
2. Having additional clustering info in the coordinate set
3. Can a transform of some kind be use to simplify the range check
4. What is the best way to order the points

Is here a better approach than doing a circular/square check on several equi-distant points along the path.

解决方案

There are many optimisations that you can do:

• Split your points into fixed sized tiles so you don't have to check every point (first determine which tile you're in, so you can skip all points in other tiles).

• When calculating the distance to each point, you'd normally use pythagoras to get the distance. But if you only want to know which point is the closest, you can omit the square root, which is an expensive operation (see example code below).

• Use some flat projection instead of working with lat/lon, or approximate calculated distances by just assuming that the earth is flat. For small distances (up until several kilometres) that's usually accurate enough, and way faster and easier than working with WGS84 coordinates. You might have to convert all your coordinates though, but that precalculation is going to save a lot of cpu-cycles in runtime.

-

 // delphi code that would iterate through a set of points to find the index
 // of the point that is the closest to the provided x/y
 function TMatcher.GetIndexOfClosest(X,Y:Double):Integer;
 var
  i : Integer;
  Closest:Double;
  Distance:Double;
begin
  Closest:= MaxInt;
  Result := -1;
  for i:=0 to high(Points) do
  begin
    // taking the square root is not needed here!
    Distance :=Sqr(X-Points[I].X)+Sqr(Y-Points[I].Y);

    if Distance < Closest then
    begin
      Closest := Distance;
      Result := i;
    end; 
  end;
end;

这篇关于如何在一组纬度/经度坐标上执行走廊范围搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！