1.3.1 贪心算法

以下的贪心算法展示了如何找到凸包上的每个点：

  1. 删除P中的最低点low——low必须在凸包上。
  2. 垂直画一条穿过点low的直线，将剩余的n－1个点分别和点low连线，以垂直直线右侧的点的夹角为正值降序排列，夹角的范围是从90皛－90啊n-2是最右侧的点，而P0是最左侧的点。图1-3中显示了垂直线以及每个点与其的夹角。
  3. 以{Pn-2, low, P0}这个顺序组成的点集为基础，在剩余的点中选择可以组成凸包的点——从P1开始，将每个点尝试加至这个点集的尾部，如果这个点集的最后三个点组成的两条线段向左拐，那么就需要移除这个错误的点。
  4. 在访问完所有的点之后，就得到了一个凸包，如图1-3所示。
    2017_09_19_143857

图1-3：使用贪心算法得到的凸包

继续阅读与本文标签相同的文章

None
最新文章 最热文章
收藏 打印

特别推荐 2026年05月14日 星期四

精彩发现

热门标签

阻止表单提交 窗口 关闭浏览器 清除 CDATA css文件 光标位置 坐标 javascrpt !important 超链接 数字

相关文章

1
陆奇：看好5G技术，但应用好5G还需要时间
879人阅读
2
在Visual Studio中使用clang-tidy进行代码分析
255人阅读
3
甘薇贾跃亭曝出离婚消息，贾跃亭破产前转账51万美元，作为“家庭费用”
1446人阅读