如何在C ++中找出给定点是否在3d区域的内部/外部？

Question

我有一个由网格（点和连通性）定义的3d区域。我有一个点（x，y，z）。需要检查此点是在3D区域的内部/外部还是在表面上。寻找优化的解决方案，因为我需要检查C ++中的数百万个点。

我尝试使用立体角方法，但它非常慢。请为此建议任何算法或方法。

Answer 1

假设您的网格是四面体网格，您可以使用：

1. 找到可能承受这一点的四面体子集。也就是说，尽可能多地排除候选人。您可以通过使用八叉树或kd树等结构来实现。
2. 对于剩下的所有四面体，计算相对于给定四面体的点的重心坐标。如果任何坐标为负，则它位于外部。

可以通过计算相对于该点的子四面体的体积然后将该体积除以总体积来计算重心坐标。你会发现快速搜索的公式。

编辑：Barycentric coordinates of a tetrahedron就是一个例子。

（也就是说，总是有很多优化空间 - 最好找到一个很好的库来为你做这个。例如，如果你想要并行计算，你需要一些实验来找出用于当前处理器和给定网格的完美核心数量。通常它不是最大值。）

如果你的网格由八面体（“不均匀的立方体”）组成，你需要求解一个线性方程组。多面体越复杂，公式就越复杂。对于一般的凸多面体，最好的方法可能是为每个面计算一半空间，以便多面体是这些半空间的交点，然后看看这些点是否位于所有半空间中。