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



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

假设我们有一个四面体和一个点,我们可以确定根据中描述的解决方案,点属于四面体如何检查点是否在四面体中?这里的关键思想是确定该点是否在四面体的四个侧面的内侧。

我的问题给定一个点和N个四面体,其中N约为700万,我需要确定该点在哪个四面体中。我们会关心用大量点进行重复测试的性能。

附加信息:

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

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

  3. 四面体除了在相邻边界上没有交点。所以,这个问题应该有一个唯一的解,除非在边界上,在这种情况下,让相交的四面体中的任何一个都可以回答我的问题。

  4. 在输入上没有给出四面体的具体顺序。四面体的形状是否规则没有具体的说明。

对这个问题的有效解决方案有什么想法吗?Python是解决这个问题的首选。

谢谢!

您可以首先过滤四面体,只保留边界长方体(与X、Y和Z轴平行)包含p的四面体。这是更快的测试:

因此,找到四面体——点t0,t1、t2t3——它们相对于点p具有以下性质:

  • i,j:tix≤pxjx
  • i,j:tiy≤py≤tjy
  • i,j:tiz≤pz/sup>≤tjz

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

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

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

  1. 将空间划分为相等的框(将其命名为SpaceBoxes)
  2. 在每个SpaceBox中,保留一个与长方体碰撞的四面体列表
  • 为了加快速度,我会测试四面体的边界框,而不是四面体本身
  • 请注意,这一步骤可以相对便宜地完成——你知道SpaceBox的大小相等,你知道它们的位置,所以给定四面体的边界框,很容易找到SpaceBox的候选者

现在,有了这个空间结构:

对于待测点p

  • 找到相应的SpaceBoxO(1)
  • 所有四面体都和SpaceBox碰撞,所以这些都是要测试的候选者
  • CCD_ 6与每个四面体的边界盒的首次测试碰撞
  • 只有这样,四面体本身

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

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

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

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

将四面体放入三维R树中,使其边界框为键,四面体本身为值。查询该点上的R-树。然后用四面体检查中的点测试查询返回的每个结果值。

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

相关内容

  • 没有找到相关文章

最新更新