testminvexcoreview.cpp

我同学写的一个最小凸包的算法程序！注释详尽

// 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;
	LastPointNums = 0;
	m_drawding = false;
	OrderPointNums = 0;
}

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+1,4);
	pDC->MoveTo(LastPoint[0]);
	for (i=0; i<=LastPointNums; i++)
	{
		pDC->LineTo(LastPoint[i]);
		pDC->MoveTo(LastPoint[i]);
	}
	pDC->LineTo(LastPoint[0]);


}

/////////////////////////////////////////////////////////////////////////////
// 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); //找到屏幕上最低的点
	LastPointNums = 0;
	OrderPointList[OrderPointNums] = PointList[LowPt];
	OrderPointNums++;
	//在原POINTLIST中去掉最低的点
	for(int i=LowPt; i<PointNums; i++)
	{
		PointList[i] = PointList[i+1];
	}
	PointNums--;
	//将点按顺时针排序
	ListThePointByRight();
	Makecvx(OrderPointList,OrderPointNums);
	Invalidate();
}

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

	
}

void CTestMinvexCoreView::OnPologon() 
{
	PointNums = 0;
	OrderPointNums = 0;
	LastPointNums = 0;
	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;
		MarkPoint(&dc,point,PointNums,3);
		break;
	case DEFAULT:
		break;
	}
	
	CView::OnLButtonDown(nFlags, point);
}

void CTestMinvexCoreView::MarkPoint(CDC* pDC,CPoint pt, int num,int x)
{

	pDC->SetTextColor(RGB(255,0,255));
	CString str;
	CBrush* hOldBrush = pDC->SelectObject(&m_pBrush);
	str.Format("%d",num);
	pDC->Ellipse(pt.x-2,pt.y-2,pt.x+2,pt.y+3);
	pDC->TextOut(pt.x+x,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;
	int j,k;
	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(j=i; j>1; j--)
		{			
			if(bufAngle > Angle[j-1])	
				break;

		}
		for (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::IsOnDown(CPoint ptB, CPoint ptC, CPoint ptF)
{
	double res;
	res = (ptC.x - ptB.x)*(ptF.y - ptB.y) - (ptC.y - ptB.y)*(ptF.x - ptB.x);
	if (res > 0)
		return true;
	return false;
}

void CTestMinvexCoreView::Makecvx(CPoint pt[], int ptN)
{
	LastPoint[LastPointNums] = MinPoint;
	int BackN,CentN,FrontN;
	int NUMS = ptN;
	CPoint BuffPt[50];
	int i;
	for ( i=0;i<NUMS; i++)
	{
		BuffPt[i] = pt[i];
	}
	BackN = 1;
	CentN = 2;
	FrontN = 3;
	while (FrontN < NUMS)
	{
		if (IsOnDown( BuffPt[BackN],BuffPt[CentN],BuffPt[FrontN]))
		{
			LastPointNums++;
			LastPoint[LastPointNums] = BuffPt[BackN];
			BackN++;
			CentN++;
			FrontN++;
		}else{
			for (i=CentN;i<NUMS;i++)
			{
				BuffPt[i] = BuffPt[i+1];
			}
			LastPointNums--;
			BackN--;
			CentN--;
			FrontN--;
			NUMS--;
		}
	}
	LastPointNums++;
	LastPoint[LastPointNums] = BuffPt[BackN];
	LastPointNums++;
	LastPoint[LastPointNums] = BuffPt[CentN];
}