mychview.cpp

平面凸包

// MyCHView.cpp : implementation of the CMyCHView class
//

#include "stdafx.h"
#include "MyCH.h"

#include "MyCHDoc.h"
#include "MyCHView.h"
#include "InitialSet.h"

#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define  inf  1<<18
#define  NODE_STYLE_CYCLE  0  // 圆形点
#define  NODE_STYLE_CROSS  1  // 十字形点

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

/////////////////////////////////////////////////////////////////////////////
// CMyCHView

IMPLEMENT_DYNCREATE(CMyCHView, CView)

BEGIN_MESSAGE_MAP(CMyCHView, CView)
	//{{AFX_MSG_MAP(CMyCHView)
	ON_COMMAND(IDD_INI_DATA, OnIniData)
	ON_COMMAND(IDD_CONVEXHULL, OnConvexhull)
	ON_UPDATE_COMMAND_UI(IDD_CONVEXHULL, OnUpdateConvexhull)
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CMyCHView construction/destruction

CMyCHView::CMyCHView()
{
	// TODO: add construction code here
	IsInitialed = FALSE;
	IsComputed  = FALSE;
	m_pNode     = NULL;
	m_pResult   = NULL;
}

CMyCHView::~CMyCHView()
{
	if(m_pNode != NULL && m_pResult != NULL)
	{
        delete  []m_pNode;
		delete  []m_pResult;
        m_pNode    = NULL;
		m_pResult  = NULL;
	}
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMyCHView drawing

void CMyCHView::OnDraw(CDC* pDC)
{
	CMyCHDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	if(IsInitialed == TRUE)
	{
		for(int i=0; i<m_nCount; i++)
		{
			if(m_nodeStyle == NODE_STYLE_CYCLE)
			{
			  CPoint topLeft(m_pNode[i].x - m_r, m_pNode[i].y - m_r);
			  CPoint bottomRight(m_pNode[i].x + m_r, m_pNode[i].y + m_r);
			  pDC->Ellipse(CRect(topLeft, bottomRight));
			 
			}
			else if(m_nodeStyle == NODE_STYLE_CROSS)
			{
			  CPoint  Top(m_pNode[i].x, m_pNode[i].y - m_r);
              CPoint  Left(m_pNode[i].x - m_r, m_pNode[i].y);
			  CPoint  Bottom(m_pNode[i].x, m_pNode[i].y + m_r);
              CPoint  Right(m_pNode[i].x + m_r, m_pNode[i].y);
			  pDC->MoveTo(Top);
			  pDC->LineTo(Bottom);
			  pDC->MoveTo(Left);
			  pDC->LineTo(Right);
			}
		}
		if(IsComputed == TRUE)  // 画凸包轮廓
		{
			pDC->MoveTo(m_pResult[0]);
			for(i=1; i<=m_h; i++)
			   pDC->LineTo(m_pResult[i]);
		}
	}
}

/////////////////////////////////////////////////////////////////////////////
// CMyCHView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CMyCHView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CMyCHView message handlers

void CMyCHView::OnIniData() //设置初始化数据
{
	// TODO: Add your command handler code here

	CInitialSet  IniSetDlg;
	if(IDOK == IniSetDlg.DoModal())
	{
		if(m_pNode != NULL ) 
		{
            delete  []m_pNode;
			m_pNode = NULL;
		}	
		if(m_pResult != NULL)
		{
            delete  []m_pResult;
			m_pResult = NULL;
		}

		m_nCount      = IniSetDlg.m_NodeNum;
		m_r           = IniSetDlg.m_NodeSize;
		m_nodeStyle   = IniSetDlg.m_NodeStyleIndex;
		m_topLeft.x   = IniSetDlg.m_TopleftX;
		m_topLeft.y   = IniSetDlg.m_TopleftY;
		m_sScreen.cx  = IniSetDlg.m_SrcWidth;
		m_sScreen.cy  = IniSetDlg.m_SrcHeigth;
		m_h           = 0;
		m_pNode       = new CPoint[m_nCount];
		m_pResult     = new CPoint[m_nCount]; 
	
		srand(time(NULL));
		for(int i=0; i<m_nCount; i++)
		{
			m_pNode[i].x = m_topLeft.x + rand()%m_sScreen.cx;
			m_pNode[i].y = m_topLeft.y + rand()%m_sScreen.cy;
		}
		Invalidate();
		IsInitialed   = TRUE;
		IsComputed    = FALSE; 
	}
}

/*
int cmp(const void *a,const void *b)
{
	CPoint *p, *q;
	p = (CPoint*)a;
	q = (CPoint*)b;
	if(p->x != q->x)
	   return p->x - q->x;
	else
		return p->y - q->y;
}
*/

void CMyCHView::ConvexHull() // 计算凸包
{
 
//	qsort(m_pNode, m_nCount, sizeof(CPoint), cmp); //按X坐标升序，并且Y坐标升序排序

	long  *tPoint = new long[m_topLeft.x + m_sScreen.cx];  // 对每个X坐标，Y坐标最大的点
	long  *bPoint = new long[m_topLeft.x + m_sScreen.cx];  // 对每个X坐标，Y坐标最小的点
	int h = 0;                 // 凸包顶点数
    long  minX = inf, maxX = -1;
	int i;
    for(i=0; i< m_topLeft.x + m_sScreen.cx; i++)
	{
        tPoint[i] = -1;
		bPoint[i] = inf;
	}
  //计算tPoint，bPoint数组
    for(i=0; i<m_nCount; i++)
	{
        if(m_pNode[i].y > tPoint[m_pNode[i].x])
			tPoint[m_pNode[i].x] = m_pNode[i].y;
		if(m_pNode[i].y < bPoint[m_pNode[i].x])
		    bPoint[m_pNode[i].x] = m_pNode[i].y;
        if(m_pNode[i].x < minX)
			minX = m_pNode[i].x;
		if(m_pNode[i].x > maxX)
			maxX = m_pNode[i].x;
	}

	double  k;          //斜率
	double  maxk;       // 最大斜率
	CPoint  bestPoint;  // 凸包的下一顶点
	int     index;  // 凸包当前顶点对应的tPoint，bPoint数组的下标

  // 上半段
	if(tPoint[minX] == bPoint[minX])
	   m_pResult[h] = CPoint(minX, bPoint[minX]);
	else
	{
       m_pResult[h]   = CPoint(minX, bPoint[minX]);
	   m_pResult[++h] = CPoint(minX, tPoint[minX]);
	}
	index = minX;
	while(m_pResult[h] != CPoint(maxX, tPoint[maxX]))
	{
        maxk = -inf;		
		for(i=index+1; i<=maxX; i++)
		{
			if(tPoint[i] > -1)
			{
			    k = double(tPoint[i] - m_pResult[h].y)/double(i - m_pResult[h].x);
				if(k >= maxk)
				{
					maxk = k;
					bestPoint = CPoint(i, tPoint[i]);
					index = i;
				}
			}
		}
		m_pResult[++h] = bestPoint;
	}

  // 下半段
    if(tPoint[maxX] != bPoint[maxX])
	   m_pResult[++h] = CPoint(maxX, bPoint[maxX]);
	index = maxX;
	while(m_pResult[h] != CPoint(minX, bPoint[minX]))
	{
        maxk = -inf;
		for(i=index-1; i>=minX; i--)
		{
			if(bPoint[i] < inf)
			{
				k = double(bPoint[i] - m_pResult[h].y)/double(i - m_pResult[h].x);
				if(k > maxk)
				{
					maxk = k;
					bestPoint = CPoint(i, bPoint[i]);
					index = i;
				}
			}

		}
		m_pResult[++h] = bestPoint;
	}
	m_h = h;
	delete []tPoint;
	delete []bPoint;
}

void CMyCHView::OnConvexhull() 
{
	// TODO: Add your command handler code here
	clock_t  start, finish; //计时
	start  = clock();	  
	ConvexHull();
    finish = clock();
	IsComputed = TRUE; 
    Invalidate();
	CString  totalTime;
	totalTime.Format("总计用时：%.0lf ms", (double)(finish-start)*1000.0/CLOCKS_PER_SEC);
	MessageBox(totalTime);		
}

void CMyCHView::OnUpdateConvexhull(CCmdUI* pCmdUI) 
{
	// TODO: Add your command update UI handler code here
	pCmdUI->Enable(IsInitialed);
}