Pseudo-Code: Graham Scan Algorithm
|
Input: a set of points
S = {P = (P.x,P.y)}
Select the rightmost lowest point P0 in S.
Sort S angularly about P0 as a center.
For ties, discard the closer points.
Let P[N] be the sorted array of points.
Push P[0]=P0 and P[1] onto a stack W.
while i < N
{
Let PT1 = the top point on W
Let PT2 = the second top point on W
if (P[i] is strictly left of the line PT2 to PT1) {
Push P[i] onto W
i++ // increment i
}
else
Pop the top point PT1 off the stack
}
Output: W = the convex hull ofS.
|
转自:凸包问题的几种算法,包括Graham scan 算法
这个算法其实也很好想通的。
第一步:找到y坐标最小的点p0;
第二步:以p0为原点,对所有的点按逆时针顺序排序;
第三步:逐步迭代,加入边界点。(画出一条边,如果一个新的边更靠左,则加入,否则不加入)。
分享到:
相关推荐
O(nlogn)凸包问题 poj2187
NULL 博文链接:https://128kj.iteye.com/blog/1749213
北大POJ1113-Wall【凸包】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1748635
POJ上做的一个凸包的题,可作为凸包的模板。
凸包melkman算法cpp实现,通过poj1113题测试
poj1113 melkman算法求凸包, 使用STL
NULL 博文链接:https://128kj.iteye.com/blog/1752345
1.16.2 直线旋转_两凸包的最短距离(poj3608) 58 1.16.3 扇形的重心 62 1.16.4 根据经度纬度求球面距离 62 1.16.5 多边形的重心 64 1.16.6 存不存在一个平面把两堆点分开(poj3643) 66 1.16.7 pku_3335_判断多边形的核...
3.6.4 凸包 3.6.5 数值积分 3.7 一起来挑战GCJ的题目(2) 3.7.1 Numbers 3.7.2 No Cheating 3.7.3 Stock Charts 3.7.4 Watering Plants 3.7.5 Number Sets 3.7.6 Wi-fi Towers 第4章 登峰造极——高级篇 4.1 更加...
5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) 7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式. 8. 调用系统的qsort, 技巧很多,慢慢掌握. 9. 任意...
2.10.1 一类开关问题,对 2 取模的 01 方程组 . . . . . . . . . . . . . . . . . . . 37 2.10.2 解同余方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.11 整数拆分 . . . . . . ....