凸包doc.cpp

凸包问题~基于mfc的实现。界面粗糙点

// 凸包Doc.cpp : implementation of the CMyDoc class
//

#include "stdafx.h"
#include "凸包.h"

#include "凸包Doc.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CMyDoc

IMPLEMENT_DYNCREATE(CMyDoc, CDocument)

BEGIN_MESSAGE_MAP(CMyDoc, CDocument)
	//{{AFX_MSG_MAP(CMyDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDoc construction/destruction

CMyDoc::CMyDoc()
{
	// TODO: add one-time construction code here

}

CMyDoc::~CMyDoc()
{
}

BOOL CMyDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CMyDoc serialization

void CMyDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CMyDoc diagnostics

#ifdef _DEBUG
void CMyDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CMyDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMyDoc commands
Node::Node(long double p_x,long double p_y)
{
	x=p_x;
	y=p_y;
}
Node::~Node()
{

}
long double Node::X()
{
	return x;
}
long double Node::Y()
{
	return y;
}
Link::Link()
{
	now=LeftEnd=RightEnd=0;
	num=0;
	length=0;
}
Link::~Link()
{
	
}
Node& Link::Now()
{
	return *now;
}
bool Link::Find(int k)         //now指向第k个元素 1,2,3,4
{
	if (k<1)return false;
	Node *find=LeftEnd;
	int index=1;
	while (index<k&&find!=RightEnd)
	{
		find=find->right;
		index++;
	}
	if (find) 
	{
		now=find;
		return true;
	}
	return false;
}
Link& Link::Insert(int k,long double x,long double y)///k=0,1,2,3,4插入后成为第k+1个数
{
	Node *mid=new Node(x,y);
	if (LeftEnd==0&&RightEnd==0)
	{
		if (k==0)
		{
			RightEnd=LeftEnd=mid;
		    LeftEnd->left=RightEnd;
	        RightEnd->right=LeftEnd;
	    	mid->left=LeftEnd;
	    	mid->right=RightEnd;
	    	LeftEnd->right=mid;
	    	RightEnd->left=mid;
	    	now=mid;
		}
		else if(k==1&&now!=0)
		{	
			{
				mid->left=now;
			    mid->right=now->right;
	        	now->right->left=mid;
    		    now->right=mid;
    			if (now==RightEnd)
				{
					RightEnd=mid;
				}
				now=mid;
			}
		}
	}
	else if(Find(k))
		{	
			{
				mid->left=now;
			    mid->right=now->right;
	        	now->right->left=mid;
    		    now->right=mid;
    			if (now==RightEnd)
				{
					RightEnd=mid;
				}
				now=mid;
			}
		}
	length++;
	return *this;
}
Link& Link::Delete(int k)//k=1,2,3,4  删除第k个元素，now指向后一个
{
	if (Find(k))
	{
		Node *p=now->right;
		now->left->right=now->right;
		now->right->left=now->left;
		delete now;
		now=p;
		if (k==1)
		{
			LeftEnd=now;
		}
		else if (now==LeftEnd)
		{
			RightEnd=LeftEnd->left;
		}
	}
	length--;
	return *this;
}
int Link::Num(Node &x)
{
	Node *p=LeftEnd;
	int index=1;
	while (p!=&x)
	{
		index++;
		p=p->right;
	}
	return index;
}
/////////////////////////////////////////////
long double Rad(long double x0,long double y0,long double x,long double y)//(x0,y0)为基准点，（x,y）为所求点
{
	if (x==x0&&y!=y0)
	{
		return 3.1415926/2;
	}
	else if (y==y0)
	{
		return 0;
	}
	else
	{
		long double mid=atan((y0-y)/(x-x0));
		if(mid<0) mid=mid+3.1415926;
		return mid;

	}
}
///////////////////////////////////////////////
bool Link::IsLine()
{
	Node *mid=LeftEnd;
	long double rad=Rad(LeftEnd->x,LeftEnd->y,mid->right->x,mid->right->y);
	long double mid_rad;
	for (;mid->right!=LeftEnd;)
	{
		mid=mid->right;
		mid_rad=Rad(LeftEnd->x,LeftEnd->y,mid->x,mid->y);
		if(rad!=mid_rad)
			return false;
	}
	return true;
}
//////////////////////////////////////////////
Node& Link::Find_Node_max_y()
{
	Node *mid=LeftEnd->right;
	Node *max_Node=LeftEnd;
	long double index=LeftEnd->y;
	for (int i=0;i<length;i++)
	{
		if(index<mid->y)
		{
			index=mid->y;
			max_Node=mid;
		}	
		mid=mid->right;
	}
	return *max_Node;

}
/////////////////////////////////////////////
Node& Link::Find_Node_min_x()
{
	Node *mid=LeftEnd->right;
	Node *min_Node=LeftEnd;
	long double index=LeftEnd->x;
	for (int i=0;i<length;i++)
	{
		if(index>mid->x)
		{
			index=mid->x;
			min_Node=mid;
		}	
		mid=mid->right;
	}
	return *min_Node;
}
//////////////////////////////////////////////
long double Point_length(long double x0,long double y0,long double x,long double y)
{
	return sqrt(pow(x-x0,2)+pow(y-y0,2));
}
///////////////////////////////////////////
void Link::Line_Delete()
{
	Node *m_x=&Find_Node_min_x();
	Node *m_y=&Find_Node_max_y();
	Node *mid=LeftEnd;
	Node *p=mid;
	for (;mid->right!=LeftEnd;)
	{
		if (mid!=m_x&&mid!=m_y)
		{
			p=mid->right;
			Delete(Num(*mid));
			mid=p;
		}
		else
		{
			mid=mid->right;
		}
	}
}
////////////////////////////////////////////////
void swap(long double& x, long double& y)
{
	long double mid;
	mid=x,x=y,y=mid;
}
/////////////////////////////////////////////
void Link::PaiXu()
{
	Node *p_y=&Find_Node_max_y();
	Node *mid=LeftEnd;
	long double f=0;
	long double l_rad,n_rad;
	for (int i=0;i<length;i++)
	{
		mid=LeftEnd;
		for (int j=length-i-1;j>0;j--)
		{
			l_rad=Rad(p_y->x,p_y->y,mid->x,mid->y);
			n_rad=Rad(p_y->x,p_y->y,mid->right->x,mid->right->y);
			if (l_rad>n_rad)
			{
				swap(mid->x,mid->right->x);
				swap(mid->y,mid->right->y);
				p_y=&Find_Node_max_y();
			}
			if (l_rad==n_rad)
			{
				if (Point_length(p_y->x,p_y->y,mid->x,mid->y)>Point_length(p_y->x,p_y->y,mid->right->x,mid->right->y))
				{
					swap(mid->x,mid->right->x);
				    swap(mid->y,mid->right->y);
				    p_y=&Find_Node_max_y();
				}
			}
			mid=mid->right;
		}
	}
}
//////////////////////////////////////////////
long double Link::Tp_rad(Node last,Node mid,Node next)
{
	long double fi_se,se_th;
	fi_se=Rad(last.x,last.y,mid.x,mid.y);
	se_th=Rad(mid.x,mid.y,next.x,next.y);
	long double sub;
	sub=fi_se-se_th;
	if(sub<0) sub=-sub;
	if (last.y>mid.y&&next.y<mid.y)
	{
		if (mid.x>=(mid.y-last.y)*(next.x-last.x)/(next.y-last.y)+last.x)
		{
			return 3.1415926+sub;
		}
		else if (mid.x<(mid.y-last.y)*(next.x-last.x)/(next.y-last.y)+last.x)
		{
			return 3.1415926-sub;
		}

	}
	else if (last.y<mid.y&&next.y>mid.y)
	{
		if (mid.x>=(mid.y-last.y)*(next.x-last.x)/(next.y-last.y)+last.x)
		{
			return 3.1415926-sub;
		}
		else if (mid.x<(mid.y-last.y)*(next.x-last.x)/(next.y-last.y)+last.x)
		{
			return 3.1415926+sub;
		}
		
	}/////////////////////////////////////////
	else if (last.y>mid.y&&next.y>mid.y)
	{
		if (next.x<mid.x&&mid.x<last.x)
		{
			return 2*3.1415926-sub;
		}
		else if (next.x>mid.x&&mid.x>last.x)
		{
			return sub;
		}
		else if (next.x<mid.x&&mid.x>last.x||next.x>mid.x&&mid.x<last.x)
		{
			if (fi_se<se_th)
			{
				return sub;
			}
			else if (fi_se>se_th)
			{
				return 2*3.1415926-sub;
			}
			else return 0;
		}
		
	}
	else if (last.y<mid.y&&next.y<mid.y)
	{
		if (next.x<mid.x&&mid.x<last.x)
		{
			return sub;
		}
		else if (next.x>mid.x&&mid.x>last.x)
		{
			return 2*3.1415926-sub;
		}
		else if (next.x<mid.x&&mid.x>last.x||next.x>mid.x&&mid.x<last.x)
		{
			if (fi_se<se_th)
			{
				return sub;
			}
			else if (fi_se>se_th)
			{
				return 2*3.1415926-sub;
			}
			else return 0;
		}
	}
	else if (last.y==mid.y)
	{
		if (last.x>mid.x)
		{
			if (next.y>last.y)
			{
				return 2*3.1415926-sub;
			}
			else if (next.y<last.y)
			{
				return sub;
			}
			else return 0;
			 	
		}
		else if (last.x<mid.x)
		{
			if (next.y>last.y)
			{
				return sub;
			}
			else if (next.y<last.y)
			{
				return 2*3.1415926-sub;
			}
			else return 0;			
		}
	}
	else if (next.y==mid.y)
	{
		if (next.x>mid.x)
		{
			if (last.y>next.y)
			{
				return sub;
			}
			else if (last.y<next.y)
			{
				return 2*3.1415926-sub;
			}
			else return 0;
		}
		else if (next.x<mid.x)
		{
			if (last.y>next.y)
			{
				return 2*3.1415926-sub;
			}
			else if (last.y<next.y)
			{
				return sub;
			}
			else return 0;
		}
	}
}
/////////////////////////////////////////////////
void Link::Delete_NN()
{
	Node *max_y=&Find_Node_max_y();
	Node *mid=LeftEnd;
	for(;mid->right!=LeftEnd;) 
	{
		long double mid_rad=Tp_rad(*mid,*mid->right,*mid->right->right);
		if (mid_rad<=3.1415926)
		{
			//Node *p=;
			Delete(Num(*(mid->right)));
			mid=mid->left;
		}
		else
		{
			mid=mid->right;
		}
	} 
	
}
/////////////////////////////////////////////////
Link& Link::TuBao()
{
	if (length<3)
	{
		return *this;
	}
	if (IsLine())
	{
		Line_Delete();
		return *this;
	}
	PaiXu();
	Delete_NN();
	return *this;
}
int Link::Length()
{
	return length;
}