pointarray.cpp

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

// PointArray.cpp: implementation of the CPointArray class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ConvexHull.h"
#include "PointArray.h"

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

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

CPointArray::CPointArray()
{
	first=last=NULL;
	length=0;
}

CPointArray::~CPointArray()
{
	this->Destroy();
}

bool CPointArray::Add(CPointNode *ppoint)
{
	if(!ppoint)
		return false;
	ppoint->next=first;
	first=ppoint;
	if(last==NULL)
		last=ppoint;
	length++;
	return true;
}

bool CPointArray::Push(CPointNode *ppoint)
{
	if(!ppoint)
		return false;
	ppoint->next=first;
	first=ppoint;
	if(last==NULL)
		last=ppoint;
	length++;
	return true;
}

CPointNode* CPointArray::Pop()
{
	if(first==NULL)
		return NULL;
	CPointNode* ppn=first;
	first=ppn->next;
	ppn->next=NULL;
	if(last==ppn)
		last=NULL;
	length--;
	return ppn;
}

bool CPointArray::Delete(CPointNode *ppn)
{
	CPointNode* temp=first;
	CPointNode*	pre=NULL;
	while (temp)
	{
		if(temp==ppn)
		{
			if(pre!=NULL)
				pre->next=temp->next;
			else
				first=temp->next;
			if(last==ppn)
				last=pre;
			ppn->next=NULL;
			length--;
			return true;
		}
		pre=temp;
		temp=temp->next;
	}
	return false;
}

void CPointArray::Destroy()
{
	while(first)
	{
		last=first->next;
		delete first;
		first=last;
	}
	last=first=NULL;
	length=0;
}