快速查找点到多边形最近边的距离的方法
Fast method to find distance from point to closest edge of polygon
设置
- 函数需要提供点到多边形最近边的距离
- 已知点位于多边形内部
- 多边形可以是凸的也可以是凹的
- 需要测试很多点（百万）
- 许多单独的多边形（几十个）将需要 运行 通过每个点的函数
- 预先计算和持久存储的数据结构是一种选择。
- 最终的搜索功能将在 C++ 中实现
对于函数实现，我知道一个简单的方法是使用到线段的标准距离公式来测试到多边形所有线段的距离。这个选项在规模上会相当慢，我相信应该有更好的选择。
我的直觉是，对于这种类型的函数，应该有一些非常快速的已知算法可以在游戏引擎中实现，但我不确定去哪里找。
我找到了一个在四叉树中存储线段的参考，它可以提供非常快速的搜索，我认为它可以用于我的目的，以快速缩小将哪个线段视为最近线段的范围，并且那么只需要计算到一条线段的距离。
https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf
我找不到任何代码示例来说明它是如何工作的。我不介意从头开始实施算法，但如果存在有效的、经过测试的代码库，我不认为这样做有什么意义。
我一直在研究几个四叉树的实现，我认为它的工作方式是为每个多边形创建一个四叉树，然后将每个多边形的线段和一个边界框插入到该多边形的四叉树中。
我将要创建的函数的 "query" 部分将包括创建一个点作为一个非常小的边界框，然后将用于搜索四叉树结构，四叉树结构将只找到多边形最接近的部分。
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
和
我真正的问题是，对于快速搜索时间函数来说，这看起来是一种合理的方法吗？
有什么东西可以更快地工作吗？
编辑：
我一直在环顾四周，发现使用四叉树存在一些问题。四叉树的工作方式有利于碰撞检测，但并未设置为允许有效的最近邻搜索。
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 已经实现了它们。这看起来与我计划做的非常接近，我将继续实施并验证结果。
我不确定你提出的四叉树算法会有多好，所以我会让其他人对此发表评论，但我有一个想法可能是快速和健壮的。
我的想法是你可以用 KD 树表示一个多边形（假设顶点在时间上是静态的）然后找到最近的两个顶点，进行最近的 2 邻域搜索，无论点在哪个点这个多边形。如果我的想法是正确的，这两个顶点应该是创建最近线段的顶点，而不考虑凸性。
编辑：
因为我已经实现了 PMR 四叉树，所以我现在看到，最近邻搜索比我描述的要复杂一些。
如果搜索点的四元搜索结果为空，那么它会变得更加复杂。
我记得 Hannan Sammets:Multidimensional 搜索结构中某处的描述。
在给出下面的答案时，我想到了搜索指定距离内的所有对象。这对于 PMR 四叉树来说很容易，但仅仅找到最接近的就更复杂了。
编辑结束
我不会使用 R 树。
R 树的弱点（也是强点！）是将 space 分成矩形。
已知有三种算法可以进行这种分离，但 none 非常适合所有情况。
R 树实现起来真的很复杂。
那为什么要这样做呢？仅仅因为 R-Trees 在完美实现时可以比四叉树快两倍。四叉树和 R 树之间的速度差异无关紧要。货币差异是。 （如果你有两者的工作代码，我会使用 PMR 四叉树，如果你只有 R-Tree 的代码，那么使用它，如果你有 none 使用 PMR 四叉树）
四叉树 (PMR) 始终有效，并且易于实现。
使用PMR四叉树，您只需找到与搜索点相关的所有线段。结果将是几段，然后您只需检查它们并准备就绪。
告诉四叉树不适合或邻居搜索的人，不知道有数百种不同的四叉树。不适用性仅适用于点四叉树，不适用于存储边界框的 PMR。
我曾经记得在 POINT-Quadtree 中找到邻居点的复杂描述。对于PMR-quadtree我没有做任何事情（在指定的矩形区间内搜索），没有代码更改，只是迭代结果并找到最接近的。
我认为对于您的特定问题，还有比四叉树或 R 树更好的解决方案，但关键是 PMR 始终有效。只需实施一次，然后将 if 用于所有空间搜索。
由于要测试的点比多边形多得多，您可以考虑对多边形进行一些相当广泛的预处理，以加快平均测试次数以找到每个点的最近线段。
考虑这样的方法（假设多边形没有孔）：
- 遍历多边形的边缘并沿每条等距线定义线段
- 测试一个点在线段的哪一边来限制最近线段的潜在集合
- 构建一个算术编码树，每个测试的权重为 space 的数量，该数量被线段的一半 - space 剔除。这应该在确定一个点的最近线段时提供良好的平均性能，并开启一次对多个点进行并行测试的可能性。
这张图应该能说明这个概念。蓝线定义多边形，红线是等距线。
请注意，需要支持凹多边形会大大增加复杂性，如 6-7-8 区域所示。凹区域意味着延伸到无穷远的线段可以由任意远的顶点定义。
您可以通过将凸包拟合到多边形然后对大多数点进行快速凸测试并仅对凹区域 "region of influence" 内的点进行额外工作来分解此问题，但我不确定是否有快速计算该测试的方法。
设置
- 函数需要提供点到多边形最近边的距离
- 已知点位于多边形内部
- 多边形可以是凸的也可以是凹的
- 需要测试很多点（百万）
- 许多单独的多边形（几十个）将需要 运行 通过每个点的函数
- 预先计算和持久存储的数据结构是一种选择。
- 最终的搜索功能将在 C++ 中实现
对于函数实现，我知道一个简单的方法是使用到线段的标准距离公式来测试到多边形所有线段的距离。这个选项在规模上会相当慢，我相信应该有更好的选择。
我的直觉是，对于这种类型的函数，应该有一些非常快速的已知算法可以在游戏引擎中实现，但我不确定去哪里找。
我找到了一个在四叉树中存储线段的参考，它可以提供非常快速的搜索，我认为它可以用于我的目的，以快速缩小将哪个线段视为最近线段的范围，并且那么只需要计算到一条线段的距离。 https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf
我找不到任何代码示例来说明它是如何工作的。我不介意从头开始实施算法，但如果存在有效的、经过测试的代码库，我不认为这样做有什么意义。
我一直在研究几个四叉树的实现，我认为它的工作方式是为每个多边形创建一个四叉树，然后将每个多边形的线段和一个边界框插入到该多边形的四叉树中。
我将要创建的函数的 "query" 部分将包括创建一个点作为一个非常小的边界框，然后将用于搜索四叉树结构，四叉树结构将只找到多边形最接近的部分。
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
和
我真正的问题是，对于快速搜索时间函数来说，这看起来是一种合理的方法吗？
有什么东西可以更快地工作吗？
编辑： 我一直在环顾四周，发现使用四叉树存在一些问题。四叉树的工作方式有利于碰撞检测，但并未设置为允许有效的最近邻搜索。 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 已经实现了它们。这看起来与我计划做的非常接近，我将继续实施并验证结果。
我不确定你提出的四叉树算法会有多好，所以我会让其他人对此发表评论，但我有一个想法可能是快速和健壮的。
我的想法是你可以用 KD 树表示一个多边形（假设顶点在时间上是静态的）然后找到最近的两个顶点，进行最近的 2 邻域搜索，无论点在哪个点这个多边形。如果我的想法是正确的，这两个顶点应该是创建最近线段的顶点，而不考虑凸性。
编辑： 因为我已经实现了 PMR 四叉树，所以我现在看到，最近邻搜索比我描述的要复杂一些。 如果搜索点的四元搜索结果为空，那么它会变得更加复杂。 我记得 Hannan Sammets:Multidimensional 搜索结构中某处的描述。 在给出下面的答案时，我想到了搜索指定距离内的所有对象。这对于 PMR 四叉树来说很容易，但仅仅找到最接近的就更复杂了。 编辑结束
我不会使用 R 树。
R 树的弱点（也是强点！）是将 space 分成矩形。
已知有三种算法可以进行这种分离，但 none 非常适合所有情况。
R 树实现起来真的很复杂。
那为什么要这样做呢？仅仅因为 R-Trees 在完美实现时可以比四叉树快两倍。四叉树和 R 树之间的速度差异无关紧要。货币差异是。 （如果你有两者的工作代码，我会使用 PMR 四叉树，如果你只有 R-Tree 的代码，那么使用它，如果你有 none 使用 PMR 四叉树）
四叉树 (PMR) 始终有效，并且易于实现。
使用PMR四叉树，您只需找到与搜索点相关的所有线段。结果将是几段，然后您只需检查它们并准备就绪。
告诉四叉树不适合或邻居搜索的人，不知道有数百种不同的四叉树。不适用性仅适用于点四叉树，不适用于存储边界框的 PMR。
我曾经记得在 POINT-Quadtree 中找到邻居点的复杂描述。对于PMR-quadtree我没有做任何事情（在指定的矩形区间内搜索），没有代码更改，只是迭代结果并找到最接近的。
我认为对于您的特定问题，还有比四叉树或 R 树更好的解决方案，但关键是 PMR 始终有效。只需实施一次，然后将 if 用于所有空间搜索。
由于要测试的点比多边形多得多，您可以考虑对多边形进行一些相当广泛的预处理，以加快平均测试次数以找到每个点的最近线段。
考虑这样的方法（假设多边形没有孔）：
- 遍历多边形的边缘并沿每条等距线定义线段
- 测试一个点在线段的哪一边来限制最近线段的潜在集合
- 构建一个算术编码树，每个测试的权重为 space 的数量，该数量被线段的一半 - space 剔除。这应该在确定一个点的最近线段时提供良好的平均性能，并开启一次对多个点进行并行测试的可能性。
这张图应该能说明这个概念。蓝线定义多边形，红线是等距线。
请注意，需要支持凹多边形会大大增加复杂性，如 6-7-8 区域所示。凹区域意味着延伸到无穷远的线段可以由任意远的顶点定义。
您可以通过将凸包拟合到多边形然后对大多数点进行快速凸测试并仅对凹区域 "region of influence" 内的点进行额外工作来分解此问题，但我不确定是否有快速计算该测试的方法。