14

给定一组点s （一组 x,y 坐标）和一条由连接一组点l的线段组成的路径，描述一种有效的算法，该算法可用于从s中找到点的子集，它们是在路径l的指定距离d内。

这方面的一个实际应用可能是沿着城市之间的公路旅行路径在 10 英里范围内的任何地方查找餐馆列表。

例如，在下图中，绿色点将包含在搜索结果中。点图

解决方案在 C# 中是首选，但基于 SQL 的方法可能会获得奖励积分 :-)

4

12 回答 12

5

前段时间我也想过这个问题。我认为，高效是一种误导。只需测试每个点的所有线段就足够了。计算距离很便宜。如果有很多点，您还可以考虑使用水平集方法来细化选择哪些点的策略。IE

  • 沿着这条线走，步长是您要检查的距离的 2 倍（或多或少？）并创建“接近”的人工点。
  • 迭代：在“附近”的点周围选择新点（不计算欧几里德距离，只计算 1 范数并简单地测试 x 和 y 坐标） - 然后测试它们的距离（您甚至可以从人工指向找到的“近”点并首先选择那个进行测试，但要扩大搜索范围，因为可能会有曲折！）

这可能不完整，但应该很快并且避免检查点很远而且很好。

于 2009-01-21T17:11:57.383 回答
3

  1. 定义一条“左路”和“右路”：对于原始路径的每个线段，在该线段的“左侧”创建一个 d 个单位，在“右侧”创建一个 d 个单位的线段。

  2. 将两端的左路和右路连接起来，形成一个多边形。

  3. 应用标准算法来确定哪些兴趣点位于多边形内。

于 2009-01-21T16:34:31.887 回答
1

艰巨的家庭作业是吗？

也许一个好的开始可能是查看广度优先寻路算法——也许像洪水填充方法这样的东西对此有用？

编辑：所以如果它看起来像一个家庭作业，也许我可以更有帮助......

我首先会定义一个包含直线和其中可能包含的点的矩形，因为这可以让我们摆脱大量远离我们的直线的点。

然后，您可以为每个点创建一个正方形，表示该点半径内的点列表。这又是一种减少要搜索的元素数量的方法。

不幸的是，除了简单地通过基本触发计算它们与圆心之间的距离之外，我不知道足够的几何知识来知道一种聪明的方法来决定点列表是落在圆内还是圆外 - 我是肯定有一个。通过使用前面提到的简单细分或一些变体，您应该会发现您可以先发制人地减少需要搜索的可能点的数量。

此外，如果您将所有要搜索的点保留在一个列表中，并在测量后续形状时删除第一个圆的命中点。我已经使用了这个的蛮力版本来根据位置数据进行简单的邮政编码距离检查 - 这在网上很多地方都有记录，但是沿着一条路径运行它可能会在计算上非常昂贵。

这种几何方法可能更适合您没有进行大量重复搜索的情况 - 如果连续有很多，您可能希望将您的 ponts 组织成一个网络，以便您可以对它们使用标准寻路。值得做一些原型设计来看看哪个更有效，但我希望如果您要创建一个合适的网络来表示您的数据，那么您可以更灵活地搜索它。

于 2009-01-21T16:30:18.387 回答
1

对此的唯一解决方案是：

for each point
  for each line
    is distance to line within constraints

一旦找到位于约束内的点，就可以提前终止内部循环。请注意，内部和外部循环可以调换。

那么问题就变成了确定一个点是否在约束范围内。mbeckish 建议使用简单的矩形测试，其中矩形是通过沿线的垂线挤压形成的，但是对于端点附近但在该矩形之外的点，这将失败。沿线的方向挤压矩形也将失败，因为靠近末端的点应该真正使用圆测试中的点：

|-------------
| *    /
|    --
|   /
|  /
| |
| |
|/
|         |--------| <- the line segment

其中 * 在扩展矩形内部但在圆形端盖外部，这将是一个更严格的测试。

现在，距离测试可能不是“乌鸦飞”测试，而是图形搜索，例如，仅使用道路将它们连接在一起的道路 x 英里内的点：

--------------------------------------------------- < the road
   |
   |              * <- target
...|..............|................................ < check distance
   |              |
   |--------------| <- roads to target

在上图中，目标位于搜索区域内，但沿可用道路到达目标将大于允许的距离。

无论您选择实施测试，都将需要循环算法中的基本循环。

检查约束是“如乌鸦飞”约束的约束的方法：

  1. 几何上：首先，确定点 P 到直线的距离。然后，如果该点在约束范围内，则将点 P 投影到线段上，其中线定义为：

    L = P1 + (P2-P1).n

    其中 P1 和 P2 是端点，n 是参数变量。如果投影 P 的 n 值在 0 <= n <= 1 范围内，则该点位于 P1 和 P2 之间。最后，对以 P1 和 P2 为中心的圆进行圆点测试。

  2. 变换：为每个线段创建一个变换矩阵，使 P1 变换为原点，P2 变换为 (|P1-P2|, 0)。然后将每个变换应用于所有点，然后测试矩形（0，-约束）-（|P1-P2|，约束）中的每个点。此方法可以使用 SIMD 或 GPU 进行高度优化

  3. 以图形方式：使用带有圆形端盖且宽度与约束距离成比例的笔将线段绘制到位图。然后，对于每个测试点，检查该点对应的位图中的像素。这并不准确（但更大的位图会产生更准确的结果，但需要更多内存），但一旦创建位图就会很快。

    如果约束是由沿图的路线定义的，它会变得更加复杂。您需要查看广度优先搜索，其中起点是每条线段的终点，终点是潜在目标。如果线段沿其长度有交汇点，则将线段分成没有交汇点的线段。

于 2009-01-21T17:09:01.430 回答
1

我不确定我是否正确理解了这个问题，但Dijkstra 的算法不适合吗？它从源节点找到最短路径，您可以在达到最大距离后中止并检查已找到s中的哪些点。我不确定它在 SQL 上的表现如何。

于 2009-01-21T17:22:35.053 回答
1

1.) 使用几何数据类型（或地理，如果它们是使用纬度/经度坐标定义的）将您的点存储在 SQL Server 2008 表中 这是一个脚本，用于创建随机分布在 (0,0) 和 ( 40,20):

DECLARE @Points table (
  id int,
  position geometry
  );

DECLARE @i int = 0, @x int, @y int;
WHILE (@i < 100)
BEGIN
  INSERT INTO @Points VALUES 
    (@i, geometry::Point(RAND() * 40, RAND() * 20, 0))
  SET @i = @i + 1;
END

2.) 将您的线定义为线串，使用与您的点相同的数据类型和 SRID：

DECLARE @line geometry = 'LINESTRING(0 10, 10 15, 20 8, 40 10)';

3.) 在针对点表的 SELECT 查询的谓词中使用 STDistance() 方法。例如，要选择直线 5 个单位内的所有点：

SELECT * FROM @Points
WHERE @line.STDistance(position) < 5;

更重要的是，由于 SQL Server 的空间方法在可再发行的 dll 中可用（Microsoft.SqlServer.Types.dll - SQL Server 功能包的一部分http://www.microsoft.com/downloads/en/details.aspx? FamilyID=ceb4346f-657f-4d28-83f5-aae0c5c83d52），您可以在 C# 中或直接在 SQL Server 中使用相同的方法。

于 2010-11-29T12:25:30.523 回答
1

如果您想在 SQL 中至少完成一些工作，您可以计算路径的边界框，然后将位置在边界框内的条件合并到查询中。您仅针对返回的行运行其他算法之一。

这至少可以防止您必须为每个路径下载整个数据库。

于 2009-01-23T06:09:37.577 回答
0

您应该能够通过矢量数学和触发来完成此操作，尽管确切的方法使我无法理解。

对于每个线段，计算需要将点从世界坐标转换为相对于线段的局部坐标的值（因此通过计算运行的任何点都将相对于线段为 x 轴的坐标系）

对于每个点运行以下检查：

1-如果该点在任一端点的距离内，我们知道它应该被包括在内。这是通过每个端点和目标点之间的简单距离^2 <= (x2 - x1)^2 + (y2 - y1)^2 计算来完成的。

2-通过变换运行目标点。如果 x >= 0 且 x <= (线段的长度) 且 |y| 转换后 <= 距离，则应包括目标点，否则应将其排除。

我的向量数学有点生疏，所以我无法提供更好的代码/示例对不起！但也许我的帖子会激励其他人写出正确的方法。

于 2009-01-21T21:48:36.560 回答
0

I'm surprised no one has mentioned the A* alogirithm for this. It seems like a perfect fit. What am I missing here? If you're not familar with it, google and ye shall find =). (Yes, it does come from the gaming world...)

于 2010-04-16T14:13:23.897 回答
0

I believe these two classes will answer your question. I built the GetArea() function using Heron's Formula. Make sure that the Segment Points are always passed first to the IsPointWithinDistanceToLineSegment and the TestPoint is always passed 3rd.

EDIT: I stupidly used Point which only allows integers for X and Y. You'll need to fix this with another class that takes doubles or floats as X and Y...

public class Geometry
{
    public static double GetDistanceBetweenTwoPoints(Point SegmentStart, Point SegmentEnd)
    {
        return Math.Sqrt(Math.Pow(SegmentEnd.X - SegmentStart.X, 2) + Math.Pow(SegmentEnd.Y - SegmentStart.Y, 2));
    }

    public static bool IsPointWithinDistanceToLineSegment(Point SegmentStart, Point SegmentEnd, Point TestPoint, double TestDistance)
    {
        if (GetDistanceBetweenTwoPoints(SegmentStart,SegmentEnd) <= TestDistance || GetDistanceBetweenTwoPoints(SegmentEnd,TestPoint) <= TestDistance)
        {
            return true;
        }
        var T = new Triangle(SegmentStart, SegmentEnd, TestPoint);
        var BaseLength = GetDistanceBetweenTwoPoints(SegmentStart, SegmentEnd);
        var Area = T.GetArea();
        var TriangleHeight = 2* Area / BaseLength;
        return T.AB >= T.BC && T.AB >= T.AC && TriangleHeight <= TestDistance;
    }
}

public class Triangle
{
    public Triangle(Point a, Point b, Point c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public Point a
    {
        get;
        set;
    }

    public Point b
    {
        get;
        set;
    }

    public Point c
    {
        get;
        set;
    }

    //Lengths of Sides
    public double AB
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(a, b);
        }
    }

    public double AC
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(a, c);
        }
    }

    public double BC
    {
        get
        {
            return Geometry.GetDistanceBetweenTwoPoints(b, c);
        }
    }

    public double GetArea()
    {
        var Term1 = Math.Pow((Math.Pow(AB, 2) + Math.Pow(AC, 2) + Math.Pow(BC, 2)), 2);
        var Term2 = 2 * (Math.Pow(AB, 4) + Math.Pow(AC, 4) + Math.Pow(BC, 4));
        var result = .25 * Math.Sqrt(Term1 - Term2);
        return result;
    }
}
于 2009-01-22T16:54:39.193 回答
0

您可以使用四叉树将空间划分为段，然后仅用于靠近路径的段中的点吗？

于 2009-01-21T16:49:47.303 回答
0

给定通用计算工具，您最好的算法将是过滤掉明显不感兴趣的点并找到从每个线段到每个剩余点的距离的一些变化。（建议的多边形解决方案是错误的——感兴趣的区域是该多边形与围绕l上每个点的半径为d的圆的并集——实际上比简单地找到每个点到每个线段的距离效率低。）

哪些过滤器最好取决于您的数据的性质——例如，在示例图中，过滤l的边界框（加上d）将非常有用。

一个有趣的过滤器是：给定点p定义l，取一个半径为r的圆，其中r是部分由p加上d定义的两个段的最大长度。只有这个圆内的点才能与这两个线段足够接近才能在我们的解决方案集中，因此我们可以快速确定是否可以跳过这两个线段距离计算。（如果某些线段很长，这将降低效率，但如果它们是，这些线段可以很容易地分解成更小的块。）

于 2009-01-29T10:59:18.503 回答