c++ - 用于查找 3D 中最近三角形的数据结构

Question

我有一组三角形，我想找到距离空间中任意点最近的三角形。

我不喜欢蛮力方法太慢，因此我正在研究可以帮助加速搜索的各种数据结构。

我的问题是，我研究过的结构(rtree、kdtree)使用边界框来缩小搜索范围，但在许多情况下，最近的边界框不一定对应于最近的三角形。

这是一个这样的例子:

请注意蓝点如何最接近大边界框，但更接近绿色小三角形。这让我觉得依赖边界框的数据结构会导致不正确的搜索结果……除非我遗漏了一些明显的东西？

总的来说，我正在寻找一种轻量级的 C++ 解决方案(因此没有 CGAL 或其他强大的包)，或者只是指向我应该研究的正确算法类型。

谢谢!

Answer 1

您可以使用边界框方法来缩小搜索范围。您只需执行以下操作:

• 找到最近的边界框(假设它是您示例中的大边界框)
• 令 r 为点与最近边界框之间的距离，b 为边界框的大小。找到所有距离该点小于 (r+b) 的边界框。
• 使用蛮力在剩余的边界框中找到最近的三角形。