给定一个点和大量的四面体，如何有效地确定该点在哪个四面体中是

Question

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

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

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

更多信息：

1. 可以用上述方法逐个检查这些四面体。但考虑到我的四面体数量很大，这可能太慢了。--

1. 在问题设置中有一个特定的点。这些四面体是从一个有限元()问题中得到的，用于解决医学成像问题(它们构成病人的大脑)。也许有限元本身与这个问题无关，但我们可以利用这样一个事实，即这些四面体是相邻的，并且在这些tetrahedrons.

模拟的空间中没有“洞”。

，

1. ，四面体，除了它们相邻的边界外，它们没有交点。因此，这个问题应该有一个唯一的解决方案，除非在边界，在这种情况下，有一个交叉四面体的答案我的问题。

。

1. 没有给出输入四面体的特定顺序。没有关于四面体形状是否规则的说明。

对这个问题有什么有效的解决办法吗？在解决这个问题方面，Python是首选。

谢谢!

Answer 1

如果你计划在同一组四面体上测试很多点，我肯定会用预处理的步骤来构建四面体的空间结构。

在我的评论中，我提到了八进制，但知道四面体填充了空间(没有洞)，我认为没有必要对空间进行自适应细分，最好将其划分为相等的部分。

SpaceBoxes).

• In

• 将空间分成等号框(让它们命名为SpaceBox，保存一个四面体列表，这些四面体与box.

• To加速碰撞)，我将测试四面体的包围盒，而不是四面体本身。
• 注意到，这个步骤可以做得比较便宜--您知道SpaceBoxes有相同的大小，您知道它们的位置，所以给定四面体的包围框，很容易找到SpaceBox候选。

现在，具有这样的空间结构：

需要测试的点，p

tetrahedron

• only

• 找到相应的SpaceBox O(1)

• --所有四面体都与SpaceBox碰撞，所以这些都是测试

• 的候选条件，首先测试p与每个SpaceBox的包围盒的碰撞，然后再用四面体自身H 226F 227

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

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

SpaceBoxes

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

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

Answer 2

将四面体放入三维R-树，使它们的包围盒成为键，而四面体本身就是值。在这一点上查询R树。然后用四面体点检查测试查询返回的每个结果值。

使用R树(或类似结构)的好处是，如果四面体不改变，您可以构建R树一次并测试多个点。