知识卡片
单调链凸包用叉积维护转向
将点按x、y字典序排序,分别按正向和反向扫描;每加入一点后检查末尾三点的叉积,若转向不符合所需方向则移除中间点,直到满足条件。上、下链去重端点后合并得到凸包。
叉积符号表达左右转,等于0表示共线;是否保留边界上的共线点必须先约定。排序 O(n log n),每点在各链至多入栈和出栈一次,扫描 O(n)。
253假设至少三个且点不太接近;实际接口仍须定义空集、单点、重复点和全共线输入。数值误差是否可忽略取决于应用,不能预先保证。
254以坐标极值点组成内接四边形,严格位于其内部的点不可能是凸包顶点,可以在线性预处理中过滤;边界共线点是否可删取决于输出要求,极值点重合时也需处理退化。过滤效果依分布而异。
255讨论排序选择;Graham扫描也可使用叉积和比较器而不必计算三角函数,链表也可用归并排序,并非只能插入排序。桶排序的期望线性依赖分布和映射条件,不能无条件承诺线性。
256的03414–03416代码排序后维护两条链并去除重复端点;调用的areLastThreeNonRight决定共线如何处理,重复点、空输入及浮点比较仍需核验。
258指出排序后上下链的总删除次数各至多线性;03417–03418中的点数和时间来自单位正方形均匀样本,不能推广到任意分布,例如圆周点可全部属于凸包。固定δ=10⁻⁹的叉积容差依坐标尺度,不能普遍消除数值误差。
259说明已按所需顺序排序的点可线性扫描;03419比较圆周、均匀和偏斜分布,桶排序的优势依均匀条件。高维凸包和已按简单多边形顺序给出的输入也需要各自算法及假设。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 7 处
- · 查看原书依据
Andrew凸包扫描算法将整个问题分成两个部分,分别构建一个上部凸包和一个下部凸包。首先,点集P中所有的点按照x坐标排序(x坐标相同时,对y坐标进行排序)。图9-8中的点已经按照x坐标从左至右标上了数字。上部凸包从P中的最左边两个点开始构建。凸包扫描算法首先对上部凸包进行扩展,在P中找到这样一个点p
- · 查看原书依据
没有两个点会过于接近。如果两个点太过接近,而且如果一个点属于凸包,那么凸包扫描算法将会错误地选择一个无效的凸包点(或者抛弃一个有效的凸包点),但是这种误差可以忽略不计。
- · 查看原书依据
Akl-Toussaint启发式函数(1978)能够显著地改善算法的总体性能。它抛弃那些在极端四边形中的点。图9-10描绘了图9-4的点所得的极端四边形,启发式函数会抛弃那些灰色的点,这些点不可能组成凸包。 图 9-10 工作中的Akl-Toussaint启发式函数 检查是否一个点p在极端四边形中,
- · 查看原书依据
排序来排序点,那么其性能将会受快速排序影响,比如几乎有序的数据情况下,快速排序的性能严重退化(详见第4章“快速排序”)。凸包扫描算法能够支持巨大规模的点集,因为它并不是采用的递归策略。例9-2的实现使用了数组,如果使用链表,那么我们不得不采用插入排序,这将会使性能退化到O(n2)。使用平衡二叉树而不
- · 查看原书依据
PartialHull类。 图 9-11 PartialHull类 例9-2:凸包扫描算法
- · 查看原书依据
叉积时,可能会出现浮点运算的误差。因此我们不会严格地判断cp<0,PartialHull采用的是计算cp<δ代替cp<0,希望能够努力消除误差,此时δ=10-9。
- · 查看原书依据
已知有序,那么凸包扫描算法的排序步骤可以跳过,在这种情况下,凸包扫描算法的性能是O(n)。如果输入的点是均匀分布的,那么我们可以使用桶排序(详见第4章“桶排序”),也能够得到O(n)的性能。另一种计算凸包的变种是QuickHull(Preparata和Shamos,1985),受到快速排序的启发,使