四面体网格中的点定位是否有任何经过验证的数据结构，其中四面体都是不相交但彼此“接触”的？ IE。大多数面孔恰好是两个四面体的面孔。
位置我的意思是我想找出给定点位于哪个四面体中，或者它是否不位于任何四面体中。
到目前为止，我已经尝试过:
一个简单的 KD 树。这对我的需求来说太慢了，因为平均树深度非常高，而且我仍然有很多单独的四面体要在每片叶子中进行测试。
包含每个单元格的所有相交四面体的网格。这似乎工作得更好，但仍然不够快。首先，网格包含很多空单元格，因为我的整体网格不是很“四四方方”。其次，实际上确实包含四面体的大多数细胞确实包含很多(10+)。我想这是因为很多四面体共享每个顶点，一旦一个顶点在一个单元格中，它所有相邻的四面体也是如此。
关于输入数据的一些进一步信息:网格通常不是凸面的，可能有孔洞或夹杂物。尽管后两个不太可能，但我必须处理它们，这使得在没有(昂贵且复杂的？)预处理的情况下“行走”是不可能的。
最佳答案
如果您正在处理由具有邻接信息的四面体组成的 3D 三角剖分，您可以只使用行走。这是点定位的标准技术，使用 3D 方向测试。
有关详细信息，请参阅 Olivier Devillers 等人的论文在三角剖分中行走。 (谷歌它，你会找到它的 PDF。)
关于algorithm - 四面体网格中的点位置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11849435/