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