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

Question

假设我们将一个点定义为一个元组三个 float 组成，四面体由四个点组成。

假设我们有一个四面体和一个点，我们可以确定是否点属于下面描述的解决方案的四面体 How to check whether the point is in the tetrahedron or not?这里的关键思想是确定该点是否在四面体四个侧面的内侧。

我的问题。给定一个点和 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

平均而言，这将只留下几个四面体(通常只有一两个)，然后您可以使用这些四面体来应用四面体中的点测试。