假设我们将一个点定义为元组三个浮点数的四面体和四个点的元组。
假设我们有一个四面体和一个点,我们可以确定根据中描述的解决方案,点属于四面体如何检查点是否在四面体中?这里的关键思想是确定该点是否在四面体的四个侧面的内侧。
我的问题给定一个点和N个四面体,其中N约为700万,我需要确定该点在哪个四面体中。我们会关心用大量点进行重复测试的性能。
附加信息:
-
使用上述方法可以逐个检查这些四面体。但考虑到我有大量的四面体,这可能太慢了。
-
问题设置中有一个特定点。这些四面体是从FEM(有限元法)问题中获得,用于求解医学成像问题(它们形成了患者的大脑)。也许FEM本身与这个问题无关,但我们可以利用这样一个事实,即这些四面体彼此相邻,并且这些四面体模拟的空间中没有"洞"。
-
四面体除了在相邻边界上没有交点。所以,这个问题应该有一个唯一的解,除非在边界上,在这种情况下,让相交的四面体中的任何一个都可以回答我的问题。
-
在输入上没有给出四面体的具体顺序。四面体的形状是否规则没有具体的说明。
对这个问题的有效解决方案有什么想法吗?Python是解决这个问题的首选。
谢谢!
您可以首先过滤四面体,只保留边界长方体(与X、Y和Z轴平行)包含p的四面体。这是更快的测试:
因此,找到四面体——点t0,t1、t2和t3——它们相对于点p具有以下性质:
- ∃i,j:tix≤px
jx - ∃i,j:tiy≤py≤tjy
- ∃i,j:tiz≤pz/sup>≤tjz
平均而言,这将只剩下几个四面体(通常只有一两个),然后您可以使用这些四面体来应用四面体测试中的点。
如果你计划针对同一组四面体测试很多点,我肯定会进行预处理步骤,为四面体构建空间结构。
在我的评论中,我提到了八叉树,但知道四面体填充了空间(没有洞),我认为没有必要对空间进行自适应细分,最好将其等分。
- 将空间划分为相等的框(将其命名为
SpaceBoxes
) - 在每个
SpaceBox
中,保留一个与长方体碰撞的四面体列表
- 为了加快速度,我会测试四面体的边界框,而不是四面体本身
- 请注意,这一步骤可以相对便宜地完成——你知道SpaceBox的大小相等,你知道它们的位置,所以给定四面体的边界框,很容易找到SpaceBox的候选者
现在,有了这个空间结构:
对于待测点p
- 找到相应的
SpaceBox
O(1) - 所有四面体都和
SpaceBox
碰撞,所以这些都是要测试的候选者 - CCD_ 6与每个四面体的边界盒的首次测试碰撞
- 只有这样,四面体本身
请注意,测试的性能主要取决于每个SpaceBox中四面体的数量。
假设一个空间是一个立方体:
- 将每条边细分为16个部分,得到16^3=4096个空格
- 当N=7000000时,应该有大约1709个候选四面体需要测试
此外,在实现方面,预处理和测试多个点看起来都像是数据并行问题,因此多处理可能会有所帮助。
将四面体放入三维R树中,使其边界框为键,四面体本身为值。查询该点上的R-树。然后用四面体检查中的点测试查询返回的每个结果值。
使用R-树(或类似的结构)的好处是,如果四面体没有改变,你可以构建一次R-树并测试多个点。