知识卡片

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

包裹法按方向选凸包下一点

理解等级:中级

从最低且同高时最左的点出发,维护当前包裹点P0和候选Pc;遍历其他点Pi,以叉积符号比较方向,发现更外侧候选时替换Pc。与Pc同方向共线时选择离P0更远者,避免把边内点当成极端顶点。随后从Pc继续,直到回到起点。

03108示例依次为(−2,−4)→(4,1)→(−3,4)→(−4,−2)→起点;03109距离式是两点欧氏距离。方向正负依向量顺序决定,不能不看公式就固定解释为左转或右转。

对n个输入、h个输出顶点,每轮扫描n点,正常终止时O(nh);h可随n增长,所以最坏可达O(n²)。浮点近共线、重复坐标和退化点集需要另行约定。

316/03112–03113每选一个边界点遍历全部n点,正常终止h轮是O(nh),最低点扫描O(n)。代码使用sqrt/pow比较距离、double精确等零;实际数值误差与退化导致的错误终止不能由渐近复杂度保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      Jarvis's March 为点集P创建凸包的一种方法是采用Jarvis's march法。Jarvis's march按照两个部分来建立凸包,称为右链和左链。右链由凸包中位置最低的点(y轴坐标最小)到位置最高的点所组成。如果两个点的高度一样,那么最低点就是那个x轴坐标也最小的点。左链由凸包中位置

    • · 查看原书依据

      O(nh),这里n代表点集中总的元素个数,而h代表凸包中的点的个数。对于确定最低点的循环,其复杂度为O(n),因为必须遍历所有的点才判断出哪一个点最低。嵌套循环总的复杂度为O(nh),因为对于每一个插入凸包中的点,必须遍历点集中所有其他的点才能确定出哪个才是下一个要插入的点。由于确定最低点以及构建凸

    参考来源

    - 位置:《算法精解:C语言描述》第17章《Jarvis's March》(spine1426;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1392.html;u314-ch17-008)。 - 结论依据:314全文、03108四阶段完整图和03109距离公式实读。 - 原始内容:Jarvis's March 为点集P创建凸包的一种方法是采用Jarvis's march法。Jarvis's march按照两个部分来建立凸包,称为右链和左链。右链由凸包中位置最低的点(y轴坐标最小)到位置最高的点所组成。如果两个点的高度一样,那么最低点就是那个x轴坐标也最小的点。左链由凸包中位置 - 位置:《算法精解:C语言描述》第17章《凸包的实现与分析》(spine1428;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1394.html;u316-ch17-008)。 - 结论依据:316/03112–03113每选一个边界点遍历全部n点,正常终止h轮是O(nh),最低点扫描O(n)。代码使用sqrt/pow比较距离、double精确等零;实际数值误差与退化导致的错误终止不能由渐近复杂度保证。 - 原始内容:O(nh),这里n代表点集中总的元素个数,而h代表凸包中的点的个数。对于确定最低点的循环,其复杂度为O(n),因为必须遍历所有的点才判断出哪一个点最低。嵌套循环总的复杂度为O(nh),因为对于每一个插入凸包中的点,必须遍历点集中所有其他的点才能确定出哪个才是下一个要插入的点。由于确定最低点以及构建凸