algorithm - 三角形曲面上有一个点，如何找到包含该点的三角形？

Question

我们有一个 3d 三角面，上面有一个点。我怎样才能找到包含该点的三角形。我们可以通过测试所有三角形来找到，但这是一种缓慢的方式。我必须让算法更快。

有没有什么搜索算法或者有什么缩小搜索区域的技巧？

Answer 1

您需要的是 spatial data structure ，它们允许 computational geometry 的那些典型查询.您的点是一组三角形的查询点。

例如，您可以计算 minimal bounding box对于每个三角形并将它们存储到 R-tree 中(保留哪个 mbb 对应哪个三角形的 map ，或者将这些三角形作为 R 树中的叶节点)然后快速查找最佳边界框可能不会给你最终结果，但我认为它会提供很多缩小的搜索区域(匹配的 mbb 列表导致三角形候选列表)，然后您可以在其中快速搜索确切的三角形(因为边界框和三角形有点不同)。