delaunayview.cpp

经典模拟退火算法,希望能对大家有所帮助

// DelaunayView.cpp : implementation of the CDelaunayView class
//

#include "stdafx.h"
#include "Delaunay.h"

#include "DelaunayDoc.h"
#include "DelaunayView.h"

#include <strstrea.h>
#include "dataStruct.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView

IMPLEMENT_DYNCREATE(CDelaunayView, CView)

BEGIN_MESSAGE_MAP(CDelaunayView, CView)
	//{{AFX_MSG_MAP(CDelaunayView)
	ON_WM_LBUTTONDOWN()
	ON_COMMAND(ID_DELAUNAY, OnDelaunay)
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView construction/destruction

CDelaunayView::CDelaunayView()
{
	// TODO: add construction code here
    startPoint.x = 0;
	startPoint.y = 0;
	pointNumber = 0;
	Tricount = nCurTri = 0;
}

CDelaunayView::~CDelaunayView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView drawing

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

	POSITION pos1;
	TriAngle* pTri;
	PointCls *p4, *p5, *p6;	

	if(pDoc->PointList->GetCount())
	{
		pos1 = pDoc->PointList->GetHeadPosition();
		while(pos1 != NULL)
		{
			PointCls* pa = (PointCls*)pDoc->PointList->GetNext(pos1);

			pDC->SetPixel(pa->x, pa->y, RGB(255, 0, 0));
		}

//		createFirstTri(pDoc->PointList,
//			           pDoc->TriList);
//
//		POSITION pos4, pos5;
//		pos4 = pDoc->TriList->GetHeadPosition();
//		TriAngle* pTriSeed = (TriAngle*)pDoc->TriList->GetAt(pos4);
//
//		pos5 = pDoc->PointList->GetHeadPosition();
//		while(pos5 != NULL)
//		{
//			PointCls* pa = (PointCls*)pDoc->PointList->GetNext(pos5);
//
//			if(pa->index == pTriSeed->index[0])
//			{
//				p1 = pa;
//			}
//			if(pa->index == pTriSeed->index[1])
//			{
//				p2 = pa;
//			}
//			if(pa->index == pTriSeed->index[2])
//			{
//				p3 = pa;
//			}
//		}
//		enlargeEdge(p1, p2, p3, pDoc->PointList, pDoc->TriList);
//
//		enlargeTri(pDoc->PointList, pDoc->TriList);
//
//		continueEnlarge(pDoc->PointList, pDoc->TriList);
	}
	if(pDoc->TriList->GetCount())
	{
		POSITION pos8 = pDoc->TriList->GetHeadPosition();
		while(pos8 != NULL)
		{
			pTri = (TriAngle*)pDoc->TriList->GetNext(pos8);			

			POSITION pos9 = pDoc->PointList->GetHeadPosition();
			while(pos9 != NULL)
			{
				PointCls* pa = (PointCls*)pDoc->PointList->GetNext(pos9);

				if(pa->index == pTri->index[0])
				{
					p4 = pa;
				}
				if(pa->index == pTri->index[1])
				{
					p5 = pa;
				}
				if(pa->index == pTri->index[2])
				{
					p6 = pa;
				}
			}			
			pDC->MoveTo(p4->x, p4->y);
			pDC->LineTo(p5->x, p5->y);
			pDC->MoveTo(p5->x, p5->y);
			pDC->LineTo(p6->x, p6->y);
			pDC->MoveTo(p6->x, p6->y);
			pDC->LineTo(p4->x, p4->y);
		}
	}
}

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CDelaunayView message handlers

void CDelaunayView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CDelaunayDoc* pDoc = GetDocument();
	
	startPoint = point;
	PointCls* p = new PointCls(point.x, point.y, pointNumber);
	pDoc->PointList->AddTail(p);
	pointNumber++;

	CClientDC dc(this);
	dc.SetPixel(point, RGB(255, 0, 0));

	CView::OnLButtonDown(nFlags, point);
}

//计算两个向量之间的夹角
//两个向量分别为(x1[0], x1[1]),(x2[0], x2[1])
double  GetAngle(double x1[2],
			     double x2[2])
{
	double temp;
	double norm1,norm2;
	norm1 = sqrt(x1[ 0 ] * x1[ 0 ] + x1[ 1 ] * x1[ 1 ]);
	norm2 = sqrt(x2[ 0 ] * x2[ 0 ] + x2[ 1 ] * x2[ 1 ]);
	temp = x1[ 0 ] * x2[ 0 ] + x1[ 1 ] * x2[ 1 ];
	if(norm1 == 0 || norm2 == 0)
	{
		return 0;
	}
	else
	{
		temp = temp / (norm1 * norm2);
		if(temp > 1.0)
		{
			temp = 1.0;
		}
		else if(temp < -1.0)
		{
			temp = -1.0;
		}
		return acos(temp);
	}	
}

void CDelaunayView::createFirstTri(CObList* pointList, 
								   CObList* triList,
								   PointCls* p1)
{
	POSITION pos1, pos4, pos5, pos6, pos7, pos8;
	PointCls *p2, *p3;
	double distance = 1e20;
	double maxAngle = 0.0;
	bool inside1 = false;
	bool inside2 = false;

	bool again = false;
	
	pos1 = pointList->GetHeadPosition(); 
	if(p1 == NULL)
	{
		p1 = (PointCls*)pointList->GetNext(pos1);
	}
	else
	{
		again = true;
	}

	if(p1->vertex)//p1的所有边的使用次数均为2
		return;
//////////////////////////////////////////////////////////////////////
	//在点表中寻找距离p1最近的点p2
	while(pos1 != NULL)
	{
		pos4 = pos1;
		PointCls* pa = (PointCls*)pointList->GetNext(pos1);
		if(pa->vertex)
			continue;
//		if(again)
//		{
//			if(!pa->intri)
//				continue;
//		}
		double tempDis = sqrt((pa->x - p1->x) * (pa->x - p1->x) +
			(pa->y - p1->y) * (pa->y - p1->y));
		if(tempDis < distance
			&& tempDis > 0)
		{
			inside1 = true;
			distance = tempDis;
			pos5 = pos4;
		}
	}
	if(inside1)
	{
		p2 = (PointCls*)pointList->GetAt(pos5);
	}
	else
		return;
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
	//在点表中寻找与p1，p2所成夹角最大的点
	if(p2->intri)
	{
		pos6 = pointList->GetHeadPosition();
		while(pos6 != NULL)
		{
			pos7 = pos6;
			PointCls* p = (PointCls*)pointList->GetNext(pos6);

			POSITION position1, position2, position3;
			bool inEdgeList = false;
			position1 = p2->edgeList->GetHeadPosition();
			while(position1 != NULL)
			{
				position2 = position1;
				EdgeNode* pTemp = (EdgeNode*)p2->edgeList->GetNext(position1);
				if(pTemp->index == p->index)
				{
					inEdgeList = true;
					position3 = position2;
					break;
				}
			}
			if(!inEdgeList)
				continue;
			else
			{
				if(p->vertex)
					continue;
				
				double x1[2], x2[2];
				x1[0] = p1->x - p->x;
				x1[1] = p1->y - p->y;
				x2[0] = p2->x - p->x;
				x2[1] = p2->y - p->y;
				double angle = GetAngle(x1, x2);
				if(angle > maxAngle)
				{
					inside2 = true;
					maxAngle = angle;
					pos8 = pos7;
				}
			}
		}
		if(inside2)
		{
			p3 = (PointCls*)pointList->GetAt(pos8);
		}
		else
			return;
	}
	else
	{
		pos6 = pointList->GetHeadPosition(); 
		while(pos6 != NULL)
		{
			pos7 = pos6;
			PointCls* p = (PointCls*)pointList->GetNext(pos6);
			if(p->vertex)
				continue;
			double x1[2], x2[2];
			x1[0] = p1->x - p->x;
			x1[1] = p1->y - p->y;
			x2[0] = p2->x - p->x;
			x2[1] = p2->y - p->y;
			double angle = GetAngle(x1, x2);
			if(angle > maxAngle)
			{
				inside2 = true;
				maxAngle = angle;
				pos8 = pos7;
			}
		}
		if(inside2)
		{
			p3 = (PointCls*)pointList->GetAt(pos8);
		}
		else
			return;
	}
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
	//处理p1, p2, p3是当前三角剖分中的点的情形
	if(p1->intri && p2->intri && p3->intri)//p1, p2, p3都在当前剖分中
		return;
	else if(!p1->intri && p2->intri && p3->intri)
	{
		POSITION pos41, pos42, pos43;
		EdgeNode* pEdge10;
		bool inside6 = false;
		pos41 = p2->edgeList->GetHeadPosition();
		while(pos41 != NULL)
		{
			pos42 = pos41;
			EdgeNode* pEdge = (EdgeNode*)p2->edgeList->GetNext(pos41);
			if(pEdge->index == p3->index)
			{
				inside6 = true;
				pos43 = pos42;
				break;
			}
		}		
		
		if(inside6)
		{
			pEdge10 = (EdgeNode*)p2->edgeList->GetAt(pos43);
			pEdge10->nCount++;
		}
		else
		{
			EdgeNode* pEdge11 = new EdgeNode(p3->index, 1);
			p2->edgeList->AddTail(pEdge11);
		}

		POSITION pos51, pos52, pos53;
		EdgeNode* pEdge12;
		bool inside7 = false;
		pos51 = p3->edgeList->GetHeadPosition();
		while(pos51 != NULL)
		{
			pos52 = pos51;
			EdgeNode* pEdge = (EdgeNode*)p3->edgeList->GetNext(pos51);
			if(pEdge->index == p2->index)
			{
				inside7 = true;
				pos53 = pos52;
				break;
			}
		}		
		
		if(inside7)
		{
			pEdge12 = (EdgeNode*)p3->edgeList->GetAt(pos53);
			pEdge12->nCount++;
		}
		else
		{
			EdgeNode* pEdge13 = new EdgeNode(p2->index, 1);
			p3->edgeList->AddTail(pEdge13);
		}

		EdgeNode* pEdge1 = new EdgeNode(p2->index, 1);
	    EdgeNode* pEdge2 = new EdgeNode(p3->index, 1);
		EdgeNode* pEdge3 = new EdgeNode(p1->index, 1);
		EdgeNode* pEdge4 = new EdgeNode(p1->index, 1);

		p1->edgeList->AddTail(pEdge1);
	    p1->edgeList->AddTail(pEdge2);

		p2->edgeList->AddTail(pEdge3);
		p3->edgeList->AddTail(pEdge4);
	}
	else if(p1->intri && !p2->intri && p3->intri)
	{
		POSITION pos41, pos42, pos43;
		EdgeNode* pEdge10;
		bool inside6 = false;
		pos41 = p1->edgeList->GetHeadPosition();
		while(pos41 != NULL)
		{
			pos42 = pos41;
			EdgeNode* pEdge = (EdgeNode*)p1->edgeList->GetNext(pos41);
			if(pEdge->index == p3->index)
			{
				inside6 = true;
				pos43 = pos42;
				break;
			}
		}		
		
		if(inside6)
		{
			pEdge10 = (EdgeNode*)p1->edgeList->GetAt(pos43);
			pEdge10->nCount++;
		}
		else
		{
			EdgeNode* pEdge11 = new EdgeNode(p3->index, 1);
			p1->edgeList->AddTail(pEdge11);
		}

		POSITION pos51, pos52, pos53;
		EdgeNode* pEdge12;
		bool inside7 = false;
		pos51 = p3->edgeList->GetHeadPosition();
		while(pos51 != NULL)
		{
			pos52 = pos51;
			EdgeNode* pEdge = (EdgeNode*)p3->edgeList->GetNext(pos51);
			if(pEdge->index == p1->index)
			{
				inside7 = true;
				pos53 = pos52;
				break;
			}
		}		
		
		if(inside7)
		{
			pEdge12 = (EdgeNode*)p3->edgeList->GetAt(pos53);
			pEdge12->nCount++;
		}
		else
		{
			EdgeNode* pEdge13 = new EdgeNode(p1->index, 1);
			p3->edgeList->AddTail(pEdge13);
		}

		EdgeNode* pEdge1 = new EdgeNode(p1->index, 1);
	    EdgeNode* pEdge2 = new EdgeNode(p3->index, 1);
		EdgeNode* pEdge3 = new EdgeNode(p2->index, 1);
		EdgeNode* pEdge4 = new EdgeNode(p2->index, 1);

		p2->edgeList->AddTail(pEdge1);
	    p2->edgeList->AddTail(pEdge2);

		p1->edgeList->AddTail(pEdge3);
		p3->edgeList->AddTail(pEdge4);
	}
	else if(p1->intri && p2->intri && !p3->intri)
	{
		POSITION pos41, pos42, pos43;
		EdgeNode* pEdge10;
		bool inside6 = false;
		pos41 = p1->edgeList->GetHeadPosition();
		while(pos41 != NULL)
		{
			pos42 = pos41;
			EdgeNode* pEdge = (EdgeNode*)p1->edgeList->GetNext(pos41);
			if(pEdge->index == p2->index)
			{
				inside6 = true;
				pos43 = pos42;
				break;
			}
		}		
		
		if(inside6)
		{
			pEdge10 = (EdgeNode*)p1->edgeList->GetAt(pos43);
			pEdge10->nCount++;
		}
		else
		{
			EdgeNode* pEdge11 = new EdgeNode(p2->index, 1);
			p1->edgeList->AddTail(pEdge11);
		}

		POSITION pos51, pos52, pos53;
		EdgeNode* pEdge12;
		bool inside7 = false;
		pos51 = p2->edgeList->GetHeadPosition();
		while(pos51 != NULL)
		{
			pos52 = pos51;