testminvexcoreview.cpp

求点集的最小凸包Graham算法。给定平面上的一个点集

// TestMinvexCoreView.cpp : implementation of the CTestMinvexCoreView class
//

#include "stdafx.h"
#include "TestMinvexCore.h"
#include <math.h>
#include "TestMinvexCoreDoc.h"
#include "TestMinvexCoreView.h"

#define PI  3.14159265

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

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView

IMPLEMENT_DYNCREATE(CTestMinvexCoreView, CView)

BEGIN_MESSAGE_MAP(CTestMinvexCoreView, CView)
	//{{AFX_MSG_MAP(CTestMinvexCoreView)
	ON_COMMAND(ID_MCVEX, OnMcvex)
	ON_UPDATE_COMMAND_UI(ID_MCVEX, OnUpdateMcvex)
	ON_COMMAND(ID_POLOGON, OnPologon)
	ON_UPDATE_COMMAND_UI(ID_POLOGON, OnUpdatePologon)
	ON_WM_LBUTTONDOWN()
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView construction/destruction

CTestMinvexCoreView::CTestMinvexCoreView()
{
	m_pColor = RGB(0,0,0);
	m_drawType = DEFAULT;
	m_pBrush.CreateSolidBrush(m_pColor);
	PointNums = 0;
	m_drawding = false;
	OrderPointNums = 0;
	Plist.clear();
}

CTestMinvexCoreView::~CTestMinvexCoreView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView drawing

void CTestMinvexCoreView::OnDraw(CDC* pDC)
{
	CTestMinvexCoreDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
// 	int i;
// //	for(i=1; i<=PointNums ; i++)
// //		MarkPoint(pDC,PointList[i],i,3);
// 	for(i=0; i<OrderPointNums ; i++)
// 		MarkPoint(pDC,OrderPointList[i],i,4);


}

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CTestMinvexCoreView message handlers

void CTestMinvexCoreView::OnMcvex() 
{
	m_drawType = DEFAULT;
	int LowPt = FindTheLow(PointList,PointNums); //找到屏幕上最低的点

	OrderPointList[OrderPointNums] = PointList[LowPt];
	OrderPointNums++;
	//在原POINTLIST中去掉最低的点
	for(int i=LowPt; i<PointNums; i++)
	{
		PointList[i] = PointList[i+1];
	}
	PointNums--;
	//将点按顺时针排序
	ListThePointByRight();
	for (int j=0;j<=OrderPointNums;j++)
	MarkPoint(OrderPointList[j],j);
	ConvexList();
	
	CClientDC	dc(this);
	list<CPoint>::iterator Phead = Plist.begin();
	dc.MoveTo(*Phead);
	Phead++;

	for(;Phead!=Plist.end();Phead++){
		dc.LineTo(*Phead);
		dc.MoveTo(*Phead);
	}
	dc.LineTo(*Plist.begin());

}

void CTestMinvexCoreView::OnUpdateMcvex(CCmdUI* pCmdUI) 
{
	if(PointNums == 0 )
		pCmdUI->Enable(false);
	else pCmdUI->Enable(true);

	
}

void CTestMinvexCoreView::OnPologon() 
{
	PointNums = 0;
	OrderPointNums = 0;
	Plist.clear();
	Invalidate();
	m_drawType = POLOGON;
	
}

void CTestMinvexCoreView::OnUpdatePologon(CCmdUI* pCmdUI) 
{
	pCmdUI->SetCheck(m_drawType == POLOGON);	
}

void CTestMinvexCoreView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	CClientDC dc(this);
	switch(m_drawType)
	{
	case POLOGON:
		PointNums++;
		PointList[PointNums] = point;
		dc.Ellipse(point.x-2,point.y-2,point.x+2,point.y+2);
	//	MarkPoint(point,PointNums);
		break;
	case DEFAULT:
		break;
	}
	
	CView::OnLButtonDown(nFlags, point);
}

void CTestMinvexCoreView::MarkPoint(CPoint pt, int num)
{

	CClientDC dc(this);
	CString str;
	str.Format("%d",num);
	dc.Ellipse(pt.x-2,pt.y-2,pt.x+2,pt.y+3);
	dc.TextOut(pt.x+3,pt.y+3,str);
}

int CTestMinvexCoreView::FindTheLow(CPoint pt[], int ptN)
{
	int LowPN = 0;
	MinPoint = pt[0];
	for(int i=1; i<=ptN; i++)
	{
		if (pt[i].y > MinPoint.y)
		{
			MinPoint = pt[i];
			LowPN = i;
		}
	}
	return LowPN;
}

void CTestMinvexCoreView::ListThePointByRight()
{
	double bufAngle=0.0;
	for (int i=1; i<= PointNums ; i++)
	{
		if(PointList[i].x != MinPoint.x){
			bufAngle = atan( (PointList[i].y-MinPoint.y)
				/(double)(PointList[i].x - MinPoint.x) );
			if(PointList[i].x > MinPoint.x)
				bufAngle += PI;//如果点在最低点的右边则角度大于90度
			
		} else bufAngle = PI/2.0;
		
		for(int j=i; j>1; j--)
		{			
			if(bufAngle > Angle[j-1])	
				break;

		}
		for (int k=i; k > j ; k--)
		{
			Angle[k] = Angle[k-1];
			OrderPointList[k] = OrderPointList[k-1];
		}
		Angle[k] = bufAngle;
		OrderPointList[k] = PointList[i];
		OrderPointNums++;
	}
}

bool CTestMinvexCoreView::Judgerightleft(CPoint pt1, CPoint pt2, CPoint pt3)
{
	if(((pt2.x-pt1.x)*(pt3.y-pt2.y) - (pt2.y-pt1.y)*(pt3.x-pt2.x)) < 0)
		return	false;
	else
		return true;
}

void CTestMinvexCoreView::ConvexList()
{
	Plist.push_back(OrderPointList[0]);
	Plist.push_back(OrderPointList[1]);
	for (int i=2;i<OrderPointNums;)
	{
		list<CPoint>::iterator	Pend = Plist.end();
		list<CPoint>::iterator	Preend;
		Pend--; Preend = Pend; Pend--;
		if (Judgerightleft(*Pend,*Preend,OrderPointList[i]) == true)
		{
			Plist.push_back(OrderPointList[i]);
			i++;
		}
		else
			Plist.erase(Preend);	
		}
}