计算几何---凸包问题
计算 --- 几何 问题 凸包
2023-09-27 14:21:08 时间
https://zh.wikipedia.org/zh-cn/%E5%87%B8%E5%8C%85
1,增量式算法
逐次将点加入,然后检查之前的点是否在新的凸包上。由于每次都要检查所有之前的点,时间复杂度为
2. 包裹法(Jarvis步进法)
首先由一点必定在凸包的点开始,例如最左的一点
3. 葛立恒(Graham)扫描法
由最底的一点A_1开始(如果有多个这样的点,那么选择最左边的),计算它跟其他各点的连线和x轴正向的角度,按小至大将这些点排序,称它们的对应点为
考虑最小的角度对应的点
这个算法的整体时间复杂度是
这个算法由葛立恒在1972年发明。[1]它的缺点是不能推广到二维以上的情况。
4. 单调链
将点按x坐标的值排列,再按y坐标的值排列。
选择x坐标为最小值的点,在这些点中找出y坐标的值最大和y坐标的值最小的点。对于x坐标为最大值也是这样处理。将两组点中y坐标值较小的点连起。在这条线段下的点,找出它们之中y坐标值最大的点,又在它们之间找x坐标值再最小和最大的点……如此类推。
时间复杂度是
5. 分治法
将点集X分成两个不相交子集。求得两者的凸包后,计算这两个凸包的凸包,该凸包就是X的凸包。时间复杂度是
6. 快包法(Akl-Toussaint启发式)
选择最左、最右、最上、最下的点,它们必组成一个凸四边形(或三角形)。这个四边形内的点必定不在凸包上。然后将其余的点按最接近的边分成四部分,再进行快包法(QuickHull)。
相关文章
- 地球引擎高级教程——GEE中(TAGEE函数 3x3 移动窗口的球体几何形状和高程节点来计算偏导数和地形属性)中的地形分析
- 【云计算】私有云是什么?主要集中在哪些行业?与公有云有什么区别?
- difflib --- 计算差异的辅助工具
- 第12周报告3 --- 计算存款利息
- 《微软云计算Windows Azure开发与部署权威指南》——6.7 AppFabric服务总线REST的服务开发
- 2017云计算市场需要密切关注的10个趋势
- 边缘重生将如何改变云计算
- [洛谷]P1028数的计算
- vue基础---计算属性和侦听器
- 建设一个能承受500万PV/每天的网站如果计算?
- 高数 | 旋转体体积计算方法汇总、二重积分计算旋转体体积
- CAD负荷计算时怎么复制楼层?CAD楼层复制技巧
- 【Java】使用BigDecimal类进行精确小数计算