哪种算法可以在路径的一定距离内有效地找到一组点？

Question

给定一组点s(一组x,y坐标)和由连接一组点l的线段组成的路径,描述一种有效的算法,可用于从s中找到点的子集.在路径l的指定距离d内.

这种实际应用可能是在城市之间的公路旅行路径上的任何地方找到10英里范围内的餐馆列表.

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

解决方案在C#中是首选,但可以为基于SQL的方法提供奖励积分:-)

Answer 1

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

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

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

Answer 2

家庭作业很艰巨吧？

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

编辑：所以如果它看起来只是一个家庭作业，也许我可以提供更多帮助......

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

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

不幸的是，除了通过基本三角函数简单地计算它们与圆心之间的距离之外，我还没有足够的几何知识来了解确定点列表是否落在圆内或圆外的聪明方法 - 我是当然有。通过使用前面提到的简单细分或其某些变体，您应该发现可以预先减少需要搜索的可能点的数量。

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

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