本文主要是介绍2D凸包算法(六):Incremental Method,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Incremental Method 图示
Incremental Method 实时的保持一个凸包。每当输入一点,如果点在外面,计算此点与当前凸包的两条切线,去除凸包内的边以连接两条切线为新的边。如果在凸包内部就删除该点。
通过遍历凸包边界点。如果点的左右邻点都在改点与请求点连线的同侧,则说明该点就是切点,这个连线就是切线。反之则不是,需要继续查找。
- 时间复杂度为O(N²)
每次需要遍历所有的凸包边界点。
这篇关于2D凸包算法(六):Incremental Method的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!