quickhullview.cpp

快速凸包演示程序 演示了快速凸包算法的执行过程

// QuickHullView.cpp : implementation of the CQuickHullView class
//

#include "stdafx.h"
#include "QuickHull.h"

#include "QuickHullDoc.h"
#include "QuickHullView.h"
#include <vector>
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView

IMPLEMENT_DYNCREATE(CQuickHullView, CView)

BEGIN_MESSAGE_MAP(CQuickHullView, CView)
	//{{AFX_MSG_MAP(CQuickHullView)
	ON_WM_LBUTTONDOWN()
	ON_COMMAND(ID_GENEQUICKHULL, OnGenequickhull)
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView construction/destruction

CQuickHullView::CQuickHullView() : leftthenlowest(10000, 10000), rightthenhighest(-1, -1),
 lastpoint(0, 0), flag(false)
{
	// TODO: add construction code here
	hBrush = CreateSolidBrush(RGB(255, 0, 0));
	hPen = CreatePen(PS_DOT, 1, RGB(0, 255, 0));
}

CQuickHullView::~CQuickHullView()
{
	DeleteObject(hBrush);
	DeleteObject(hPen);
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView drawing

void CQuickHullView::OnDraw(CDC* pDC)
{
	CQuickHullDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	const int d = 3;
	int i;
	//HANDLE hBrush = CreateSolidBrush(RGB(255, 0, 0));
	pDC->SelectObject(hBrush);
	//SelectObject(pDC->GetSafeHdc(), NULL_PEN);
	pDC->SelectObject(GetStockObject(NULL_PEN));
	for (i = 0; i < pts.size(); ++i)
	{
		/*pDC->Ellipse((int)pts[i].x - d, (int)pts[i].y - d, 
			(int)pts[i].x + d, (int)pts[i].y + d);*/
		pts[i].Draw(pDC);
	}
	pDC->SelectObject(GetStockObject(BLACK_PEN));
	pDC->SelectObject(GetStockObject(WHITE_BRUSH));
	if (!phull.empty())
	{
		//pDC->MoveTo((int)leftthenlowest.x, (int)leftthenlowest.y);
		pDC->MoveTo((int)pts[phull[0]].x, (int)pts[phull[0]].y);
		for (i = 1; i < phull.size(); ++i)
		{
			pDC->LineTo((int)pts[phull[i]].x, (int)pts[phull[i]].y);
		}
		pDC->LineTo((int)pts[phull[0]].x, (int)pts[phull[0]].y);
		//pDC->LineTo((int)rightthenhighest.x, (int)rightthenhighest.y);
	}
}

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CQuickHullView message handlers

void CQuickHullView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	const int d = 2;
	if (lastpoint != point && !flag)
	{
		MyPoint pt(point.x, point.y);
		pts.push_back(pt);
		CRect rect(point.x - d, point.y - d, point.x + d, point.y + d);
		InvalidateRect(&rect, TRUE);
	}
	CView::OnLButtonDown(nFlags, point);
}

void CQuickHullView::OnGenequickhull() 
{
	// TODO: Add your command handler code here
	if (pts.size() < 3)
	{
		MessageBox("point number should not be less than 3!");
		return;
	}
	if (flag)
	{
		return;
	}
	int i;
	const int MAX = 10000;
	int idleft = -1, idright = -1;
	CClientDC DC((CWnd*)this);
	//MyPoint leftthenlowest(MAX, MAX);
	//MyPoint rightthenhighest(-1, -1);
	for (i = 0; i < pts.size(); ++i)
	{
		pts[i].blink(&DC);
		if (pts[i].x < leftthenlowest.x || 
			(pts[i].x == leftthenlowest.x && pts[i].y < leftthenlowest.y))
		{
			idleft = i;
			leftthenlowest = pts[i];
		}
		if (pts[i].x > rightthenhighest.x || 
			(pts[i].x == rightthenhighest.x && pts[i].y > rightthenhighest.y))
		{
			idright = i;
			rightthenhighest = pts[i];
		}
	}

	pts[idleft].setcolor(RGB(255, 0, 255));
	pts[idright].setcolor(RGB(255, 0, 255));
	pts[idleft].blink(&DC);
	pts[idleft].blink(&DC);
	pts[idleft].blink(&DC);
	pts[idright].blink(&DC);
	pts[idright].blink(&DC);
	pts[idright].blink(&DC);
	DC.SelectObject(hPen);
	DC.MoveTo((int)leftthenlowest.x, (int)leftthenlowest.y);
	DC.LineTo((int)rightthenhighest.x, (int)rightthenhighest.y);

	vector<int> upPts;
	vector<int> downPts;
	
	for (i = 0; i < pts.size(); ++i)
	{
		if (i == idleft || i == idright)
		{
			continue;
		}
		if (ToLeft(leftthenlowest, rightthenhighest, pts[i]))
		{
			upPts.push_back(i);
		}
		else if ( ToLeft(rightthenhighest, leftthenlowest, pts[i]))
		{
			downPts.push_back(i);
		}
	}

	vector<int> phullup = QuickHull(leftthenlowest, rightthenhighest, upPts);
	vector<int> phulldown = QuickHull(rightthenhighest, leftthenlowest, downPts);

	phull.push_back(idleft);
	for (i = 0; i < phullup.size(); ++i)
	{
		phull.push_back(phullup[i]);
	}
	phull.push_back(idright);
	for (i = 0; i < phulldown.size(); ++i)
	{
		phull.push_back(phulldown[i]);
	}

	Invalidate(TRUE);
	flag = true;	
}
vector<int> CQuickHullView::QuickHull
	(const MyPoint& a, const MyPoint& b, vector<int>& S, bool up)
{
	CClientDC DC((CWnd*)this);
	DC.SelectObject(hPen);
// 	DC.MoveTo((int)a.x, (int)a.y);
// 	DC.LineTo((int)b.x, (int)b.y);
// 	DC.SelectObject(GetStockObject(BLACK_PEN));
	if (S.empty())
	{
		return S;
	}
	int id = FindFurthest(a, b, S);
	MyPoint& c = pts[id];
	c.setcolor(RGB(255, 0, 255));
	c.blink(&DC);
	c.blink(&DC);
	c.blink(&DC);
 	DC.MoveTo((int)a.x, (int)a.y);
	DC.LineTo((int)c.x, (int)c.y);
 	DC.LineTo((int)b.x, (int)b.y);
	Sleep(500);
	vector<int> A, B;
	vector<int>::iterator it;
	for (it = S.begin(); it != S.end(); ++it)
	{
		if (*it == id)//point c 不属于任何集合
		{
			continue;
		}
		MyPoint& temp = pts[*it];
		if (ToLeft(a, c, temp))
		{
			A.push_back(*it);
			
		}
		else if (ToLeft(c, b, temp))
		{
			B.push_back(*it);
			
		}
		else
		{
			temp.setcolor(RGB(0, 255, 255));
			temp.blink(&DC);
		}

	}
	vector<int> L, R;
	L = QuickHull(a, c, A);
	R = QuickHull(c, b, B);
	vector<int> result;
	int i;
	for (i = 0; i < L.size(); ++i)
	{
		result.push_back(L[i]);
	}
	result.push_back(id);
	for (i = 0; i < R.size(); ++i)
	{
		result.push_back(R[i]);
	}
// 	DC.MoveTo((int)a.x, (int)a.y);
// 	DC.LineTo((int)b.x, (int)b.y);
	return result;
}

int CQuickHullView::FindFurthest(const MyPoint& a, const MyPoint& b,
								 vector<int>& S, bool up /* = true */) const
{
	int id;
	double dis = 0;
	vector<int>::iterator it;
	CClientDC DC((CWnd*)this);
	for (it = S.begin(); it != S.end(); ++it)
	{
		const MyPoint& pt = pts[*it];
		//pt.blink(&DC);
		if (distanc(a, b, pt) > dis)
		{
			id = *it;
			dis = distanc(a, b, pt);
		}
	}
	return id;
}