凸包算法

今天做作业 ，研究凸包算法，写了一个专说中很快的方法。听说效率N，算法的精髓在于任何的判断操作都基于一个点和向量的位置关系。
例如，要判断点是否在多边形内，只需判断点和每条边向量的位置是否都一直，都在左边或者都在右边。

bool CGrahamView::isLeft(CPoint point,m_line *line)
{
	//m_line x;
	float a=line->a;
	float b=line->b;
	float c=line->c;
	float v=a*point.x+b*point.y+c*1.0f;
	if(v<=0)
		return true;
	else
		return false;
}
m_line CGrahamView::createLine(CPoint i, CPoint j)
{
	//m_line *line=new m_line();
	m_line line;
	line.i=i;
	line.j=j;
	line.a=i.y-j.y;
	line.b=j.x-i.x;
	line.c=i.x*j.y-j.x*i.y;
	return line;
}
bool CGrahamView::isInside(node *head, CPoint pt,bool isClock)
{
	int flag=1;
	node *p;
	p=head->next;
	vector<m_line> v_line;
	m_line line;
	while(p!=NULL&&p->next!=NULL)
	{
		line=createLine(p->pt,p->next->pt);
		v_line.push_back(line);
		p=p->next;
	}
	line=createLine(p->pt,head->next->pt);
	v_line.push_back(line);
	if(isClock==true)
	{
		for(int i=0;i<v_line.size();i++)
		{
			if(isLeft(pt,&v_line[i])==true)
			{
				flag=0;
				break;
			}
		}
	}
	if(isClock==false)
	{
		for(int i=0;i<v_line.size();i++)
		{
			if(isLeft(pt,&v_line[i])==false)
			{
				flag=0;
				break;
			}
		}
	}
	if(flag==0)
	return false;
	else
	return true;
}

bool CGrahamView::findVisible(node *head, CPoint pt,bool isClock)
{
	node * p;
	p=head->next;
	vector<m_line> v_line;
	vector<int> v_point;
	m_line line;
	while(p!=NULL&&p->next!=NULL)
	{
		line=createLine(p->pt,p->next->pt);
		v_line.push_back(line);
		p=p->next;
	}
	line=createLine(p->pt,head->next->pt);
	v_line.push_back(line);
	if(isClock==true)
	{
		for(int i=0;i<v_line.size();i++)
		{
			if(isLeft(pt,&v_line[i])==true)
			v_point.push_back(i);
		}
	}
	else
	{
		for(int i=0;i<v_line.size();i++)
		{
			if(isLeft(pt,&v_line[i])==false)
			v_point.push_back(i);
		}
	}
	int sit=0;
	int flag1;
	int flag2;
	int count=0;
	count=v_point.size();
	for(int i=0;i<v_point.size()-1;i++)
	{
		if(v_point[i]!=v_point[i+1]-1)
		{
			flag1=v_point[i];
			flag2=v_point[i+1];
			sit=1;
			break;
		}	
	}
	if(sit==0)
	{
		
		int start=v_point[0]+1;
		int end;
		if(count>=2)
		{
			start=v_point[0]+1;
			end=v_point[count-1];
			for(int i=start;i<=end;i++)
			//p=index(head,v_point[1]);
			dele(head,start);
		}
		insert(head,pt,start-1);
		v_point.clear();
	}
	else
	{
		int start=flag2+1;
		insert(head,pt,flag2);
		if(count>=2)
		{
			node*p=CGrahamView::index(head,(flag2+1)%CGrahamView::getSize(head));
			node*q=p->next;
			for(int i=count-1;i>0;i--)
			{
				if(q==NULL)
				{
					dele(head,0);
					//q=head->next;
				}
				else
				{
					node*w =q;
					q=q->next;
					p->next=q;
					delete w;
				}
			    //if(start%CGrahamView::getSize(head)<flag2)
				//flag2--;
				//	dele(head,start);
			}
		}
		//insert(head,pt,flag2);
		v_point.clear();
	}
	return 0;
}


node* CGrahamView::index(node *head, int index)
{
	int i=0;
	node*p;
	if(index<0)
	p=NULL;
	else
	{
		p=head->next;
		while(p!=NULL&&i<index)
		{
			p=p->next;
			i++;
		}
	}
	return p;
}



bool CGrahamView::insert(node*head,CPoint pt, int index)
{
	if(index<0)
	return false;
	node*p;
	p=CGrahamView::index(head,index);
	node* np=new node();
	np->pt=pt;
	np->next=p->next;
	p->next=np;
	return true;
}

bool CGrahamView::dele(node *head, int index)
{
	node*p;
	int size=CGrahamView::getSize(head);
	if(size==0)
	//	MessageBox("0");
	return false;
	index=index%size;
	if(index<0)
	return false;
	if(index==0)
	{
		p=head->next;
		head->next=p->next;
		delete p;
	}
	else
	{
		p=CGrahamView::index(head,index-1);
		node*q=p->next;
		p->next=q->next;
		delete q;
	}
	return true;
}

int CGrahamView::getSize(node* head)
{
	int size=0;
	node* p;
	p=head->next;
	while(p!=NULL)
	{
		size++;
		p=p->next;
	}
	return size;
}