Алгоритм Джарвиса / SOURCE / ChildView

// ChildView.cpp : implementation of the CChildView class
//

#include "stdafx.h"
#include "Jarvis.h"
#include "MainFrm.h"
#include "ChildView.h"
#include <math.h>

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

#define ID_PULSE 1
static	double	rndMax=(double)RAND_MAX;
static	double	deltaLen = 10.;
/////////////////////////////////////////////////////////////////////////////
// CChildView
//double 	Pi=3.141592654;
const	PointRad = 3;

CChildView::CChildView()
{
	MinPoint=-1;
	MaxPoint=-1;
	Animation=false;
	
	time_t t;
	t = time(&t);
	srand(t);
	Bluebr.CreateSolidBrush(0x00FF0000);
	Greenbr.CreateSolidBrush(0x0000FF00);
	Redbr.CreateSolidBrush(0x000000FF);
	Pi = acos(-1.);
	fileName.Empty();
	bitName.Empty();
	x = y = dx = dy = 1.;
//	bits = NULL;
}

CChildView::~CChildView()
{
}


BEGIN_MESSAGE_MAP(CChildView,CWnd )
	//{{AFX_MSG_MAP(CChildView)
	ON_WM_PAINT()
	ON_WM_LBUTTONDOWN()
	ON_WM_RBUTTONDOWN()
	ON_WM_SIZE()
	ON_WM_TIMER()
	ON_COMMAND(ID_EDIT_CLEAR_ALL, OnEditClearAll)
	ON_UPDATE_COMMAND_UI(ID_ANIMATE, OnUpdateAnimate)
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	ON_COMMAND(ID_FILE_SAVE, OnFileSave)
	ON_COMMAND(ID_FILE_SAVE_AS, OnFileSaveAs)
	ON_COMMAND(ID_FILE_SAVE_COPY_AS, OnFileSaveCopyAs)
	ON_COMMAND(ID_REFRESH, OnRefresh)
	ON_UPDATE_COMMAND_UI(ID_REFRESH, OnUpdateRefresh)
	ON_COMMAND(ID_NEWPOINTS,Generate)
	ON_COMMAND(ID_ANIMATE,Animate)
	ON_COMMAND(ID_CONVEX_HULL,Create_Convex_hull)
	ON_UPDATE_COMMAND_UI(ID_EDIT_CLEAR_ALL, OnUpdateAnimate)
	ON_UPDATE_COMMAND_UI(ID_CONVEX_HULL, OnUpdateAnimate)
	ON_UPDATE_COMMAND_UI(ID_FILE_SAVE, OnUpdateAnimate)
	ON_UPDATE_COMMAND_UI(ID_FILE_SAVE_AS, OnUpdateAnimate)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()


/////////////////////////////////////////////////////////////////////////////
// CChildView message handlers

BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs) 
{
	cs.cy=500;
	if (!CWnd::PreCreateWindow(cs))
		return FALSE;
	cs.cy=500;
	cs.dwExStyle |= WS_EX_CLIENTEDGE;
	cs.style &= ~WS_BORDER;
	cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS, 
		::LoadCursor(NULL, IDC_ARROW), HBRUSH(COLOR_WINDOW+1), ::LoadIcon(NULL,MAKEINTRESOURCE(IDR_MAINFRAME)));

	return TRUE;
}

void CChildView::OnPaint() 
{
	int i,dx1,dy1,dx2,dy2;
	CString	str;
	CPaintDC dc(this); // device context for painting

	LOGFONT LogFont;
	CFont   Font;
	CFont*  OldFont;
	LogFont.lfHeight=12;
	LogFont.lfWidth =0;
	LogFont.lfEscapement =0;
	LogFont.lfOrientation =0;
	LogFont.lfWeight =FW_NORMAL;
	LogFont.lfItalic =0;
	LogFont.lfUnderline =0;
	LogFont.lfStrikeOut =0;
	LogFont.lfCharSet =ANSI_CHARSET;
	LogFont.lfOutPrecision =OUT_DEFAULT_PRECIS;
	LogFont.lfClipPrecision =CLIP_DEFAULT_PRECIS;
	LogFont.lfQuality =PROOF_QUALITY;
	LogFont.lfPitchAndFamily =VARIABLE_PITCH|FF_ROMAN;
 	strcpy(LogFont.lfFaceName,"Times New Roman");

	Font.CreateFontIndirect (&LogFont);
	OldFont=dc.SelectObject(&Font); 

    CString strX;
	CString strY;
	CString strR;
	CString strCount;

	strX.Format("%i",(int)x);
	strY.Format("%i",(int)y);
	dc.TextOut(x*dx-20,0,strX); 
	dc.TextOut(0,y*dy-20,strY);
	
	if(bRounded)	{
		dx1 = x/2;
		dy1 = y/2;
		dx2 = (dx1+dRho)*dx;
		dy2 = (dy1+dRho)*dy;
		dx1 = (dx1-dRho)*dx;
		dy1 = (dy1-dRho)*dy;
		dc.Ellipse(dx1,dy1,dx2,dy2);
   	    
		strR.Format("Radius = %i",(int)dRho);
	    dc.TextOut((x/2+dRho)*dx+5,y/2*dy,strR); 
	}
	for(i=0;i<Points.size();i++) {
		// set point color
		if(i==MinPoint)
			dc.SelectObject(&Bluebr);
		else	if(i==MaxPoint)
			dc.SelectObject(&Redbr);
		else
			dc.SelectObject(&Greenbr);
		// show point
		dc.Ellipse(Points[i].x*dx-PointRad,Points[i].y*dy-PointRad,Points[i].x*dx+PointRad,Points[i].y*dy+PointRad);
	}
	if(Animation)
	{// step by step
		// multiplication
		CPen p2(PS_SOLID,1, (COLORREF) 0x00FFCCAA);
		dc.SelectObject(&p2);
		if(TimerValue>=0)	{
			for(i=0;i<Points.size();i++) {
				if(Convex_hull[TimerValue].p1.x==Points[i].x&&Convex_hull[TimerValue].p1.y==Points[i].y)
					continue;
				drawLineEx(dc,Convex_hull[TimerValue].p1,Points[i]);
			}
			// shape
			CPen p(PS_SOLID,1, (COLORREF) 0x00FF3333);
			dc.SelectObject(&p);
			for(i=0;i<TimerValue;i++) {
				dc.MoveTo(Convex_hull[i].p1.x*dx,Convex_hull[i].p1.y*dy);
				dc.LineTo(Convex_hull[i].p2.x*dx,Convex_hull[i].p2.y*dy);
			}
		}
	}
	else	
	{// shape at once
		CPen p(PS_SOLID,1, (COLORREF) 0x00FF3333);
			dc.SelectObject(&p);
		for(i=0;i<Convex_hull.size();i++) {
			dc.MoveTo(Convex_hull[i].p1.x*dx,Convex_hull[i].p1.y*dy);
			dc.LineTo(Convex_hull[i].p2.x*dx,Convex_hull[i].p2.y*dy);
		}
	    strCount.Format("%i",Convex_hull.size());
	    dc.TextOut(5,5,"h="+strCount); 
	}
	dc.SelectObject(OldFont);
}

void CChildView::Animate()
{
	if(bRounded) {
		bRounded=false;
	}

	if(!Animation)	{
		// prepare counter
		TimerValue=-1;
		// create
		Create_Convex_hull();
		// set animation mode
		Animation=true;
		Invalidate(TRUE);
	}
	else	{
		TimerValue ++;
		if(TimerValue>=Convex_hull.size())
			Animation = false;
		Invalidate(TRUE);
	}
	// set 1 second timer tick
}

CPoint CChildView::Norm(int Mx, int My, double sigmaX,double sigmaY)
{
	CPoint p;
	double N;
	double x,y;
	x=(double)rand()/((double)rndMax+1.0);
	y=(double)rand()/((double)rndMax+1.0);
	N=sqrt(-2.0*log(x))*cos(2.0*Pi*y);
	N*=sigmaX;
	p.x=Mx+N;

	x=(double) rand()/((double) rndMax+1.0);
	y=(double)rand()/((double)rndMax+1.0);
	N=sqrt(-2.0*log(x))*cos(2.0*Pi*y);
	N*=sigmaY;
	p.y=My+N;
	return p;
}

CPoint CChildView::Even(int Mx,int My, double sigmaX,double sigmaY)
{
	CPoint p;
	double N;
	N=(double) rand()*sigmaX/((double) rndMax+1.0);
	p.x=Mx-sigmaX+2*N;
	N=(double) rand()*sigmaY/((double) rndMax+1.0);
	p.y=My-sigmaY+2*N;
	return p;
}

void CChildView::Generate()
{
	int	x,y;

	x = this->x/2;
	y = this->y/2;
	CChildView::OnEditClearAll();
	m_Distribution.mx = x;
	m_Distribution.my = y;
	if(m_Distribution.DoModal()!=IDOK)
		return;

	bRounded = false;
	if(m_Distribution.m_Item==2)	{
		bRounded = true;
		dRho = m_Distribution.m_Rho;
	}
	int sigma=m_Distribution.m_Sigma;
	for(int i=0; i<m_Distribution.m_Num;i++)	{
		switch(m_Distribution.m_Item)	{
		case 0:
			Points.push_back(Even(x,y,m_Distribution.m_Rect,m_Distribution.m_Rect));;
			break;
		case 1:
			Points.push_back(Norm(x,y,sigma,sigma));
			break;
		case 2:
			Points.push_back(Rounded(dRho));
			break;
		}
			
	}
	
	OnRefresh();
}

void CChildView::OnRButtonDown(UINT nFlags, CPoint point) 
{
	Create_Convex_hull();
	CWnd::OnRButtonDown(nFlags, point);
}

//////////////////////////////////////////////////////////////////////

void CChildView::Create_Convex_hull()
{
	CLine	line;
	// index of first point
	int iTempPoint1;
	// index of second point
	int iTempPoint2;
	// temporary variables
	int i,n1,n2;

	if(bRounded) {
		bRounded=false;
		Invalidate(TRUE);
	}

	if(Animation)	{
		// stop animation
		Animation = false;
		// redraw window
		Invalidate(TRUE);
	}
	// clear shape
	Convex_hull.clear();

	if(Points.size()>2)
	{
		// clear max and min
		MaxPoint=0;
		MinPoint=0;
		// looking for max(y) and min(y)
		for(i=1;i<Points.size();i++) {
			// minimum
			if(Points[MinPoint].y<Points[i].y) 
				MinPoint=i;
			else	if(Points[MinPoint].y==Points[i].y)
			{
				if(Points[MinPoint].x>Points[i].x)
					MinPoint=i;
			}
			// maximum
			if(Points[MaxPoint].y>Points[i].y) 
				MaxPoint=i;
			else	if(Points[MaxPoint].y==Points[i].y)
			{
				if(Points[MaxPoint].x<Points[i].x)
					MaxPoint=i;
			}
		}

		// from minimun to maximum
		iTempPoint1=MinPoint;
		
		while(iTempPoint1!=MaxPoint) {
			// init point 2
			if(iTempPoint1>0) 
				iTempPoint2=0;
			else
				iTempPoint2=1;
			// look for second point
			for(i=0;i<Points.size();i++) {
				if(i!=iTempPoint1) {
					n1 = (Points[iTempPoint2].x-Points[iTempPoint1].x)*(Points[i].y-Points[iTempPoint1].y);
					n2 = (Points[i].x-Points[iTempPoint1].x)*(Points[iTempPoint2].y-Points[iTempPoint1].y);
					if(n1>n2)
						iTempPoint2=i;
				}

			}
			// set line from 1 to 2
			line.p1=Points[iTempPoint1];
			line.p2=Points[iTempPoint2];
			// put it in storage
			Convex_hull.push_back(line);
			// set p1 to p2
			iTempPoint1=iTempPoint2;
		}
		
		// from maximum to minimun
		while(iTempPoint1!=MinPoint) {
			// init point 2
			if(iTempPoint1>0) 
				iTempPoint2=0;
			else
				iTempPoint2=1;
			//  look for second point
			for(i=0;i<Points.size();i++) {
				if(i!=iTempPoint1) {
					n1 = (Points[iTempPoint2].x-Points[iTempPoint1].x)*(Points[i].y-Points[iTempPoint1].y);
					n2 = (Points[i].x-Points[iTempPoint1].x)*(Points[iTempPoint2].y-Points[iTempPoint1].y);
					if(n1>n2)
						iTempPoint2=i;
				}

			}
			// set line from 1 to 2
			line.p1=Points[iTempPoint1];
			line.p2=Points[iTempPoint2];
			// put it in storage
			Convex_hull.push_back(line);
			// set p1 to p2
			iTempPoint1=iTempPoint2;
		}
		// refresh window
		Invalidate(FALSE);
	}
}

void CChildView::OnTimer(UINT nIDEvent)
{
	TimerValue++;
	if(TimerValue==Convex_hull.size()) {
		KillTimer(ID_PULSE);
		Animation=false;
	}
	Invalidate(TRUE);
	

	CWnd::OnTimer(nIDEvent);
}

void CChildView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	if(Animation)
		return ;
	CPoint p;
	p.x=point.x/dx;
	p.y=point.y/dy;
	Points.push_back(p);
	MinPoint=-1;
	MaxPoint=-1;
	
	if(Convex_hull.size()>0) {
		Convex_hull.clear();
		Invalidate(TRUE);
	}
	else 
		Invalidate(FALSE);
	if(bRounded) {
		Invalidate(TRUE);
		bRounded=false;
	}
	
	CWnd::OnLButtonDown(nFlags, point);

}


void CChildView::OnSize( UINT nType, int cx, int cy )
{
	static bool bFirst=true;
	CString	str;

	if(!bFirst&&ClientX&&ClientY)	{
		dx = (double)cx / (double)x;
		dy = (double)cy / (double)y;
		str.Format("%dx%d",cx,cy);
		((CMainFrame*)GetParent())->showStatus(str);
	}
	else	{
        x = 1000;
	    y = 1000;
		bFirst = false;
	}
	ClientX=1000;
	ClientY=1000;
}


void CChildView::OnEditClearAll() 
{
	if(Animation)
		return;
	fileName.Empty();
	MinPoint=-1;
	MaxPoint=-1;
	Points.clear();
	Convex_hull.clear();
	bRounded=false;
	Invalidate(TRUE);	
}

void CChildView::OnUpdateAnimate(CCmdUI* pCmdUI) 
{
	if(Points.size()<3)
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);	
}

double CChildView::drand()
{
	return (double)rand()/rndMax;
}

double CChildView::drand0()
{
	return (double)rand()/rndMax*2.-1.;
}

double CChildView::gaussian(double sigma, double mu)
{
	static	double	r,v1,v2;
	do
	{
		v1 = drand0();
		v2 = drand0();
		r = v1*v1+v2*v2;
	}while(r>=1.||r<=0.);
	return	(v1*sqrt(-2.*log(r)/r)*sigma+mu);
}

CPoint CChildView::Rounded(double rho)
{
	CPoint	p;
	bool ok=false; 
	double x1;
	double y1;

	while (!ok) {
	x1 = rho-2*rho * drand();
    y1 = rho-2*rho * drand();
	ok = (sqrt(x1*x1+y1*y1)<=rho);
	if (ok) {
	 p.x = x1 + x/2;
	 p.y = y1 + y/2;
	}

	}

	return p;
}

void CChildView::Serialize(CArchive& ar) 
{
	CString	sIO,sIn;
	bool	bData;
	int	cnt,offt,i;
	TCHAR	chr;
	CPoint	pnt;

	try	{
		if (ar.IsStoring())
		{	// storing code
			sIO.LoadString(IDR_MAINFRAME);
			ar.WriteString(sIO);
			ar << '\r' << '\n';
			sIO.LoadString(IDS_LEADIN);
			ar.WriteString(sIO);
			ar << '\r' << '\n';
			for(i=0;i<Points.size();i++)
			{
				sIO.Format(IDS_FMT,Points[i].x,Points[i].y);
				ar.WriteString(sIO);
				ar << '\r' << '\n';
			}
		}
		else
		{	// loading code
			ar.ReadString(sIn);
			sIO.LoadString(IDR_MAINFRAME);
			if(sIO.Compare(sIn)==0)
			{
				bData = false;
				sIO.LoadString(IDS_LEADIN);
				while(!bData)
				{
					if(!ar.ReadString(sIn))
						break;
					if(sIO.Compare(sIn)==0)
						bData = true;
				}
				while(ar.ReadString(sIn))
				{
					if(sIn.IsEmpty())
						break;
					cnt = 0;
					do
					{
						chr = sIn.GetAt(cnt+2);
						cnt ++;
					} while(chr!=' '&&chr!='\t'&&cnt+2<sIn.GetLength());
					if(cnt+2>sIn.GetLength())
						continue;
					sIO = sIn.Mid(2,cnt-1);
					pnt.x = atoi((LPCTSTR)sIO);
					offt = cnt + 2;
					cnt = 0;
					do
					{
						chr = sIn.GetAt(cnt+offt);
						cnt ++;
					} while(chr!='='&&cnt+offt<sIn.GetLength());
					if(cnt+offt>sIn.GetLength())
						continue;
					offt += cnt;
					cnt = sIn.GetLength() - offt;
					sIO = sIn.Mid(offt,cnt);
					pnt.y = atoi((LPCTSTR)sIO);
					Points.push_back(pnt);
				}
				Invalidate(FALSE);
			}
			else	{
				sIO.LoadString(IDS_BADFMT);
				MessageBox(sIO,"Чтение файла",MB_OK);
			}
		}
	}	catch(CFileException fe)	{
		MessageBox("FileException");
		fe.Delete();
	}	catch(CArchiveException ae)	{
		MessageBox("ArchiveException");
		ae.Delete();
	}	catch(CMemoryException me)	{
		MessageBox("MemoryException");
		me.Delete();
	}
}

void CChildView::OnFileOpen() 
{
	CFileDialog	fd(TRUE,"txt",fileName,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,"Текстовые файлы|*.txt\0Все файлы|*.*\0\0",this);
	
	if(fd.DoModal()!=IDCANCEL)
	{
		OnEditClearAll();
		fileName = fd.GetPathName();
		CFile	f(fileName,0);
		CArchive ar(&f,1,4096,NULL);
		Serialize(ar);
	}
}

void CChildView::OnFileSave() 
{
	if(fileName.IsEmpty())
	{
		OnFileSaveAs();
	}
	else
	{
		CFile	f(fileName,1|0x1000|0x2000);
		CArchive ar(&f,0,4096,NULL);
		Serialize(ar);
	}
}

void CChildView::OnFileSaveAs() 
{
	CFileDialog	fd(FALSE,"txt",fileName,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,"Текстовые файлы|*.txt\0Все файлы|*.*\0\0",this);

	if(fd.DoModal()!=IDCANCEL)
	{
		fileName = fd.GetPathName();
		CFile	f(fileName,1|0x1000|0x2000);
		CArchive ar(&f,0,4096,NULL);
		Serialize(ar);
	}
}

void CChildView::OnFileSaveCopyAs() 
{
	BOOL WriteWindowToDIB( LPCTSTR szFile, CRect	rect, CWnd *pWnd);
	CRect	r;

	CFileDialog	fd(FALSE,"bmp",bitName,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,"Windows bitmap|*.bmp\0Все файлы|*.*\0\0",this);

	if(fd.DoModal()!=IDCANCEL)
	{
		bitName = fd.GetPathName();
		this->GetClientRect(r);
		WriteWindowToDIB((LPCTSTR)bitName,r,this);
	}
}

void CChildView::drawLineEx(CDC &dc, CPoint p1, CPoint p2)
{
	int	dx1,dy1;

	//////////////////////////////////////////////////
	// move p1 from p2 for 10 points by ordinate axis
	//////////////////////////////////////////////////
	dx1 = p2.x - p1.x;
	dy1 = p2.y - p1.y;
	//////////////////////////////////////////////////
	// leave original point unchanged
	//////////////////////////////////////////////////
	p2.x += deltaLen*(double)dx1/sqrt(dx1*dx1+dy1*dy1);
	p2.y += deltaLen*(double)dy1/sqrt(dx1*dx1+dy1*dy1);
	//////////////////////////////////////////////////
	// just draw it
	//////////////////////////////////////////////////
	dc.MoveTo(p1.x*dx,p1.y*dy);
	dc.LineTo(p2.x*dx,p2.y*dy);
}


void CChildView::OnRefresh() 
{
 Convex_hull.clear();
 Animation = false;
 MaxPoint=-1;
 MinPoint=-1;
 Invalidate(TRUE);
}


void CChildView::OnUpdateRefresh(CCmdUI* pCmdUI) 
{
	if(Points.size()<3)
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);	
}