给定一个点和大量四面体，如何高效判断该点在哪个四面体中
Given a point and a large number of tetrahedrons, how to efficiently determine in which tetrahedron the point is
假设我们定义一个点为一个元组
三个浮点数，一个四面体一个四点元组。
假设我们有一个四面体和一个点，我们可以确定
点属于遵循中描述的解决方案的四面体
How to check whether the point is in the tetrahedron or not?
这里的核心思想是判断该点是否在四面体四个侧面的内侧。
我的问题。给定一个点和N个四面体，其中N约为700万，我需要确定该点在哪个四面体中。我们会关心做重复测试的性能，有大量的点。
附加信息：
用上面提到的方法一个一个检查这些四面体就可以了。但这可能太慢了，因为我有大量的四面体。
问题设置中有一个具体的点。这些四面体是
从 FEM（有限元法）问题中获得，用于求解
医学成像问题（它们构成了患者的大脑）。也许 FEM 本身与这个问题无关，但我们可以利用这些四面体彼此相邻并且这些四面体模拟的 space 中没有“孔”的事实。
四面体除了相邻边界外没有交点。所以，这个问题应该有一个唯一的解决方案，除非在边界处，在这种情况下，我的问题的答案可以是相交的四面体中的任何一个。
输入中没有给出四面体的特定顺序。四面体的形状是否规则没有规定
关于有效解决问题的任何想法？ Python解决此题优先
谢谢！
您可以先过滤四面体，只保留边界长方体（与 X、Y 和 Z 轴平行）包含 p 的那些。这样测试速度更快：
所以找到四面体 -- 点 t0, t1, t2 , 和 t3 -- 相对于点有以下 属性 p:
- ∃ i,j: tix ≤ px ≤ tjx
- ∃ i,j: tiy ≤ py ≤ tjy
- ∃ i,j: tiz ≤ pz ≤ tjz
平均而言，这只会给您留下几个四面体（通常只有一两个），然后您可以使用这些四面体来应用 point-in-tetrahedron 测试。
如果您打算针对同一组四面体测试很多点，我肯定会进行预处理步骤并为四面体构建空间结构。
在我的评论中我提到了八叉树，但是知道四面体填充space（没有空洞）我认为不需要自适应细分space，最好将其分成相等的部分。
- 将 space 分成相等的方框（让它们命名为
SpaceBoxes）。
- 在每个
SpaceBox 中，保留一个与盒子碰撞的四面体列表。
- 为了加快速度，我会测试四面体的边界框，而不是四面体本身。
- 请注意，这一步可以相对便宜地完成 - 你知道 SpaceBoxes 具有相同的大小，你知道它们的位置，所以给定四面体的边界框，很容易找到候选 SpaceBox。
现在，有了这个空间结构：
待测点p
- 找到对应的
SpaceBoxO(1)
- 你有所有与
SpaceBox 碰撞的四面体，所以这些是要测试的候选对象
p 与每个四面体的边界框的第一次测试碰撞- 只有这样，四面体本身
请注意，测试的性能主要取决于每个 SpaceBox 中四面体的数量。
假设 space 是一个立方体：
- 将每条边细分为 16 个部分，得到 16^3 = 4096 个 SpaceBoxes
- N = 7000000，应该有大约 1709 个候选四面体要测试
此外，在实现方面，预处理和测试多点看起来像 data-parallel 问题，因此多处理可能会有所帮助。
假设我们定义一个点为一个元组 三个浮点数，一个四面体一个四点元组。
假设我们有一个四面体和一个点，我们可以确定 点属于遵循中描述的解决方案的四面体 How to check whether the point is in the tetrahedron or not? 这里的核心思想是判断该点是否在四面体四个侧面的内侧。
我的问题。给定一个点和N个四面体，其中N约为700万，我需要确定该点在哪个四面体中。我们会关心做重复测试的性能，有大量的点。
附加信息：
用上面提到的方法一个一个检查这些四面体就可以了。但这可能太慢了，因为我有大量的四面体。
问题设置中有一个具体的点。这些四面体是 从 FEM（有限元法）问题中获得，用于求解 医学成像问题（它们构成了患者的大脑）。也许 FEM 本身与这个问题无关，但我们可以利用这些四面体彼此相邻并且这些四面体模拟的 space 中没有“孔”的事实。
四面体除了相邻边界外没有交点。所以，这个问题应该有一个唯一的解决方案，除非在边界处，在这种情况下，我的问题的答案可以是相交的四面体中的任何一个。
输入中没有给出四面体的特定顺序。四面体的形状是否规则没有规定
关于有效解决问题的任何想法？ Python解决此题优先
谢谢！
您可以先过滤四面体，只保留边界长方体（与 X、Y 和 Z 轴平行）包含 p 的那些。这样测试速度更快：
所以找到四面体 -- 点 t0, t1, t2 , 和 t3 -- 相对于点有以下 属性 p:
- ∃ i,j: tix ≤ px ≤ tjx
- ∃ i,j: tiy ≤ py ≤ tjy
- ∃ i,j: tiz ≤ pz ≤ tjz
平均而言，这只会给您留下几个四面体（通常只有一两个），然后您可以使用这些四面体来应用 point-in-tetrahedron 测试。
如果您打算针对同一组四面体测试很多点，我肯定会进行预处理步骤并为四面体构建空间结构。
在我的评论中我提到了八叉树，但是知道四面体填充space（没有空洞）我认为不需要自适应细分space，最好将其分成相等的部分。
- 将 space 分成相等的方框（让它们命名为
SpaceBoxes）。 - 在每个
SpaceBox中，保留一个与盒子碰撞的四面体列表。
- 为了加快速度，我会测试四面体的边界框，而不是四面体本身。
- 请注意，这一步可以相对便宜地完成 - 你知道 SpaceBoxes 具有相同的大小，你知道它们的位置，所以给定四面体的边界框，很容易找到候选 SpaceBox。
现在，有了这个空间结构：
待测点p
- 找到对应的
SpaceBoxO(1) - 你有所有与
SpaceBox碰撞的四面体，所以这些是要测试的候选对象 p与每个四面体的边界框的第一次测试碰撞- 只有这样，四面体本身
请注意，测试的性能主要取决于每个 SpaceBox 中四面体的数量。
假设 space 是一个立方体：
- 将每条边细分为 16 个部分，得到 16^3 = 4096 个 SpaceBoxes
- N = 7000000，应该有大约 1709 个候选四面体要测试
此外，在实现方面，预处理和测试多点看起来像 data-parallel 问题，因此多处理可能会有所帮助。