作者：gnuhpc
出处：http://www.cnblogs.com/gnuhpc/
二维凸包问题描述：
二维凸包的寻找是计算几何学的经典问题之一。
给定平面上的一些点，找出一个最小点集连成一个凸多边形，使得这若干
个点皆在此多边形内或此多边形上，这个凸多边形就是给定点的二维凸包。
凸包的鼻祖算法——“三硬币”算法（The Three-Coins Algorithm）。三硬币算法由斯卡兰斯奇（Sklansky）于 1972 年提出，我们可以用三个硬币来模拟这个算法。
要想凸包问题，需要理解点的排序和左转判定。
点的排序步骤：
1.找一个必在凸包上的点，这显然很容易，通常取横坐标或纵坐标最小的点，极为P0。
2.连结 P0 与其他点，分别计算这些线段与“竖直向下方向”（也就是三四象限的分割线）的夹角，按照夹角由小到达的顺序将各线段的另一端（一端是 P0）标号为 P1、P2、P3……
排序完成
左转判定：
这是经典的计算几何学问题，判断向量 p1=(x1,y1)到 p2=(x2,y2)是否做左
转，只需要判断 x1*y2-x2*y1 的正负，如果结果为正，则从 p1 到 p2 做左转。对于此结论的证明，有兴趣的读者请参考有关书籍。
现在就看看斯卡兰斯奇三硬币算法：
1.预处理：将各点排序。
2.在 P0、P1、P2 上分别放置一枚硬币；
把这三枚硬币分别命名为“后” 、 “中” 、 “前”。
3.反复
如果三枚硬币按“后－中－前”的顺序“做左转”
拿起“后”，放在“前”的前面；
将原先的“后”改名为“前” ；
将原先的“前”改名为“中” ；
将原先的“中”改名为“后” ；
否则
拿起“中”，放在“后”的后面；
移除刚才“中”所在的点；
将原先的“中”改名为“后” ；
将原先的“后”改名为“中” ；
直到“前”盖在 P0 上，且三枚硬币“做左转”
4.按照编号大小顺此连结剩下的点（编号最大的点连回 P0） ，
得到的多边形就是给定点集的凸包。
在纸上画几个点，用三枚硬币模拟很容易模拟这个算法的执行过程，而且似乎求得的结果总是正确的，不过，请您不要试图证明它的正确性，因为，事实上它并非正确*_*。虽然这个算法并非正确，但其中仍有很多地方值得借鉴，后来的许多凸包。算法渗透着一些斯卡蓝斯奇算法的内涵。因此，了解这个算法是很有好处的。 1978 年，Bykat 确定这个算法是错误的，因此有关此算法的反例，有兴趣的读者不妨参考一下 Bykat, A.的《Convex hull of a finite set of points in two dimensions》第 296-298 页。
OpenCV中创建凸包的函数传说中使用的是Sklansky 的算法，不过其正确性有待考察。。。以下是例子：
#include "cv.h"
#include "highgui.h"
#include <stdlib.h>
#define ARRAY 1 /* switch between array/sequence method by replacing 0<=>1 */
int main( int argc, char** argv )
{
IplImage* img = cvCreateImage( cvSize( 500, 500 ), 8, 3 );
cvNamedWindow( "hull", 1 );
#if !ARRAY
CvMemStorage* storage = cvCreateMemStorage();
#endif
for(;;)
{
int i,count = rand()%100+1,hullcount;
CvPoint pt0;
#if !ARRAY
CvSeq *ptseq = cvCreateSeq(CV_SEQ_KIND_GENERIC|CV_32SC2,
sizeof(CvContour),sizeof(CvPoint),storage);
CvSeq *hull;
//随机得到点
for (i=0;i<count;i++)
{
pt0.x = rand()%(img->width/2) + img->height/4;
pt0.y = rand()%(img->height/2) + img->width/4;
cvSeqPush(ptseq,&pt0);
}
hull = cvConvexHull2(ptseq,0,CV_CLOCKWISE,0);//顺时针
hullcount = hull->total;
#else
CvPoint *points = (CvPoint *)malloc(count * sizeof(points[0]));
int *hull = (int *)malloc(count*sizeof(hull[0]));
CvMat point_mat = cvMat(1,count,CV_32SC2,points);
CvMat hull_mat = cvMat(1,count,CV_32SC1,hull);
//随机得到点
for (i=0;i<count;i++)
{
pt0.x = rand()%(img->width/2) + img->height/4;
pt0.y = rand()%(img->height/2) + img->width/4;
points[i]=pt0;
}
cvConvexHull2(&point_mat,&hull_mat,CV_CLOCKWISE,0);
hullcount = hull_mat.cols;//注意这些与序列处理方式不同的地方
#endif
cvZero(img);//清空img，准备画新图
//画点
for (i=0;i<count;i++)
{
#if !ARRAY
pt0 = *CV_GET_SEQ_ELEM(CvPoint , ptseq ,i);
#else
pt0 = points[i];
#endif
cvCircle(img,pt0,2,CV_RGB(255,0,0),CV_FILLED);
}
//确定一个端点
#if !ARRAY
pt0 = **CV_GET_SEQ_ELEM(CvPoint*,hull,hullcount -1);
#else
pt0 = points[hull[hullcount-1]];
#endif
for (i=0;i<hullcount;i++)
{
#if !ARRAY
CvPoint pt = **CV_GET_SEQ_ELEM(CvPoint*,hull,i);
#else
CvPoint pt = points[hull[i]];
#endif
cvLine(img,pt0,pt,CV_RGB(0,255,0));
pt0 = pt;
}
cvShowImage("hull",img);
cvWaitKey(0);
cvSaveImage("hull.jpg",img);
cvDestroyWindow("hull");
#if !ARRAY
cvClearMemStorage(storage);
#else
free(points);
free(hull);
#endif
}
return 0;
}
作者：gnuhpc
出处：http://www.cnblogs.com/gnuhpc/
作者：gnuhpc
出处：http://www.cnblogs.com/gnuhpc/
除非另有声明，本网站采用知识共享“署名 2.5 *”许可协议授权。