math - 查找四面体内具有整数坐标的所有点

Question

我试图找到所有位于四面体内部的整数坐标点(我希望以某种方式能够遍历它们)。我知道定义四面体的四个点(A、B、C、D)的坐标。

我目前正在做的是找到四面体的边界框(A、B、C、D 的最小和最大 x、y、z 坐标)，然后循环遍历边界框内的所有点。对于每个这样的点，我计算重心坐标(使用 the equations from Wikipedia )并检查该点是否在四面体内部(如果任何重心坐标为负或大于 1，则该点不在四面体内部)。

有一个更好的方法吗？目前大约有 1/6 的机会我正在测试的点(从边界框)真的位于四面体内部，所以我认为我做了太多不必要的计算。

我正在处理通过对更大体积进行三角测量生成的四面体列表(我正在扩展体积并希望使用四面体插值法插入缺失值)。我没有使用任何外部库。

Answer 1

你的方法是正确的。有一些可能的优化，根据需求可能值得或不值得。例如:

有一种更简单的方法可以检查给定点是在四面体的内部还是外部。
它相当于检查该点相对于四面体的 4 个边中的每一个属于哪个半空间:

每边由 3 个点定义(例如 A、B、C)。那么平面法线是 (C-A)x(B-A) (即平面中向量的叉积)。如果这个坐标是(a,b,c)，那么平面方程是F(x,y,z) = ax+by+cz = 0 .对于给定的点 (x0, y0, z0)，F(x0,y0,z0) 的符号决定了这些点属于哪个半平面。

关键是您可以预先计算四面体每一边的平面方程以及对应于“外部”的符号，然后检查给定点最多相当于进行 4 次评估(每侧一个)，每次取3 次乘法和 2 次加法。