Fw: [問題] 3D 凸包 包絡線

[BanPeeBan (踢屁屁)]

各位好 我是這篇的原po
最近需要編寫「找出3D凸包上的點」的程式
不過上網查到的凸包演算法解說與範例都是2D的
想破了頭都覺得推廣到3D不是那麼簡單
請問該怎麼求得呢?


※ [本文轉錄自 Fortran 看板 #1VFH-RGz ]

作者: BanPeeBan (踢屁屁) 看板: Fortran
標題: [問題] 3D 凸包 包絡線
時間: Wed Aug 19 20:48:20 2020

https://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85

已知
三維空間中n個點的座標

想求
一個可以恰把全部的點包起來的凸多面體
好像叫凸包(Convex hull)或是包絡線(Envelope)
並且輸出多面體上所有點的座標

查了一下 好像沒什麼相關資料

請問邏輯該怎麼寫?會用到那些函數?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.240.53.198 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Fortran/M.1597841307.A.43D.html
→ blc: wiki上的演算法有看懂嗎？
還在理解中 不過似乎都是在處理2D的(?
※ 編輯: BanPeeBan (123.240.53.198 臺灣), 08/19/2020 22:02:15

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: BanPeeBan (101.12.193.67 臺灣), 08/22/2020 05:43:29
※ 編輯: BanPeeBan (101.12.193.67 臺灣), 08/22/2020 05:48:36
推 hwanger     : 目前只有最蠢的作法 每三個不共線的點做一個平面
→ hwanger     : 考慮所有平面(最多C(n,3)個)的集合S 從中選出所有的
→ hwanger     : 平面G滿足 所有的n點代進去要嘛全非負 要嘛全非正
→ hwanger     : 收集所有這樣的G 形成S的子集合S'
→ hwanger     : 然後對於每一個S'的元素G 找出所有在G上的點p1,p2,.
→ hwanger     : ..,pk 接著用2D的作法去找在G上凸多邊形頂點就可以
→ hwanger     : 最後凸多面體的頂點 就是這些凸多邊形頂點的聯集
推 hwanger     : 如果單純只想知道一個點是否落在Convex hull 應該是
→ hwanger     : 可以用Farkas' lemma和Linear programming來判定
推 hwanger     : 如果只是想單純從n點中找落在boundary的點 把點代
→ hwanger     : 到S'的元素中即可
感謝大大 我再想想看
※ 編輯: BanPeeBan (101.12.193.67 臺灣), 08/22/2020 14:47:33
推 hwanger     : 雖然原po說沒查到什麼資料 可是google "convex hull
→ hwanger     : 3D"其實還蠻多資料的 XDDDD
→ hwanger     : 如果真得沒有找到可以實現的想法的話 可以查一下
→ hwanger     : Qhull library的原始碼 scipy就是調用qhull
推 hwanger     : 用Farkas' lemma和Linear programming的那個方法可
→ hwanger     : 能會因為在想要的區域上沒有最小值而沒辦法判定 沒
→ hwanger     : 有仔細check過 請先忽略他