求多边形点到最近边距离的快速方法

Question

设置

• 函数需要提供从点到多边形最近边的距离。
• 点已知在多边形的内部。
• 多边形可以是凸的，也可以是凹的
• 许多点(百万)需要测试。
• 许多独立的多边形(几十个)将需要在每个点的函数中运行。
• 预计算和持久存储的数据结构是一种选择。
• 最终的搜索函数将在C++中。

对于函数的实现，我知道一个简单的方法是使用标准距离到线段公式来测试多边形的所有段之间的距离。这个方案在规模上会相当缓慢，我相信应该有一个更好的选择。

我的直觉是，对于这类函数，应该有一些非常快速的已知算法，这些算法可以在游戏引擎中实现，但我不知道该在哪里查找。

我找到了一个将线段存储在四叉树中的引用，这将提供非常快速的搜索，我认为它可以用于我的目的是快速缩小将哪个段视为最接近的段，然后只需要计算到一个线段的距离。https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

我还没有找到任何代码示例来说明它是如何工作的。我不介意从头开始实现算法，但是如果一个工作的、经过测试的代码库存在的话，我不认为这样做有什么意义。

我一直在研究几个四叉树实现，我认为它的工作方式是创建一个每多边形的四叉树，并将每个多边形的线段用一个边框插入到该多边形的四叉树中。

然后，我要做的函数的“查询”部分将包括创建一个点作为一个非常小的边框，然后用来对四叉树结构进行搜索，然后该结构只会找到多边形中最接近的部分。

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

和

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

我真正的问题是，对于快速搜索时间函数来说，这看起来像是一种合理的方法吗？

有什么东西能更快的工作吗？

编辑:我已经环顾四周，发现了使用四叉树的一些问题。四叉树的工作方式有利于碰撞检测，但不是为了有效地进行最近邻搜索而设置的。https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-树看起来是一个更好的选择。https://en.wikipedia.org/wiki/R-tree

和

efficient way to handle 2d line segments

基于这些帖子，R树看起来像是赢家。同样方便地看到C++ Boost已经实现了它们。这看起来非常接近我计划做的事情，我将继续实现它，并验证结果。

Answer 1

编辑:自从我实现了PMR四叉树之后，我现在看到最近的邻居搜索比我描述的要复杂一些。如果搜索点的四搜索结果是空的，那么它就会变得更加复杂。我记得在汉南·萨梅斯的某个地方有一个描述:多维搜索结构。给出下面的答案，我想在一定的距离内搜索所有的物体。这对于PMR四叉树来说很容易，但是仅仅找到最接近的树就更复杂了。编辑端

我不会用R树的。

弱点(和强点！)在R-树上，空间被分割成矩形.

已知有三种算法可以实现这种分离，但没有一种算法适合于所有情况。R-树的实现非常复杂。那为什么要这么做？仅仅因为R-树在完美实现时可以比四叉树快两倍。四叉树和R-树之间的速度差异是不相关的.货币上的差别是。(如果两者都有工作代码，我将使用PMR四叉树，如果您只有R-树的代码，那么使用该代码，如果没有，则使用PMR四叉树)

四叉树(PMR)总是工作的，而且它们很容易实现。

使用PMR四叉树，您只需找到与搜索点相关的所有段。结果将是几个片段，然后你只需检查它们并准备就绪。

那些告诉四叉树不适合或邻居搜索的人，不知道有几百种不同的四叉树。不适合的只是一个点四叉树，而不是PMR一号，它存储包围盒。

我曾经记得关于在点四叉树中寻找邻接点的强迫描述。对于PMR-四叉树，我没有什么可做的(在指定的矩形间隔内进行搜索)，没有代码更改，只需迭代结果并找到最接近的结果。

我认为有更好的解决方案比四叉树或R-树为您的具体问题，但重点是，PMR总是有效的。只需实现一次，并使用如果所有的空间搜索。

Answer 2

由于需要测试的点数比多边形多，所以可以考虑对多边形进行相当广泛的预处理，以加快测试的平均数量，以找到每个点最近的直线段。

考虑这样一种方法(假设多边形没有洞)：

1. 遍历多边形的边缘，并沿每条等距线定义线段。
2. 测试线段的哪一侧一个点是限制最近的线段的潜在集。
3. 构建一个算术编码树，每个测试按线段的半空间所剔除的空间大小加权。这将提供良好的平均性能，以确定一个点的最近段，并打开了在多个点上同时进行并行测试的可能性。

这个图表应该说明这个概念。蓝线定义多边形，而红线是等距线。

注意，需要支持凹多边形大大增加了复杂性，如6-7-8区域所示。凹区域意味着延伸到无穷远的线段可以由任意相距较远的顶点定义。

你可以对这个问题进行分解，方法是在多边形上拟合一个凸包，然后对大多数点做一个快速的凸测试，并且只对凹区域的“影响区域”内的点做额外的工作，但我不确定是否有一种快速的方法来计算这个测试。

​

​

Answer 3

我不知道你提出的四叉树算法会有多棒，所以我会让其他人对此发表评论，但我想到了一些可能是快速和健壮的东西。

我的想法是，你可以用一个KD树来表示一个多边形(假设顶点是静态的)，然后找出最近的两个顶点，做一个最近的2邻域搜索，不管这个多边形中的点是什么。如果我的想法正确的话，这两个顶点应该是创建最近的线段的顶点，而不考虑凸性。