convexview.cpp

凸包算法 vc 6.0 实现用户输入点凸包

// ConvexView.cpp : implementation of the CConvexView class
//

#include "stdafx.h"
#include "Convex.h"

#include "ConvexDoc.h"
#include "ConvexView.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CConvexView

IMPLEMENT_DYNCREATE(CConvexView, CView)

BEGIN_MESSAGE_MAP(CConvexView, CView)
	//{{AFX_MSG_MAP(CConvexView)
	ON_WM_LBUTTONDOWN()
	ON_WM_LBUTTONUP()
	ON_COMMAND(IDC_Convex, OnConvex)
	//}}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()



int CConvexView::flag = 0;
/////////////////////////////////////////////////////////////////////////////
// CConvexView construction/destruction

CConvexView::CConvexView()
{
	// TODO: add construction code here
	m_stackTop = 0; 
//	flag = 0;
  
}

CConvexView::~CConvexView()
{
}

BOOL CConvexView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs
    
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CConvexView drawing

void CConvexView::OnDraw(CDC* pDC)
{
	CConvexDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	CPen pen(PS_SOLID, 1, RGB(255,0,0));
	CBrush brush(RGB(255,0,0));
//	CBrush * pOldBrush;
    CPen * pOldPen;
	pOldPen = pDC->SelectObject(&pen);//总结一下  颜色 边界有无，填充
	pDC->SelectObject(&brush);    //
    
	if(flag == 0 )
	{
 	    for (int i = 0; i < m_vPoints.size(); ++i)
		{   
	    	pDC->Ellipse(m_vPoints[i].x-5, m_vPoints[i].y-5, m_vPoints[i].x+5, m_vPoints[i].y+5);//小心坐标
		}
	 
	}
    //pDC->SelectObject(pOldBrush);  有点问题
	else  
	{
        int i;
		for (  i = 0; i < m_vPoints.size(); ++i)
		{   
			pDC->Ellipse(m_vPoints[i].x-5, m_vPoints[i].y-5, m_vPoints[i].x+5, m_vPoints[i].y+5);//小心坐标
		}

		for ( i = 0; i < m_ptStack.size()-1; ++i)
		{   
		//	pDC->Ellipse(m_ptStack[i].x, m_ptStack[i].y, m_ptStack[i].x+10, m_ptStack[i].y+10);//小心坐标
			pDC->MoveTo(m_ptStack[i]);
			pDC->LineTo(m_ptStack[i+1]);	
		}
		pDC->MoveTo(m_ptStack[ m_ptStack.size()-1]);
		pDC->LineTo(m_ptStack[0]);
	}
	pDC->SelectObject(pOldPen);
}

/////////////////////////////////////////////////////////////////////////////
// CConvexView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CConvexView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CConvexView message handlers

void CConvexView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
//	CClientDC dc(this);
//	CPen pen(PS_SOLID, 1, RGB(255,0,0));
//  CPen *pOldPen = dc.SelectObject(*pen);
//	CBrush brush(RGB(255,0,0));
//	m_ptOrigin = point;	
	//dc.Ellipse()
	m_vPoints.push_back(point);
	Invalidate();
	CView::OnLButtonDown(nFlags, point);
}

void CConvexView::OnLButtonUp(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	// CClientDC dc(this);

	//CBrush brush(RGB(255, 0, 0));
    //CRect rect(m_ptOrigin, point);

	CView::OnLButtonUp(nFlags, point);
}

 
void CConvexView::OnConvex() 
{
	// TODO: Add your command handler code here
    //select minimum y_coordinate
	CPoint p0;
	int minY =  m_vPoints[0].y;
	int minYSub = 0;
	int iPt;
	vector<float> vPtCos;

	flag = 1;

	for ( iPt = 0;  iPt < m_vPoints.size(); ++iPt)  //忽略重复点和最低点有多个的情况
	{
		if ( m_vPoints[iPt].y < minY)
		{
			minY = m_vPoints[iPt].y;
		//	p0 = m_vPoints[iPt];
			minYSub = iPt;
		}
	}
	p0 = m_vPoints[minYSub];   //p0 record the point that has minimum y_coordinate
    //m_vPoints[minYSub] = NULL;          //minYSub record the sub of  p0, and this line makes 

    //sort points except p0 according to polar angle 
	//用夹角的余弦计算，因为余弦函数在(0~PI)是单调的；
	//计算余弦
     for ( iPt = 0;  iPt < m_vPoints.size(); ++iPt) 
     {
		 if ( m_vPoints[iPt] != p0)
		 {
            float xDist = m_vPoints[iPt].x - p0.x;
			float dist = sqrt((m_vPoints[iPt].x - p0.x) * (m_vPoints[iPt].x - p0.x) + 
				(m_vPoints[iPt].y - p0.y) * (m_vPoints[iPt].y - p0.y));
			vPtCos.push_back( xDist / dist);
		 }
		 else
           vPtCos.push_back(1);//自己跟自己的夹角为0
	 }
     //排序，按余弦从大到小，就是按夹角从小到大，冒泡
	 int j;
	 for ( iPt = 0; iPt < vPtCos.size() - 1; ++iPt )
	 {
		 for ( j = 0; j < vPtCos.size() - iPt; ++j )
		 {
			 if ( vPtCos[j] < vPtCos[j+1])
			 {
				 float t = vPtCos[j+1];
				 vPtCos[j+1] = vPtCos[j];
				 vPtCos[j] = t;

				 CPoint tPt = m_vPoints[j+1];
				 m_vPoints[j+1] = m_vPoints[j];
				 m_vPoints[j] = tPt;
			 }
		 }
	 }

	 m_ptStack.push_back(p0);
	 m_ptStack.push_back(m_vPoints[1]);
	 m_ptStack.push_back(m_vPoints[2]);
	 m_stackTop = 2;

  
	 for ( iPt = 3; iPt < m_vPoints.size(); ++iPt)
	 {
		 while(m_ptStack.size() != 0 && ToLeft(m_ptStack[m_ptStack.size()-2], m_ptStack[m_ptStack.size()-1], m_vPoints[iPt]) < 0 )
		 {
            m_ptStack.pop_back();
		 }
		 m_ptStack.push_back(m_vPoints[iPt]);
	 } 

     Invalidate();
	
}

int CConvexView::ToLeft(CPoint pt1, CPoint pt2, CPoint pt3)
{
    return ( pt1.x * pt2.y + pt1.y * pt3.x + pt2.x * pt3.y ) - ( pt3.x * pt2.y + pt1.x * pt3.y + pt1.y * pt2.x);

}