convexhullview.cpp

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

// ConvexHullView.cpp : implementation of the CConvexHullView class
//

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

#include "ConvexHullDoc.h"
#include "ConvexHullView.h"

#include "DlgPointNum.h"
#include "DlgPointType.h"

#include <time.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/timeb.h>

#define ORA_X(x) ((x)-m_rRange.left)
#define ORA_Y(y) ((y)-m_rRange.top)

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

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView

IMPLEMENT_DYNCREATE(CConvexHullView, CView)

BEGIN_MESSAGE_MAP(CConvexHullView, CView)
	//{{AFX_MSG_MAP(CConvexHullView)
	ON_COMMAND(IDM_GetRandomPoint, OnGetRandomPoint)
	ON_COMMAND(IDM_GetRange, OnGetRange)
	ON_WM_LBUTTONDOWN()
	ON_WM_MOUSEMOVE()
	ON_WM_LBUTTONUP()
	ON_COMMAND(IDM_SetPointNum, OnSetPointNum)
	ON_COMMAND(IDM_SetPointType, OnSetPointType)
	ON_COMMAND(IDM_RUN, OnRun)
	ON_COMMAND(IDM_DerivePoint, OnDerivePoint)
	ON_COMMAND(IDM_ImportPoint, OnImportPoint)
	ON_WM_DESTROY()
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView construction/destruction

CConvexHullView::CConvexHullView()
{
	// TODO: add construction code here
	m_bIsInited=false;
	m_bGetRange=false;
	m_bMouseDown=false;
	m_bShowEllipse=true;
	m_bNoPoint=true;
	m_nPointNum=100;
	m_rRange.top=50;m_rRange.left=50;m_rRange.bottom=400;m_rRange.right=500;

}

CConvexHullView::~CConvexHullView()
{
}

BOOL CConvexHullView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView drawing

void CConvexHullView::OnDraw(CDC* pDC)
{
	CConvexHullDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	if(!m_bIsInited)
	{	
		InitBitmap();
		
		m_bIsInited=true;
	}

	CDC dc_Compatible;
	dc_Compatible.CreateCompatibleDC(pDC);
	dc_Compatible.SelectObject(&m_Bitmap);

	pDC->BitBlt(m_rRange.left,m_rRange.top,m_rRange.Width(),m_rRange.Height(),&dc_Compatible,
		0,0,SRCCOPY);
}

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView printing

BOOL CConvexHullView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CConvexHullView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CConvexHullView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView diagnostics

#ifdef _DEBUG
void CConvexHullView::AssertValid() const
{
	CView::AssertValid();
}

void CConvexHullView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CConvexHullDoc* CConvexHullView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CConvexHullDoc)));
	return (CConvexHullDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CConvexHullView message handlers

CPointArray* CConvexHullView::GetRandomPoint(int num,CRect& rect)
{
	CPointArray* points=new CPointArray();
	CPointNode* temp=NULL;
//	srand( (unsigned)time( NULL ) );
	int width=rect.Width();
	int height=rect.Height();
	for(int i=0;i<num;i++)
	{
		int x=(int)(RANDOM*width+rect.left);
		int y=(int)(RANDOM*height+rect.top);
		temp=new CPointNode(x,y);
		
		points->Add(temp);
	}
	return points;
}

void CConvexHullView::ShowPoints(CPointArray &pa,bool bNum)
{
	CClientDC dc(this);
	CPointNode* temp=pa.first;
	
	CDC dc_Compatible;
	dc_Compatible.CreateCompatibleDC(&dc);
	dc_Compatible.SelectObject(&m_Bitmap);
	
	CPen pen(PS_DASH,1,RGB(0,0,255));
	CPen* oldpen=dc_Compatible.SelectObject(&pen);

	if(bNum){
		CPen pen(PS_DASH,1,RGB(0,0,255));
		CPen* oldpen=dc_Compatible.SelectObject(&pen);
		if(m_bShowEllipse)
			dc_Compatible.Ellipse(ORA_X(m_ConvexHull.pP0->point.x-2),ORA_Y(m_ConvexHull.pP0->point.y-2),
				ORA_X(m_ConvexHull.pP0->point.x+2),ORA_Y(m_ConvexHull.pP0->point.y+2));
		else
		{
			dc_Compatible.MoveTo(ORA_X(m_ConvexHull.pP0->point.x-2),ORA_Y(m_ConvexHull.pP0->point.y));
			dc_Compatible.LineTo(ORA_X(m_ConvexHull.pP0->point.x+3),ORA_Y(m_ConvexHull.pP0->point.y));
			dc_Compatible.MoveTo(ORA_X(m_ConvexHull.pP0->point.x),ORA_Y(m_ConvexHull.pP0->point.y-2));
			dc_Compatible.LineTo(ORA_X(m_ConvexHull.pP0->point.x),ORA_Y(m_ConvexHull.pP0->point.y+3));
		}
		dc_Compatible.SelectObject(oldpen);
	}
	
	int i=1;
	while(temp)
	{
		if(m_bShowEllipse)
			dc_Compatible.Ellipse(ORA_X(temp->point.x-2),ORA_Y(temp->point.y-2),
				ORA_X(temp->point.x+2),ORA_Y(temp->point.y+2));
		else
		{
			dc_Compatible.MoveTo(ORA_X(temp->point.x-2),ORA_Y(temp->point.y));
			dc_Compatible.LineTo(ORA_X(temp->point.x+3),ORA_Y(temp->point.y));
			dc_Compatible.MoveTo(ORA_X(temp->point.x),ORA_Y(temp->point.y-2));
			dc_Compatible.LineTo(ORA_X(temp->point.x),ORA_Y(temp->point.y+3));
		}
		if(bNum)
		{
			CString str;
			str.Format("%d",i);
			dc_Compatible.TextOut(ORA_X(temp->point.x),ORA_Y(temp->point.y),str);
			i++;
		}
		temp=temp->next;
	}
	dc_Compatible.SelectObject(oldpen);
	Invalidate();
}


void CConvexHullView::OnGetRandomPoint() 
{
	// TODO: Add your command handler code here
	::SetCursor(LoadCursor(NULL,IDC_WAIT));	
	if(m_bGetRange)
	{
		MessageBox("请先选择显示区域！","未选择显示区域");
		return;
	}
	InitBitmap();

	if(!m_bNoPoint){
		delete m_ppa;
		m_ppa=NULL;
	}

	m_ppa=GetRandomPoint(m_nPointNum,m_rRange);

	m_bNoPoint=false;
	ShowPoints(*m_ppa,false);
	Invalidate();
	::SetCursor(LoadCursor(NULL,IDC_ARROW));
}

void CConvexHullView::LinkPoints(CPointArray &pa)
{
	CClientDC dc(this);
	
	CDC dc_Compatible;
	dc_Compatible.CreateCompatibleDC(&dc);
	dc_Compatible.SelectObject(&m_Bitmap);
	
	if(!pa.first) return;
	
	CPointNode* pretemp=pa.first,*temp=pa.first->next;
	while (temp)
	{
		dc_Compatible.MoveTo(ORA_X(pretemp->point.x),ORA_Y(pretemp->point.y));
		dc_Compatible.LineTo(ORA_X(temp->point.x),ORA_Y(temp->point.y));
		pretemp=temp;
		temp=temp->next;
	}
	dc_Compatible.MoveTo(ORA_X(pretemp->point.x),ORA_Y(pretemp->point.y));
	dc_Compatible.LineTo(ORA_X(pa.first->point.x),ORA_Y(pa.first->point.y));
	Invalidate();
}

//DEL void CConvexHullView::OnGraham() 
//DEL {
//DEL 	// TODO: Add your command handler code here
//DEL 	::SetCursor(LoadCursor(NULL,IDC_WAIT));
//DEL 	m_ConvexHull.Graham();
//DEL 	LinkPoints(m_ConvexHull.ConvexHullStack);
//DEL 	::SetCursor(LoadCursor(NULL,IDC_ARROW));
//DEL }

void CConvexHullView::OnGetRange() 
{
	// TODO: Add your command handler code here
	///////////////////////////////////////////////
	if(!m_bNoPoint){
		delete m_ppa;//只释放资源，并不将其置为NULL。
		m_ppa=NULL;
	}
	m_bNoPoint=true;
	////////////////////////////////////////////////
	m_bIsInited=false;
	m_bGetRange=true;
	Invalidate();
}

void CConvexHullView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(m_bGetRange)
	{
		::SetCapture(m_hWnd);
		m_bMouseDown=true;
		m_pOldPoint.x=m_pFromPoint.x=point.x;
		m_pOldPoint.y=m_pFromPoint.y=point.y;
	}
	CView::OnLButtonDown(nFlags, point);
}

void CConvexHullView::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CClientDC dc(this);
	if(m_bGetRange&&m_bMouseDown){
		CPen pen(PS_DASH,1,RGB(255,0,0));
		CPen* oldpen=dc.SelectObject(&pen);
		dc.SetROP2(R2_NOTXORPEN);
		dc.Rectangle(m_pFromPoint.x,m_pFromPoint.y,m_pOldPoint.x,m_pOldPoint.y);
		dc.SetROP2(R2_COPYPEN);
		m_pOldPoint=point;
		dc.Rectangle(m_pFromPoint.x,m_pFromPoint.y,m_pOldPoint.x,m_pOldPoint.y);
		dc.SelectObject(oldpen);
	}
	CView::OnMouseMove(nFlags, point);
}

void CConvexHullView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(m_bGetRange)
	{
		::ReleaseCapture();
		m_bMouseDown=false;
		m_rRange.left=m_pFromPoint.x;
		m_rRange.top=m_pFromPoint.y;
		m_rRange.right=point.x;
		m_rRange.bottom=point.y;
		m_pOldPoint=point;
		
		m_bGetRange=false;
		m_bIsInited=false;
		Invalidate();
	}
	CView::OnLButtonUp(nFlags, point);
}

void CConvexHullView::OnSetPointNum() 
{
	// TODO: Add your command handler code here
	CDlgPointNum dlgPointNum;
	dlgPointNum.m_pointnum=m_nPointNum;
	if(IDOK==dlgPointNum.DoModal())
	{
		m_nPointNum=dlgPointNum.m_pointnum;
	}
}

void CConvexHullView::OnSetPointType() 
{
	// TODO: Add your command handler code here
	CDlgPointType dlgPointType;
	dlgPointType.m_nPointType=m_bShowEllipse?0:1;
	if(IDOK==dlgPointType.DoModal())
	{
		m_bShowEllipse=(dlgPointType.m_nPointType==0)?true:false;
	}
}

void CConvexHullView::InitBitmap()
{
	CClientDC dc(this);
	CRect rect;
	GetClientRect(&rect);
	
	m_Bitmap.DeleteObject();
	m_Bitmap.CreateCompatibleBitmap(&dc,m_rRange.Width(),m_rRange.Height());
	
	CDC dc_Compatible;
	dc_Compatible.CreateCompatibleDC(&dc);
	dc_Compatible.SelectObject(&m_Bitmap);
	dc_Compatible.BitBlt(0,0,m_rRange.Width(),m_rRange.Height(),
		&dc,m_rRange.left,m_rRange.top,WHITENESS);
	if(!m_bGetRange)
	{
		CPen pen(PS_DASH,1,RGB(255,0,0));
		CPen* oldpen=dc_Compatible.SelectObject(&pen);
		dc_Compatible.Rectangle(0,0,m_rRange.Width(),m_rRange.Height());
		dc_Compatible.SelectObject(oldpen);
	}
}

void CConvexHullView::OnRun() 
{
	// TODO: Add your command handler code here
	
	if(m_bNoPoint){
		if(m_bGetRange)
		{
			MessageBox("请先选择显示区域！","未选择显示区域");
			return;
		}
		::SetCursor(LoadCursor(NULL,IDC_WAIT));
//////////////////初始化/////////////////////////////
		InitBitmap();
/////////////////////////////////////////////////////
		m_ppa=GetRandomPoint(m_nPointNum,m_rRange);
		ShowPoints(*m_ppa,false);
		m_bNoPoint=false;
		::SetCursor(LoadCursor(NULL,IDC_ARROW));
	}
	else{
		SYSTEMTIME tbegin,tend;
		clock_t cbegin,cend;
		::SetCursor(LoadCursor(NULL,IDC_WAIT));

		GetLocalTime(&tbegin);
		cbegin=clock();
		
		m_ConvexHull.LoadPointArray(m_ppa);
//		ShowPoints(m_ConvexHull.pointSet,true);
		m_ConvexHull.Graham();

		GetLocalTime(&tend);
		cend=clock();

		LinkPoints(m_ConvexHull.ConvexHullStack);

		m_ConvexHull.Destroy();//释放资源。
		m_bNoPoint=true;
		::SetCursor(LoadCursor(NULL,IDC_ARROW));
/*
		CClientDC dc(this);
		CDC dc_Compatible;
		dc_Compatible.CreateCompatibleDC(&dc);
		dc_Compatible.SelectObject(&m_Bitmap);*/

		CString str;
		int ms=0;
		if(tend.wSecond==tbegin.wSecond)
			ms=tend.wMilliseconds-tbegin.wMilliseconds;
		else if(tend.wMinute==tbegin.wMinute)
			ms=tend.wMilliseconds+(tend.wSecond-tbegin.wSecond)*1000-tbegin.wMilliseconds;
		else if(tend.wHour==tbegin.wHour)
			ms=(tend.wMinute-tbegin.wMinute)*60*1000+
				tend.wMilliseconds+(tend.wSecond-tbegin.wSecond)*1000-tbegin.wMilliseconds;
		else if(tend.wDay==tbegin.wDay)
			ms=(tend.wHour-tend.wHour)*60*60*1000+(tend.wMinute-tbegin.wMinute)*60*1000+
				tend.wMilliseconds+(tend.wSecond-tbegin.wSecond)*1000-tbegin.wMilliseconds;
		double c=((double)((cend-cbegin)*1000.0))/CLOCKS_PER_SEC;
		
		str.Format("by SYSTEMTIME: %dms\nby clock_t:    %6.2fms",ms,c);
		
//		dc_Compatible.TextOut(1,1,str);

		MessageBox(str,"计算时间");
	}

	Invalidate();
}

void CConvexHullView::OnDerivePoint() 
{
	// TODO: Add your command handler code here
	if(m_bNoPoint)
	{
		MessageBox("请先创建随机点!","尚未创建随机点");
		return;
	}
	CFileDialog dlg(false);
	if(IDOK==dlg.DoModal())
	{
		SetCursor(LoadCursor(NULL,IDC_WAIT));
		CString strPath=dlg.GetPathName();
		CFile file(strPath,CFile::modeCreate|CFile::modeWrite);
		int nCount=m_ppa->length;
		file.Write(&nCount,4);
		CPointNode* temp=m_ppa->first;
		for(int i=0;i<nCount;i++)
		{
			file.Write(&temp->point.x,4);
			file.Write(&temp->point.y,4);
			temp=temp->next;
		}
		file.Close();
		SetCursor(LoadCursor(NULL,IDC_ARROW));
	}
}

void CConvexHullView::OnImportPoint() 
{
	// TODO: Add your command handler code here
	CFileDialog dlg(true);
	if(IDOK==dlg.DoModal())
	{
		::SetCursor(LoadCursor(NULL,IDC_WAIT));
		m_rRange.left=0;
		m_rRange.top=0;
		m_rRange.right=1020;
		m_rRange.bottom=653;
		
		InitBitmap();
		if(!m_bNoPoint){
			delete m_ppa;
			m_ppa=NULL;
		}
		
		CString strPath=dlg.GetPathName();
		CFile file(strPath,CFile::modeRead);

		int nCount;
		file.Read(&nCount,4);
		m_nPointNum=nCount;
		
		m_ppa=new CPointArray();
		CPointNode* temp;
		int x,y;
		for(int i=0;i<nCount;i++)
		{
			file.Read(&x,4);
			file.Read(&y,4);
			temp=new CPointNode(x,y);
			m_ppa->Add(temp);
		}
		file.Close();
		m_bNoPoint=false;
		ShowPoints(*m_ppa,false);	
		::SetCursor(LoadCursor(NULL,IDC_ARROW));
	}
}

void CConvexHullView::OnDestroy() 
{
	CView::OnDestroy();
	// TODO: Add your message handler code here
	if(!m_bNoPoint)
	{
		delete m_ppa;
		m_ppa=NULL;
	}
	
}