python - 给定一个点和大量的四面体，如何高效判断该点在哪个四面体中

Question

假设我们将点定义为三个浮点数的元组，而四面体定义为四个点的元组。

假设我们有一个四面体和一个点，我们可以按照 如何检查点是否在四面体中描述的解决方案来确定该点是否属于四面体？ 那里的关键思想是确定该点是否在四面体的四个侧面的内侧。

我的问题。给定一个点和 N 个四面体，其中 N 约为 700 万，我需要确定该点在哪个四面体中。我们将关心重复测试的性能，有大量的分数。

附加信息：

1. 可以使用上面提到的方法对这些四面体进行一一检查。但考虑到我有大量的四面体，这可能太慢了。

2. 问题设置中有一个特定的点。这些四面体是从用于解决医学成像问题的 FEM（有限元方法）问题中获得的（它们构成了患者的大脑）。也许 FEM 本身与这个问题无关，但我们可以利用这些四面体彼此相邻并且在这些四面体模拟的空间中没有“洞”这一事实。

3. 除了相邻的边界外，四面体没有交点。所以，这个问题应该有一个唯一的解决方案，除非在边界处，在这种情况下，可以让任何一个相交的四面体来回答我的问题。

4. 没有在输入上给出四面体的特定顺序。四面体的形状是否规则并没有规定。

关于有效解决问题的任何想法？Python 是解决这个问题的首选。

谢谢！

Answer 1

您可以首先过滤四面体，只保留边界长方体（与 X、Y 和 Z 轴平行）包含p的那些。这是更快的测试：

所以找到四面体 - 具有点t ₀、 t ₁、 t ₂和t ₃ —— 对于点p具有以下属性：

• ∃ i,j: t _i ^x ≤ p ^x ≤ t _j ^x
• ∃ i,j: t _i ^y ≤ p ^y ≤ t _j ^y
• ∃ i,j: t _i ^z ≤ p ^z ≤ t _j ^z

平均而言，这将只留下几个四面体（通常只有一两个），然后您可以使用它们来应用四面体点测试。

Answer 2

如果您计划针对同一组四面体测试很多点，我肯定会进行预处理步骤并为四面体构建空间结构。

在我的评论中我提到了八叉树，但是知道四面体填充空间（没有孔）我认为没有必要对空间进行自适应细分，最好将其分成相等的部分。

1. 将空间分成相等的盒子（让我们命名它们SpaceBoxes）。
2. 在每个SpaceBox中，保留与盒子碰撞的四面体列表。

• 为了加快速度，我会测试四面体的边界框，而不是四面体本身。
• 请注意，这一步可以相对便宜地完成 - 您知道 SpaceBox 具有相同的大小，您知道它们的位置，因此给定四面体的边界框，很容易找到 SpaceBox 候选者。

现在，有这个空间结构：

对于要测试的点p

• 找到对应的SpaceBoxO(1)
• 你有所有与 碰撞的四面体SpaceBox，所以这些是要测试的候选者
• p与每个四面体的边界框的第一次测试碰撞
• 只有这样，与四面体本身

请注意，测试的性能主要取决于每个 SpaceBox 中四面体的数量。

假设一个空间是一个立方体：

• 将每条边细分为 16 个部分，得到 16^3 = 4096 个 SpaceBoxes
• N = 7000000，应该有大约 1709 个候选四面体要测试

此外，在实现方面，预处理和测试多点看起来都像数据并行问题，因此多处理可能会有所帮助。