先预排序，预排序后最左和最右的点肯定是凸包中的点。然后可以递归的从内向外扩展凸包，在当前直线的2侧寻找最高点，最高点肯定在凸包中，这里涉及到一些数学知识：
a，首先定义射线p1到p2的左侧：若p1 p2 p构成的顺序是逆时针，称p在射线的左侧
b，三角形p1 p2 p3的面积等于下列行列式的一半：
仅当p3在射线p1p2左侧时这个值才为正。
由此我们很容易求p1，p2左侧的最高点（离直线最远的点，这个点即凸包向外扩展得到的新顶点），得到一个最高点后，就得到了2条新边，继续向外扩展
2022-05-21 17:10:00
1KB
1
本文参考自<<算法导论>>章节33.3,利用Graham算法寻找二位平面散点集的凸包,利用OpenGL将计算的结果绘制出来.算法主要利用向量的叉积判断点和线段的位置关系,详见 向量叉积,然后从左下角点按逆时针方向寻找最边缘的线段,利用的原理就是从凸包上任意一点逆时针出发,每到一个节点,一定会向左拐.资源包包含完整的代码实现,部分测试数据和测试结果.
2022-04-26 16:23:57
434KB
1
凸包问题基本定义与性质
基本概念：
凸集——如果平面上的一个点集中任意两点之间的连线上的点都属于这个点集，则称这个点集为凸集。
凸包－包含点集中所有点的最小凸多边形，其中凸多边形的顶点属于这个点集。
性质：
点集中两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。
凸包问题－就是求包含给定点集的凸多边形。
2022-04-25 17:25:20
558KB
1