知识卡片

普通读书笔记卡 · 8093.q.3 · 生成模型:未记录

单调链凸包用叉积维护转向

理解等级:中级

将点按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),受到快速排序的启发,使

    参考来源

    - 位置:《算法技术手册》第9章《凸包扫描》(spine1647;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1610.html;u252-ch09-004)。 - 结论依据:252全文及03410–03412伪代码、扫描图与叉积矩阵实读。 - 原始内容:Andrew凸包扫描算法将整个问题分成两个部分,分别构建一个上部凸包和一个下部凸包。首先,点集P中所有的点按照x坐标排序(x坐标相同时,对y坐标进行排序)。图9-8中的点已经按照x坐标从左至右标上了数字。上部凸包从P中的最左边两个点开始构建。凸包扫描算法首先对上部凸包进行扩展,在P中找到这样一个点p - 位置:《算法技术手册》第9章《输入/输出》(spine1647;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1610.html;u253-ch09-004)。 - 结论依据:253假设至少三个且点不太接近;实际接口仍须定义空集、单点、重复点和全共线输入。数值误差是否可忽略取决于应用,不能预先保证。 - 原始内容:没有两个点会过于接近。如果两个点太过接近,而且如果一个点属于凸包,那么凸包扫描算法将会错误地选择一个无效的凸包点(或者抛弃一个有效的凸包点),但是这种误差可以忽略不计。 - 位置:《算法技术手册》第9章《使用环境》(spine1648;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1611.html;u254-ch09-004)。 - 结论依据:254以坐标极值点组成内接四边形,严格位于其内部的点不可能是凸包顶点,可以在线性预处理中过滤;边界共线点是否可删取决于输出要求,极值点重合时也需处理退化。过滤效果依分布而异。 - 原始内容:Akl-Toussaint启发式函数(1978)能够显著地改善算法的总体性能。它抛弃那些在极端四边形中的点。图9-10描绘了图9-4的点所得的极端四边形,启发式函数会抛弃那些灰色的点,这些点不可能组成凸包。 图 9-10 工作中的Akl-Toussaint启发式函数 检查是否一个点p在极端四边形中, - 位置:《算法技术手册》第9章《驱动因素》(spine1649;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1612.html;u255-ch09-004)。 - 结论依据:255讨论排序选择;Graham扫描也可使用叉积和比较器而不必计算三角函数,链表也可用归并排序,并非只能插入排序。桶排序的期望线性依赖分布和映射条件,不能无条件承诺线性。 - 原始内容:排序来排序点,那么其性能将会受快速排序影响,比如几乎有序的数据情况下,快速排序的性能严重退化(详见第4章“快速排序”)。凸包扫描算法能够支持巨大规模的点集,因为它并不是采用的递归策略。例9-2的实现使用了数组,如果使用链表,那么我们不得不采用插入排序,这将会使性能退化到O(n2)。使用平衡二叉树而不 - 位置:《算法技术手册》第9章《解决方案》(spine1650;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1613.html;u256-ch09-004)。 - 结论依据:256的03414–03416代码排序后维护两条链并去除重复端点;调用的areLastThreeNonRight决定共线如何处理,重复点、空输入及浮点比较仍需核验。 - 原始内容:PartialHull类。 图 9-11 PartialHull类 例9-2:凸包扫描算法 - 位置:《算法技术手册》第9章《分析》(spine1652;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1615.html;u258-ch09-004)。 - 结论依据:258指出排序后上下链的总删除次数各至多线性;03417–03418中的点数和时间来自单位正方形均匀样本,不能推广到任意分布,例如圆周点可全部属于凸包。固定δ=10⁻⁹的叉积容差依坐标尺度,不能普遍消除数值误差。 - 原始内容:叉积时,可能会出现浮点运算的误差。因此我们不会严格地判断cp<0,PartialHull采用的是计算cp<δ代替cp<0,希望能够努力消除误差,此时δ=10-9。 - 位置:《算法技术手册》第9章《变种》(spine1653;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1616.html;u259-ch09-004)。 - 结论依据:259说明已按所需顺序排序的点可线性扫描;03419比较圆周、均匀和偏斜分布,桶排序的优势依均匀条件。高维凸包和已按简单多边形顺序给出的输入也需要各自算法及假设。 - 原始内容:已知有序,那么凸包扫描算法的排序步骤可以跳过,在这种情况下,凸包扫描算法的性能是O(n)。如果输入的点是均匀分布的,那么我们可以使用桶排序(详见第4章“桶排序”),也能够得到O(n)的性能。另一种计算凸包的变种是QuickHull(Preparata和Shamos,1985),受到快速排序的启发,使