1.3.4 近似算法

即使有了这些优化，计算凸包算法所固有的下界性能问题仍未有突破。不过，与其计算出精确解，也许近似解就足够了——近似解不但可以很快地计算出来，而且误差也是能够精确测定的。
Bentley-Faust-Preparata算法可以通过将点集切分成多个纵向区域来构建一个近似凸包（Bentley et al.，1982）。在每个区域中，可以很容易找到最大点（根据y坐标决定）和最小点（即图1-6中用框圈起来的点），然后将每个区域中的这两个点以及点集的最左点和最右点连起来，就得到一个近似凸包。当然，这样做有可能会漏掉实际上应该在凸包中的点P1，如图1-6所示。
2017_09_19_144619
图1-6：通过近似计算得到凸包

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

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

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

精彩发现

热门标签

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

相关文章

1
5G远程驾驶和微公交首秀互联网大会
628人阅读
2
学宏程序编程，这些知识必不可少！
1357人阅读
3
华为准备卖出“落后”的5G，多家美企极力竞争！任正非格局太大！
215人阅读