- Algorithm
- Incremental Method
- Simulation
- Backtracking
- Dynamic Programming
- Largest Empty Interval
- Location Allocation Problem
- Knapsack Problem
- Algorithm Analysis
- Data
- Sort
- Set
- 排序资料结构: Search Tree 系列
- Sequence 资料结构: Array / List
- 大量 Point 资料结构: k-Dimensional Tree
- Region 资料结构: Uniform Grid
- Graph
- Tree 资料结构: Heavy-Light Decomposition
- Graph Spectrum(Under Construction!)
- Tree
- Binary Tree
- Directed Acyclic Graph
- Articulation Vertex / Bridge
- Reachability
- Bipartite Graph
- Clique(Under Construction!)
- Planar Graph
- Path
- Single Source Shortest Paths: Label Correcting Algorithm
- Shortest Walk
- Cycle
- Spanning Tree
- s-t Flow
- Feasible s-t Flow
- Cut
- Matching
- T-Join
- Hamilton Circuit
- Domination
- Coloring
- Labeling
- Vector Product
- Sweep Line
- Rectangle
- Rectangle
- Polygon
- Convex Hull
- 3D Convex Hull(Under Construction!)
- Half-plane Intersection
- Voronoi Diagram
- Triangulation
- Metric
- Number
- Sequence
- Function (ℝ)
- Matrix
- Root Finding
- Linear Equations
- Functional Equation
- Optimization
- Interpolation
- Curve
- Regression
- Estimation
- Clustering
- Transformation(Under Construction!)
- Wave (ℝ)
- Representation
- Signal
- State(Under Construction!)
- Markov Chain
- System(Under Construction!)
- Markov Model
- Function
- Gray Code
- Base
- Divisor
- Prime
- Residue
- Lattice
- Series(Under Construction!)
- Average Number
- Nim
- String
- Longest Increasing Subsequence
- Longest Common Subsequence
- Approximate String Matching
- String Matching
- String Matching
- String Matching: Inverted Index
- Count Substrings
- Palindrome
- Language
- Code
- Compression
- Correction
- Encryption
- Transmission
- Data
- Text
- 2D Graphics
- Audio
- Audition(Under Construction!)
- Image
- Vision(Under Construction!)
- Model
- Motion(Under Construction!)
- Camera(Under Construction!)
- Glass(Under Construction!)
- Computer
- Physics
- Biology
- Medicine
- Finance
- Education
- Standard Library
3D Convex Hull(Under Construction!)
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
一个凹多边形不断翻折,最后必能变成凸多边形。
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论