convexhulldoc.cpp

凸包可视化程序

// ConvexHullDoc.cpp : implementation of the CConvexHullDoc class
//

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

#include "ConvexHullDoc.h"
#include <cmath>
#include <fstream>
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CConvexHullDoc

IMPLEMENT_DYNCREATE(CConvexHullDoc, CDocument)

BEGIN_MESSAGE_MAP(CConvexHullDoc, CDocument)
	//{{AFX_MSG_MAP(CConvexHullDoc)
		// 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()

/////////////////////////////////////////////////////////////////////////////
// CConvexHullDoc construction/destruction

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

}

CConvexHullDoc::~CConvexHullDoc()
{
}

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

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

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CConvexHullDoc serialization

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

/////////////////////////////////////////////////////////////////////////////
// CConvexHullDoc diagnostics

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

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

/////////////////////////////////////////////////////////////////////////////
// CConvexHullDoc commands

void CConvexHullDoc::PointsSort()
{   
	CPoint XDOWN;
	int sumx=0,sumy=0;
	MyPoint *cur=m_Link.m_First;
	while(cur){
		sumx+=cur->p.x;
		sumy+=cur->p.y;
		cur=cur->right;
	}
	m_Center.x=XDOWN.x=sumx/m_Link.Length();
	m_Center.y=sumy/m_Link.Length();
	XDOWN.y=m_Center.y+10;
                    
	for(cur=m_Link.m_First;cur;cur=cur->right){   //计算每个点的COS值
		double temp=Cos(m_Center,XDOWN,cur->p); 	  
		cur->CosAngle=temp;	
	}
 	for(cur=m_Link.m_First;cur;cur=cur->right){//左右点分开			
		for(MyPoint *next=cur->right;next;next=next->right){
			if(cur->p.x>=m_Center.x) break;
			if(next->p.x>=m_Center.x) {
				SwapPoint(*cur,*next);
				if(cur==m_Link.m_First){
						 m_Link.m_First=next;		  
				}
				MyPoint *temp=next;
				next=cur;
				cur=temp;
			    break;
			}
		}
		if(next==NULL) break;		
	}

	for(cur=m_Link.m_First;cur->p.x>=m_Center.x;cur=cur->right){//中点右边的点排序
		MyPoint *k=cur;
		for(MyPoint *next=cur->right;next->p.x>=m_Center.x;next=next->right){ 
			if(next->CosAngle>k->CosAngle) k=next;
		}
		SwapPoint(*cur,*k);
        if(cur==m_Link.m_First){
			m_Link.m_First=k;
		}
		MyPoint *temp=k;
		k=cur;
		cur=temp;
	}
		
	for(;cur;cur=cur->right){//中点左边的点排序
		MyPoint *k=cur;
		for(MyPoint *next=cur->right;next;next=next->right){ 
		if(next->CosAngle<k->CosAngle) k=next;
		}
		SwapPoint(*cur,*k);
		if(cur==m_Link.m_First){
			m_Link.m_First=k;
		}
		MyPoint *temp=k;
		k=cur;
		cur=temp;
	}	
}


double CConvexHullDoc::Cos(CPoint &o ,CPoint &s, CPoint &e)
{  
	int x1=s.x-o.x;
	int x2=e.x-o.x;
	int y1=o.y-s.y;
	int y2=o.y-e.y;
    return double((x1*x2+y1*y2)/(sqrt(x1*x1+y1*y1)*sqrt(x2*x2+y2*y2)));
}
void CConvexHullDoc::SwapPoint(MyPoint &a,MyPoint &b){
     MyPoint *l=b.left,*r=b.right;
	 b.left=a.left;//	 
	 if(a.right==&b){
        a.left=&b;
		b.right=&a;
	 }
	 else{
		a.left=l;
		b.right=a.right;
	 }		 
	 a.right=r;//
	 if(b.left){
		 b.left->right=&b;
	 }
	 if(b.right){
		 b.right->left=&b;
	 }
	 if(a.left){
		 a.left->right=&a;
	 } 
	 if(a.right){
	     a.right->left=&a;
	 }
}
int CConvexHullDoc::Judge180(MyPoint &o,MyPoint &s,MyPoint &e)
{     
	return ((s.p.x-o.p.x)*(e.p.y-o.p.y)-(e.p.x-o.p.x)*(s.p.y-o.p.y));	
}

void CConvexHullDoc::Search()
{   
    for(MyPoint *x=m_Link.m_First,*rx=x->right,*rrx=rx->right;rx&&rrx;){		
		if(Judge180(*rx,*x,*rrx)<=0){			
			x->right=rrx;
			rrx->left=x;					
			if(x->left){
				x=x->left;	
			}
			delete rx;
			rx=x->right;
							
		}
		else{
			x=rx;rx=rrx;
		}
		rrx=rx->right;			
    }
	
    MyPoint *last=m_Link.Back();
	if(Judge180(*last,*last->left,*m_Link.m_First)<=0){
		 last->left->right=NULL;
		 delete last;
         last=m_Link.Back();
	}
 	if(Judge180(*m_Link.m_First,*last,*m_Link.m_First->right)<=0){
         m_Link.m_First->right->left=0;
         MyPoint *temp=m_Link.m_First;
		 m_Link.m_First=m_Link.m_First->right;
		 delete temp;
		 
	}
    
}