返回介绍

3D Convex Hull(Under Construction!)

发布于 2025-01-31 22:20:43 字数 3944 浏览 0 评论 0 收藏 0

3D Convex Hull

三维凸包的表面,由数个凸多边形拼成。

为了方便储存,凸多边形习惯剖分成数个三角形。三维凸包的表面,由数个三角形拼成。

我们习惯以逆时针顺序记录三角形的三个顶点(三角形的三条边变成有向边)。这麽做的好处是,三角形依序取两条边计算叉积,就得到朝外的法向量。

Facet

高维度空间的物体,一块平坦表面称作“刻面”,就好像被刻了一刀。鑽石就是刻面的极致工艺。

三维凸包的绕行顺序是什麽?

二维凸包的顶点,是以时针顺序绕行一圈。三维凸包的顶点,至今仍未发现适当的绕行顺序;三维的 Graham's Scan 至今仍是悬案。

UVa 12513

3D Convex Hull: Enumeration(Under Construction!)

穷举所有三角形,尝试作为凸包刻面。凸包刻面外部必无点;所有点必在凸包刻面内部、或者与凸包刻面共面。时间複杂度 O(N^4)。

此演算法并不完美。如果凸包表面有多点共面,则会得到多馀的三角形。

3D Convex Hull: Gift Wrapping Algorithm(Under Construction!)

先找到第一个凸包刻面,找座标最低的三个点,O(N)。

接下来不断寻找位于最外侧的点,最外侧的点与目前的刻面连线(也就是包覆)形成新刻面。

时间複杂度是 O(NF),其中 F 为凸包刻面数量。多面体最多有 O(N) 个面,因此 F 可写作 O(N),时间複杂度可写作 O(N^2)。

3D Convex Hull: Incremental Method(Under Construction!)

与 2D 版本概念相同。通常採用试误法,穷举刻面,容易实作。时间複杂度是 O(N^2)。

运用刻面法向量,可以轻鬆判断刻面属于凸面、凹面、切面。留下凸面与切面、移除凹面,然后增加当前输入点到凹凸分际的新刻面,就完成了凸包。

利用三角形有向边的概念,可以轻鬆记录凹凸分际的哪些边已经制作过新刻面。这是一个很好用的实作技巧。

3D Convex Hull: Divide and Conquer(Under Construction!)

与二维版本相同,总时间複杂度是 O(NlogN)。

比较困难的地方是合併两个三维凸包,O(N)。

3D Convex Hull: Chan's Algorithm

非常优美的演算法。

https://cs.uwaterloo.ca/~tmchan/ch3d/ch3d.pdf

[1999 Basch et al]
往 xy-plane ,也就是底面,沿负 z 轴方向投影,量出与 z=ax+by+c 平面之间的距离

当 b 是正值,
正前方是一个往上的斜坡,
各种不同远近、与 xz 平面平行的竖立平面,整片沿著斜坡朝自己滑下来,叠在 xz 平面上。

Erdős-Szekeres Conjecture

Erdős-Szekeres Conjecture(Happy Ending Problem)

http://garden.irmacs.sfu.ca/?q=op/erdos_szekeres_conjecture

平面上任意 2^N + 1 个顶点(不会多点共线),是否能描出一个有 N+2 个顶点的凸多边形。例如任意三个点可以描出凸三角形,任意五个点可以描出凸四边形,任意九个点可以描出凸五边形,以此类推。

Szekeres 发表了这个猜想之后,有一位女数学家证明了 N 更大的情形,两人因而相知相遇、结为连理,有了幸福快乐的结局。因此 Erdős 暱称此猜想为 Happy Ending Problem。

注:Erdős-Szekeres Theorem 是另外一件事情,与 Erdős-Szekeres Conjecture 不同。

2^N 个数字,任何一种排列,
必能形成长度为 N+1 的“先递增、再递减子序列”。

这个命题曾经用来证明此猜想,不过结果是失败的。

目前来说,凹与凸是无法量化的,凹与凸无法全体一起比较、全体一起排序。即便是凸包演算法,也只能局部逐一判断凹凸。

用长度来衡量凹凸乍看是个不错的点子,不过困难重重,可能不是一个好方向。

最后附上此命题的证明。

2^(N-2) 个数字,任何一种排列,
必能形成长度为 N-1 的“先递增、再递减子序列”。

数学归纳法。

当 N=2 时,一个数字的任何一种排列,
都可以形成一个长度为 1 的“先递增、再递减子序列”。

当 N=3 时,两个数字的任何一种排列,
都可以形成一个长度为 2 的“先递增、再递减子序列”。
例如 12,刚好都是递增。
例如 21,刚好都是递减。
例如 11,说是递增或是递减都可以。

假设 N=k 时成立。
则 N=k+1 时,
我们将 2^(k-1) 个数字的随便一个排列,中间切一刀,等分为左半和右半。
左半、右半各自都可以形成长度为 k-1 的“先递增、再递减子序列”。

左半“先递增、再递减子序列”的最后一个数字,叫做 p,
右半“先递增、再递减子序列”的第一个数字,叫做 q,
如果 p > q,则左半与 q 可形成长度为 k 的“先递增、再递减子序列”。
如果 p < q,则 p 与右半可形成长度为 k 的“先递增、再递减子序列”。
如果 p = q,则上述两种情形任意一种皆可。
得证。

Erdős-Nagy Theorem

一个凹多边形不断翻折,最后必能变成凸多边形。

http://www.matrix67.com/blog/archives/4780

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文