測試三維點是否在三維多面體內

Question

給定由三角網格表示的邊界定義的三維多面體，我如何實現一個算法來確定給定的三維點是否屬於多面體的內部？

Answer 1

有幾種實現此功能的方法。

最簡單的方法是創建一個從點開始並指向任意方向的無限射線（或非常長的線段），然後計算射線與三角形之間的交點數。如果交點的數量是奇數，則該點位於多面體內。

Inside(Polyhedron P, point q) 
    Segment S = [q, q+(0,0,1e30)] 
    count = 0 
    For each triangle T of P 
     If Intersect(S,T) 
      count = count + 1 
     End if 
    End for 
    return odd(count) 
End 

現在計算是否有段和一個三角形之間的交叉點的功能：

Intersect([q1,q2],(t1,t2,t3)) 
    s1 = orient3d(q1,t1,t2,t3) 
    s2 = orient3d(q2,t1,t2,t3) 
    // Test whether the two extermities of the segment 
    // are on the same side of the supporting plane of 
    // the triangle 
    If(s1 == s2) 
    return false 
    End if 
    // Now we know that the segment 'straddles' the supporing 
    // plane. We need to test whether the three tetrahedra formed 
    // by the segment and the three edges of the triangle have 
    // the same orientation 
    s3 = orient3d(q1,q2,t1,t2) 
    s4 = orient3d(q1,q2,t2,t3) 
    s5 = orient3d(q1,q2,t3,t1) 
    return (s3 == s4 AND s4 == s5) 
End 

最後，orient3d功能：

Orient3d(a,b,c,d) 
     // Computes the sign of the signed volume 
     // of the tetrahedron (a,b,c,d) 
     return Sign(dot(cross(b-a,c-a),d-a)) 
    End 

現在有兩個大陷阱：

1. 如果在計算Orient3d時浮點精度不夠，將會發生什麼情況 ？

2. 當所選片段完全通過 頂點或三角形的邊緣時會發生什麼情況？

對於1.，必須使用任意的精確算術[1]。在參考文獻[1]（Jonathan Shewchuk）的作者[2]中有一個可公開實現的orient3d（）。 Geogram中也有一個實現，我自己的編程庫[3]。

現在爲2，它更棘手，最好的方法是實施符號擾動[4]。簡而言之，這個想法是通過考慮點沿着時間參數化的軌跡移動並在時間趨於零時採取位置的限制來消除orient3d（）返回零的配置的歧義（另一種說法是：如果位置沒有給出答案，請在時間t = 0時查看'速度向量'）。原始參考文獻[4]給出了「多邊形中的點」測試（您的問題的2D版本）的orient2d（）的符號擾動。注意：如果你很懶，而且你不想實現符號擾動，那麼每次orient3d（）測試返回一個零時，你都可以選擇一個隨機的方向（然後你不能保證它不會永久搜索，但是實際上它不太可能發生）。無論如何，我建議僅將其用於原型設計，並最終實現符號擾動。

[1] https://people.eecs.berkeley.edu/~jrs/papers/robustr.pdf

[2] https://www.cs.cmu.edu/~quake/robust.html

[3] http://alice.loria.fr/software/geogram/doc/html/index.html

[4] http://dl.acm.org/citation.cfm?id=77639