4

在给定指定宽度的情况下，从大约 5,00 个坐标中找到位于点路径内的坐标集的最佳方法是什么。例如，一架飞机跟随几个航路点。

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

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

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

  1. 存储纬度/经度或使用球坐标的最佳方式
  2. 在坐标集中有额外的聚类信息
  3. 可以使用某种转换来简化范围检查
  4. 订购积分的最佳方式是什么

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

4

4 回答 4

2

您可以进行许多优化：

  • 将您的点分成固定大小的图块，这样您就不必检查每个点（首先确定您所在的图块，这样您就可以跳过其他图块中的所有点）。

  • 在计算到每个点的距离时，您通常会使用毕达哥拉斯来获得距离。但是如果你只想知道哪个点最近，你可以省略平方根，这是一个昂贵的操作（见下面的示例代码）。

  • 使用一些平面投影而不是使用纬度/经度，或者通过假设地球是平的来近似计算距离。对于小距离（直到几公里），这通常足够准确，并且比使用 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;
于 2009-01-15T01:21:20.687 回答
1

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

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

于 2009-01-24T04:02:11.140 回答
1

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

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

于 2009-01-15T00:47:04.157 回答
0 
 Best way to store lat / long, or use spherical coordinates

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

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

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

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

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

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

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

于 2009-01-15T01:06:44.507 回答