convexhull1.cpp

使用C++实现的Graham扫描法（求解凸包问题）

// ConvexHull1.cpp: implementation of the CConvexHull class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ConvexHull.h"
#include "ConvexHull1.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CConvexHull::CConvexHull()
{
	pP0=NULL;
}

CConvexHull::~CConvexHull()
{
	ConvexHullStack.Destroy();
	pointSet.Destroy();
}

void CConvexHull::LoadPointArray(CPointArray* ppa)
{
	pointSet.first=ppa->first;
	pointSet.last=ppa->last;
	pointSet.length=ppa->length;
//////////////////////////////////////////////////////////////////////////
	ppa->first=ppa->last=NULL;ppa->length=0;
	delete ppa;
	ppa=NULL;
////////////////////////////////////////////
	pP0=pointSet.first;
	if(!pP0)return;
	CPointNode*	temp=pP0->next;
	while(temp)
	{
		if(temp->point.y<pP0->point.y||
			(temp->point.y==pP0->point.y&&temp->point.x<pP0->point.x))
			pP0=temp;
		temp=temp->next;
	}
	pointSet.Delete(pP0);
	AngleSort(pointSet);
}


int CConvexHull::DiffMul(CPoint &p0, CPoint &p1, CPoint &p2)
/*(P2-P0)*(P1-P0)*/
//<0 p0p1p2左拐；>0 p0p1p2右拐；=0 p0p1p2共线
//在屏幕坐标系中：<0 p0p1p2右拐；>0 p0p1p2左拐；=0 p0p1p2共线
{
	int x1=p2.x-p0.x;
	int y1=p2.y-p0.y;
	int x2=p1.x-p0.x;
	int y2=p1.y-p0.y;
	return x1*y2-x2*y1;
}

int CConvexHull::PointCompare(CPoint& p1, CPoint& p2)
//>0:p1>p2;<0:p1<p2;=0:p1,p2极角相等。
{
	return DiffMul(pP0->point,p1,p2);
}

void CConvexHull::AngleSort(CPointArray &pa)
{
	if(pa.length==0||pa.length==1)
		return;
	CPointNode* tagp=pa.first;
	CPointNode* temp=pa.first->next;
	CPointNode* pretagp=NULL;
	
	QuickSort(pa, NULL, pa.last);
}

void CConvexHull::QuickSort(CPointArray &pa, CPointNode *prebegin, CPointNode *end)
{
	CPointNode* tagp=NULL;
	CPointNode* temp,*pretemp;
	CPointNode* pretagp=NULL;
	if(pa.length==0||pa.length==1||end==NULL||
		(prebegin&&end==prebegin->next)||end==prebegin)
		return;
	if(!prebegin){
		tagp=pa.first;
	}
	else{
		tagp=prebegin->next;
	}
	pretagp=prebegin;
	temp=tagp->next;
	pretemp=tagp;
	
	while(pretemp!=end)
	{
		int flag=PointCompare(temp->point,tagp->point);
		if(flag<0)//只做移动，length不变。
		{
			pretemp->next=temp->next;
			if(prebegin)
			{
				temp->next=prebegin->next;
				prebegin->next=temp;
				if(pretagp==prebegin)//!!!!!!!!!!!!!!!!!!!!
					pretagp=temp;
			}
			else
			{
				temp->next=pa.first;
				pa.first=temp;
				if(!pretagp)
					pretagp=temp;
			}
			if(temp==end)
				end=pretemp;
			if(pa.last==temp)
				pa.last=pretemp;
			temp=pretemp->next;
			continue;
		}
		else if(flag==0)
		{//删除操作，length改变。
			pretemp->next=temp->next;
			pa.length--;
			if(DistanceToP0(temp->point)>DistanceToP0(tagp->point))
			{
				tagp->point.x=temp->point.x;
				tagp->point.y=temp->point.y;
			}
			if(temp==end)
				end=pretemp;
			if(pa.last==temp)
				pa.last=pretemp;
			delete temp;//及时释放删除元素。
			temp=pretemp->next;
			continue;
		}
		pretemp=temp;
		temp=temp->next;
	}

	QuickSort(pa,prebegin,pretagp);
	QuickSort(pa,tagp,end);
}


int CConvexHull::DistanceToP0(CPoint &p1)
{
	return (pP0->point.x-p1.x)*(pP0->point.x-p1.x)+
		(pP0->point.y-p1.y)*(pP0->point.y-p1.y);
}


void CConvexHull::Graham()
{
	ConvexHullStack.Push(pP0);
	pP0=NULL;//pP0已入栈，将其置为NULL。
	int i=0;
	while(pointSet.length&&i<2)
	{
		CPointNode* temp=pointSet.Pop();
		ConvexHullStack.Push(temp);
		i++;
	}
	while(pointSet.length)
	{
		CPointNode* temp=pointSet.Pop();
		int flag=DiffMul(ConvexHullStack.first->next->point,ConvexHullStack.first->point,temp->point);
		while(flag>=0){
			CPointNode* temp1=ConvexHullStack.Pop();
			delete temp1;//释放内存单元。
			flag=DiffMul(ConvexHullStack.first->next->point,ConvexHullStack.first->point,temp->point);
		}
		ConvexHullStack.Push(temp);
	}
	
}

void CConvexHull::Destroy()
{
	ConvexHullStack.Destroy();
	pointSet.Destroy();
}