在四面体内找到所有整数坐标点

Question

我正在尝试找到所有坐标为整数的点，这些点位于四面体内部（我想通过某种方式循环遍历它们）。我知道定义四面体的四个点（A、B、C、D）的坐标。

目前我的做法是找到四面体的边界框（A、B、C、D的最小和最大x、y、z坐标），然后在边界框内循环遍历所有点。对于每个这样的点，我计算重心坐标（使用维基百科上的方程式），并检查该点是否在四面体内（如果任何一个重心坐标为负或大于1，则该点不在内部）。

有更好的方法吗？目前测试的点（来自边界框）实际位于四面体内部的概率约为1/6，因此我认为我做了太多不必要的计算。

我正在使用由剖分更大体积而生成的四面体列表（我正在扩展该体积并希望使用四面体插值来进行缺失值的插值）。我没有使用任何外部库。

- ppalasek

Answer 1

您的方法是正确的。有一些可能的优化，这取决于需求是否值得尝试。例如：

检查给定点是在四面体内还是外部有更简单的方法。 它相当于检查点相对于四面体的每个边所属的哪个半空间：

每条边由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次加法。

- Petar Ivanov

---

你还可以缩放平面方程，使得在平面上$F$的值为零，在相对顶点处为1。这样所有有效点都满足$0<=F(x,y,z)<=1$，这意味着你可以舍弃更多的点。 - Michael Anderson

Answer 2

改进的另一个想法：

检查是否有一根与z轴平行的“杆”（即x=4，y=6），穿过四面体。如果没有，那么没有(x = 4，y = 5，z)的值可以在内部。

否则，找出杆子与四面体边缘相交的地方（通过找出组成四面体边缘的平面相交的位置）。

假设这些平面在z = 1.3和z = 10.04相交。然后您就知道所有点(4,5,2)到(4,5,10)都在里面。

对于所有的x和y值重复此过程。

实际上，这应该更快，因为它将节省1个循环。

- willem