我正在开发一个小项目，需要我快速找到一组三角形中的哪些三角形部分或全部包含在给定的矩形区域内。我对优化快速搜索感兴趣 - 我不受内存限制。
这不是我太熟悉的领域，因此到目前为止我所能做的就是在 Google 上查找处理此问题的标准算法。到目前为止，我最接近的是使用两个区间树。这有点笨拙，因为我必须在 x 和 y 两个方向上对每个三角形的边缘与矩形区域的边缘之间的间隔重叠进行测试。
有人可以向我指出处理此问题的“正确”方法的任何资源吗？
谢谢!
编辑:我忘了提及我当前使用的矩形区域平行于坐标轴 x 和 y。目前，我对任何利用此限制的解决方案感到满意。不过，一般来说，了解具有完全任意矩形的解决方案会很不错。
最佳答案
您可以使用 AABBTree(AABB 代表轴对齐边界框树)， 想法是将每个三角形包围在其轴对齐的边界框中，然后构建一棵树，该树将初始三角形作为叶子，并且其中上部节点具有一个边界框，该边界框是其子级边界框的并集。然后，当搜索哪些三角形与“某物”有非空交集时，检查“某物”是否与节点的边界框有交集，并在这种情况下沿着树向下测试其子节点(递归函数)。
您可以在以下位置找到 AABBTree 的高效实现:
关于在区域内查找三角形的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32575538/