假设我已经用N个点构建了一个3D delaunay三角测量。 现在我有一个查询点，我需要找到包围查询点的三角测量的四面体。 如何以最快的方式做到这一点？ 我知道一般的八角树和kdtree方法，但我希望有一种快速的方法可以利用四面体不是任意的，而是3D delaunay的结果。
我可以使用 VTK 或 CGAL 或其他C++库，代码应该在C++中。
此示例演示如何使用 locate() 函数进行 CGAL 的 3D 三角测量。如果您需要加快位置而不是真正的施工速度，则可以将Delaunay_triangulation_3的参数LP放在CGAL::Fast_location。
提示：
在2D Delaunay的Green&Sibson方法中，他们通过从云的中心开始并沿着三角测量的边缘向目标实现对最近邻居的搜索。对于均匀的点分布，这会导致每次搜索产生 √N 次操作的成本。
我相信这个原则可以推广到四面体，并且对应于成本³√N。不如日志N，但无论如何都很有吸引力。如果查询点不是随机的，而是保持本地化的，则从上一个点开始可能会进一步减少查询时间。