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

看板Math作者 (踢屁屁)時間5年前 (2020/08/22 05:43), 5年前編輯推噓5(5推 0噓 13→)
留言18則, 1人參與, 5年前最新討論串1/1
各位好 我是這篇的原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
→
08/19 21:36, 5年前 , 1F
wiki上的演算法有看懂嗎？
08/19 21:36, 1F
還在理解中 不過似乎都是在處理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
推
08/22 08:35, 5年前 , 2F
目前只有最蠢的作法 每三個不共線的點做一個平面
08/22 08:35, 2F
→
08/22 08:38, 5年前 , 3F
考慮所有平面(最多C(n,3)個)的集合S 從中選出所有的
08/22 08:38, 3F
→
08/22 08:40, 5年前 , 4F
平面G滿足 所有的n點代進去要嘛全非負 要嘛全非正
08/22 08:40, 4F
→
08/22 08:42, 5年前 , 5F
收集所有這樣的G 形成S的子集合S'
08/22 08:42, 5F
→
08/22 08:47, 5年前 , 6F
然後對於每一個S'的元素G 找出所有在G上的點p1,p2,.
08/22 08:47, 6F
→
08/22 08:49, 5年前 , 7F
..,pk 接著用2D的作法去找在G上凸多邊形頂點就可以
08/22 08:49, 7F
→
08/22 08:51, 5年前 , 8F
最後凸多面體的頂點 就是這些凸多邊形頂點的聯集
08/22 08:51, 8F
推
08/22 13:39, 5年前 , 9F
如果單純只想知道一個點是否落在Convex hull 應該是
08/22 13:39, 9F
→
08/22 13:40, 5年前 , 10F
可以用Farkas' lemma和Linear programming來判定
08/22 13:40, 10F
推
08/22 14:28, 5年前 , 11F
如果只是想單純從n點中找落在boundary的點 把點代
08/22 14:28, 11F
→
08/22 14:28, 5年前 , 12F
到S'的元素中即可
08/22 14:28, 12F
感謝大大 我再想想看 ※ 編輯: BanPeeBan (101.12.193.67 臺灣), 08/22/2020 14:47:33
推
08/22 15:13, 5年前 , 13F
雖然原po說沒查到什麼資料 可是google "convex hull
08/22 15:13, 13F
→
08/22 15:14, 5年前 , 14F
3D"其實還蠻多資料的 XDDDD
08/22 15:14, 14F
→
08/22 15:16, 5年前 , 15F
如果真得沒有找到可以實現的想法的話 可以查一下
08/22 15:16, 15F
→
08/22 15:17, 5年前 , 16F
Qhull library的原始碼 scipy就是調用qhull
08/22 15:17, 16F
推
08/22 18:58, 5年前 , 17F
用Farkas' lemma和Linear programming的那個方法可
08/22 18:58, 17F
→
08/22 18:58, 5年前 , 18F
能會因為在想要的區域上沒有最小值而沒辦法判定 沒
08/22 18:58, 18F
→
08/22 18:58, 5年前 , 19F
有仔細check過 請先忽略他
08/22 18:58, 19F
‣ 更多 BanPeeBan 的文章
文章代碼(AID): #1VG402Tc (Math)