找到四面體內的整數座標的所有點

Question

我想找到所有與整數座標位於四面體內（我想以某種方式能夠通過它們循環）的點。我知道定義四面體的四個點（A，B，C，D）的座標。

我現在正在做的是我找到四面體的邊界框（A，B，C，D的最小和最大x，y，z座標），然後通過循環遍歷所有點邊界框。對於每一個這樣的點，我計算重心座標（使用the equations from Wikipedia）並檢查點是否在四面體內（如果任何重心座標爲負值或大於1，則該點不在裏面）。

有沒有更好的方法來做到這一點？目前，我正在測試的點（從邊界框）出現在四面體內的機會大約有1/6，所以我認爲我做了太多不必要的計算。

我正在使用通過三角測量更大體積（我擴大體積並希望使用四面體插值插值缺失值）生成的四面體列表。我沒有使用任何外部庫。

Answer 1

另一個想法用於改進：如果一個 「杆」 parrallel到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個循環。

Answer 2

你的方法是正確的。有一些可能的優化，這可能是值得的或不取決於要求。例如：

有一種更簡單的方法來檢查給定的點是在四面體的內部還是外部。 它相當於檢查該點對於四面體的四條邊中的每一條所屬的半空間：

每條邊都由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次加法。