3D中半空間集合的頂點

Question

任何人都可以推薦任何好算法或他們自己的方法來計算3D中半空間集合的頂點嗎？半空間保證凸和有界。

到目前爲止，網絡搜索一直沒有結果，qhull可以執行此操作，但我希望能夠在問題上獲得更多的數學上的偏差，而不是閱讀大量的源代碼 - 但這是最​​後的手段。

Answer 1

假設所有的半空間都是由一個平面定義的，所有半空間之外的所有平面（即，相對於一個有向法向量）都在該平面之後，並且該平面之前或之上的所有東西都在裏面，所以最明顯的解決方案是：

• 爲每雙飛機得到並存儲線交集;

這會給你一個行集合。然後對於每一行和一對平面：

• 如果該行完全停在飛機上，什麼也不做;
• 如果直線與平面相交併且還不是線段，則將其轉換爲直至交點的線段;
• 如果它已經是線段並且與平面相交，則剪掉平面後面的部分;
• 如果線條已經是線段並完全停留在飛機的一側，則什麼都不做。

然後收集所有線段終點的集合。