作者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/cn.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