c++ - 快速查找点到多边形最近边的距离的方法

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-Trees 看起来是一个更好的选择。 https://en.wikipedia.org/wiki/R-tree

和

efficient way to handle 2d line segments

根据这些帖子，R 树看起来像是赢家。也很容易看到 C++ Boost 已经实现了它们。这看起来与我的计划非常接近，我将继续实现并验证结果。

Answer 1

编辑: 因为我已经实现了 PMR 四叉树，所以我现在看到，最近邻搜索比我描述的要复杂一些。 如果搜索点的四元搜索结果为空，那么它会变得更加复杂。 我记得 Hannan Sammets 某处的描述:Multidimensional search structure。 在给出下面的答案时，我想到了搜索指定距离内的所有对象。这对于 PMR 四叉树来说很容易，但仅仅找到最接近的就更复杂了。 编辑结束

我不会使用 R-Tree。
R 树的弱点(也是强点!)是将空间分成矩形。
已知有三种算法可以进行这种分离，但没有一种算法适合所有情况。 R 树实现起来真的很复杂。 那为什么要这样做呢？仅仅因为 R-Trees 在完美实现时可以比四叉树快两倍。四叉树和 R 树之间的速度差异无关紧要。货币差异是。 (如果你有两者的工作代码我会使用 PMR 四叉树，如果你只有 R-Tree 的代码然后使用它，如果你没有使用 PMR 四叉树)

四叉树 (PMR) 始终有效，并且易于实现。

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

告诉四叉树不适合或邻居搜索的人，不知道有数百种不同的四叉树。不适用性仅适用于点四叉树，不适用于存储边界框的 PMR。

我曾经记得在 POINT-Quadtree 中找到相邻点的复杂描述。对于 PMR-quadtree 我什么都不做(在指定的矩形区间内搜索)，没有代码更改，只是迭代结果并找到最接近的。

我认为对于您的特定问题，还有比四叉树或 R 树更好的解决方案，但关键是 PMR 始终有效。只需实现一次，然后将 if 用于所有空间搜索。