如何最好地在一组纬度/经度坐标上执行走廊范围搜索

发布于 2024-07-12 00:42:26 字数 363 浏览 10 评论 0原文

找到坐标集的最佳方法是什么，例如大约 5,00 个，位于给定指定宽度的点路径内。例如，一架飞机遵循多个航路点。

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

计算速度比准确性更重要，因为我正在考虑产生建议清单。

从我所看到的来看，我认为这并不简单，问题是有点宽泛，但欢迎任何建议/指针，例如：

存储纬度/经度或使用球面坐标的最佳方式
在坐标集中有附加的聚类信息
可以使用某种变换来简化范围检查
什么是对点进行排序的最佳方法

这是比对几个等距点进行圆形/方形检查更好的方法吗沿路径的点。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

笑红尘 2024-07-19 00:42:26

您可以进行许多优化：

将点分割成固定大小的图块，这样您就不必检查每个点（首先确定您所在的图块，这样您就可以跳过其他图块中的所有点）。
计算到每个点的距离时，通常会使用毕达哥拉斯来获得距离。但如果您只想知道哪个点最接近，则可以省略平方根，这是一个昂贵的操作（请参见下面的示例代码）。
使用一些平面投影，而不是使用纬度/经度，或者通过假设地球是平的来近似计算距离。对于短距离（最多几公里），这通常足够准确，并且比使用 WGS84 坐标更快、更容易。
不过，您可能必须转换所有坐标，但预先计算将在运行时节省大量 cpu 周期。

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

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;

回复收藏 0 原文

下雨或天晴 2024-07-19 00:42:26

我假设您知道如何计算点和路径之间的距离。纬度/经度是简单的 (x,y) 数据，尽管包含小数数据而不仅仅是整数。

5,000 个数据点对于计算每个点到路径的距离来说确实不算糟糕，但如果您希望进行扩展，某种关系数据结构（例如四叉树）将是存储点的最佳选择。这样，您可以立即丢弃远离您的路径的点。

回复收藏 0 原文

孤芳又自赏 2024-07-19 00:42:26

当遇到此类问题时，我会使用 PostGIS。将数据导入数据库，然后使用空间 SQL 函数在轨道上创建缓冲区并选择缓冲区内的点。比自己编码要快得多。

PostGIS（和 PostgreSQL）很容易在 Windows/OSX/Linux 上安装。他们有很好的文档，并且在 Google 上进行快速会话可以找到大多数问题的答案。

回复收藏 0 原文

泪是无色的血 2024-07-19 00:42:26

 存储纬度/经度的最佳方式，或使用球面坐标

你想存储什么？您正在寻找的路径或点？如果它是路径，那么它基本上是某种类型的列表，因为点是有序的。根据您如何/是否操作路径，这将决定您的数据结构。

坐标集中有额外的聚类信息

您想存储什么信息？例如，如果您选择链接列表作为数据结构，则可以有一个类对象的链接列表，其中包含您需要的任何信息。

可以使用某种转换来简化范围检查

您可以将纬度/经度变换为 UTM 或任何其他坐标系。两点之间的范围仍然相同。

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

如果您要存储路径，那么顺序很重要 - 如点 N-1 -> N-> N+1，依此类推...

 Best way to store lat / long, or use spherical coordinates

What are you trying to store? The path, or the point you're searching for? If its the path, then it is fundamentally a list of some kind, as points are ordered. Depending on how/if you will manipulate the path, that will determine your data structure.

Having additional clustering info in the coordinate set

what information are you trying to store? If, for example, you chose a linked list as your data structure, you could have a linked list of class objects containing whatever information you needed.