computational-geometry - kd 树是否适合保留三角形，或者我需要对经典的 kd 树构建算法进行一些更改？

Question

我在 wiki 中阅读了 kd 树描述，wiki 说 kd 树保留点。我有三角形网格，需要一些结构来有效计算与圆柱体的交点和点到点的距离查询。据我了解，如果我按平面分割网格 - 许多三角形可以与该平面相交。那我该怎么办？将三角形的副本放在左右子框中，还是分割相交的三角形？

Answer 1

您需要拆分相交的三角形。查看任何使用 KD-Trees 的开源光线追踪算法以了解如何执行此操作，或在 Google Scholar 上搜索学术论文。

查看 Surface Area Heuristic 以了解选择分割平面的好方法，它通常用于光线追踪，但它可能适用于您的情况。