tha*_*ius 11 c++ algorithm polygon quadtree r-tree
建立
对于函数实现,我知道一个简单的方法是使用标准距离到线段公式来测试到多边形的所有段的距离.这个选项规模相当慢,我相信应该有更好的选择.
我的直觉是,对于这种类型的功能应该有一些非常快速已知的算法,这些算法可以在游戏引擎中实现,但我不知道在哪里看.
我找到了一个用于在四叉树中存储线段的参考,这将提供非常快速的搜索,我认为它可以用于我的目的,以快速缩小哪个段看作最近的段然后只需要计算到一个线段的距离. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf
我无法找到任何代码示例来说明这将如何工作.我不介意从头开始实现算法,但是如果存在一个可用的,经过测试的代码库,那么就不会明白这一点.
我一直在寻找几个四叉树实现,我认为它的工作方式是每个多边形创建一个四叉树,并将每个多边形的线段与一个边界框插入到该多边形的四叉树中.
我将要制作的函数的"查询"部分将包括创建一个点作为一个非常小的边界框,然后将其用于搜索四叉树结构,然后只能找到多边形的最接近的部分.
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
和
基于这些帖子,R树看起来像赢家.也很方便看到C++ Boost已经实现了它们.这看起来足够接近我计划做的事情,我将继续实施并验证结果.
编辑： 由于我已经实现了 PMR 四叉树，所以我现在看到，最近邻搜索比我描述的要复杂一些。如果搜索点的四边形搜索结果为空，那么它会变得更加复杂。我记得 Hannan Sammets 中某处的描述：多维搜索结构。给出下面的答案时，我想到的是搜索指定距离内的所有物体。这对于 PMR 四叉树来说很容易，但仅仅找到最接近的就更复杂了。 编辑结束
我不会使用 R 树。
R 树的弱点（也是优点！）是将空间分成矩形。
已知三种算法可以进行这种分离，但没有一种算法适合所有情况。R 树的实现非常复杂。那为什么还要这么做呢？只是因为在完美实现时，R 树可以比四叉树快两倍。四叉树和 R 树之间的速度差异并不相关。货币差异是。（如果您有两者的工作代码，我会使用 PMR 四叉树，如果您只有 R 树的代码，则使用它，如果没有，则使用 PMR 四叉树）
四叉树 (PMR) 始终有效，而且实现起来很简单。
使用 PMR 四叉树，您只需找到与搜索点相关的所有段。结果将是几个片段，然后您只需检查它们即可。
人们告诉四叉树不适合或邻居搜索，不知道有数百种不同的四叉树。这种不适用性只适用于点四叉树，不适用于存储边界框的 PMR 树。
我曾经记得在点四叉树中查找邻居点的复杂描述。对于 PMR-四叉树，我没有什么可做的（对于指定矩形间隔内的搜索），没有代码更改，只需迭代结果并找到最接近的。
我认为对于您的具体问题，有比四叉树或 R 树更好的解决方案，但重点是 PMR 始终有效。只需实现一次并使用 if 进行所有空间搜索。