convexhullview.cpp

凸包算法在VC6下实现

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

#include "stdafx.h"
#include "convexHull.h"

#include "convexHullDoc.h"
#include "convexHullView.h"
#include "MyConvexHull.h"
#include "SetDialog.h"

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

extern COLORREF lineColor, nodeColor;
extern int nodeType, N, xMin, xMax, yMin, yMax;
extern CString pDataFileName; 

BOOL setFlag,okRunFlag;
CMyConvexHull ch;


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

IMPLEMENT_DYNCREATE(CConvexHullView, CView)

BEGIN_MESSAGE_MAP(CConvexHullView, CView)
	//{{AFX_MSG_MAP(CConvexHullView)
	ON_COMMAND(ID_RUN, OnRun)
	ON_COMMAND(ID_SET, OnSet)
	//}}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
    setFlag = false;
	okRunFlag = false;
}

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
}

/////////////////////////////////////////////////////////////////////////////
// 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



void CConvexHullView::MakeNodes()
{
   //生成随机点
	if(pDataFileName.IsEmpty() || !N) return; 
   CFile dataFile;
   dataFile.Open(pDataFileName,CFile::modeCreate|CFile::modeWrite);
   dataFile.SeekToBegin();  
   dataFile.Write(&N, sizeof(int));
   int rx,ry;
   int dx = xMax - xMin;
   int dy = yMax - yMin;
   for(int i=0; i<N; i++)
   {
	   if(dx!=0)
		  rx = xMin + rand()%dx;
	   else rx = xMin;
	   if(dy!=0)
		  ry = yMin + rand()%dy;
	   else ry = yMin;
	   dataFile.Write(&rx, sizeof(int));  
	   dataFile.Write(&ry, sizeof(int));
   }  
    dataFile.Flush();
    dataFile.Close();
	okRunFlag = true;
}

void CConvexHullView::ShowNodes()
{
	//绘制随机点
	CClientDC dc(this);
	CPen pen(0, 1, nodeColor);
	dc.SelectObject(&pen);
	int i;
	CPoint p1,p2;
	if(nodeType == 0)
	{
		for(i=0; i<N; i++)
		{ 
			dc.Ellipse(ch.node[i].x-2,ch.node[i].y-2,ch.node[i].x+2,ch.node[i].y+2);
		}
	}
	else if(nodeType == 1)
	{ 
		for(i=0; i<N; i++)
		{
			p1.x = ch.node[i].x-2;
			p1.y = ch.node[i].y;
			p2.x = ch.node[i].x+2;
			p2.y = ch.node[i].y;
			dc.MoveTo(p1);
			dc.LineTo(p2);
			p1.x = ch.node[i].x;
			p1.y = ch.node[i].y-2;
			p2.x = ch.node[i].x;
			p2.y = ch.node[i].y+2;
			dc.MoveTo(p1);
			dc.LineTo(p2);
		}
	} 
}

void CConvexHullView::ShowConvexHull()
{
	//绘制凸包计算的结果
	CClientDC dc(this);
	CPen pen(0, 2, lineColor);
	dc.SelectObject(&pen);
	if(N == 1) return;
	else if(N == 2)
	{
		dc.MoveTo(ch.node[0].x, ch.node[0].y);
		dc.LineTo(ch.node[1].x, ch.node[1].y);
		return;
	}	
    dc.MoveTo(ch.node[ch.V[ch.back]].x, ch.node[ch.V[ch.back]].y);
	int i;
	for(i=ch.back+1;i<ch.front;i++){
		dc.LineTo(ch.node[ch.V[i]].x,ch.node[ch.V[i]].y);
		dc.MoveTo(ch.node[ch.V[i]].x,ch.node[ch.V[i]].y);		
	}
	dc.LineTo(ch.node[ch.V[ch.back]].x,ch.node[ch.V[ch.back]].y);
}

void CConvexHullView::OnSet() 
{
	//凸包计算预设置
	setFlag = true;
	CSetDialog dlg;
	if(IDOK==dlg.DoModal())
	{
		MakeNodes();		
	}	
}

void CConvexHullView::OnRun() 
{
	if(!setFlag || !okRunFlag)
	{
		MessageBox("请先做预设置吧！^-^");
		return;
	}    
    ch.InputData(pDataFileName);
	DWORD dwStart = GetTickCount();
//	clock_t start,finish;
//	double duration;
//	start = clock();
    ch.Solve();
//	finish = clock();
//    duration = (double)(finish - start)*1000 / CLOCKS_PER_SEC;
//	CString str;
//	str.Format("凸包算法耗时为：%f ms", duration);    
	DWORD t = GetTickCount() - dwStart;
	CString str;
	str.Format("凸包算法耗时为：%d ms", t);
	ShowNodes();
    ShowConvexHull();
	MessageBox(str);
}