gendelaunayview.cpp

一个二维Delaunay三角网格剖分算法

// GenDelaunayView.cpp : implementation of the CGenDelaunayView class
//

#include "stdafx.h"
#include "GenDelaunay.h"

#include "GenDelaunayDoc.h"
#include "GenDelaunayView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView

IMPLEMENT_DYNCREATE(CGenDelaunayView, CView)

BEGIN_MESSAGE_MAP(CGenDelaunayView, CView)
	//{{AFX_MSG_MAP(CGenDelaunayView)
	ON_WM_LBUTTONDOWN()
	ON_WM_SIZE()
	ON_WM_CREATE()
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView construction/destruction

CGenDelaunayView::CGenDelaunayView()
{
	// TODO: add construction code here

}

CGenDelaunayView::~CGenDelaunayView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView drawing

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


	DrawScene();
}

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CGenDelaunayView message handlers

void CGenDelaunayView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	ASSERT(m_pDoc!=NULL);
	CPoint pos=point;
	int m_plen;//当前节点个数
	double s;
	//ScreenToClient(&pos);
		//'x' and 'y' are that to be stored in 'm_point'
		double x,y;
 		//x=double(pos.x)/double(m_oldRect.right);
		//y=double((m_oldRect.bottom-pos.y))/double(m_oldRect.bottom);
	
		x=double(pos.x);
		y=double(pos.y);
	
		
		//归一化  同时变成y轴向上记录y的值
		//form the original convexity when 'm_plen' is smaller than 3
		//the original convexity is a triangle
		m_plen=m_pDoc->m_point.GetSize();//==1????
		switch(m_plen) 
		{
		case 0 :
			m_pDoc->AddPoint(x,y);				
			m_pDoc->m_con.SetAtGrow(0,0);				
			break;
		case 1 :
			if(m_pDoc->m_point[0]->m_x==x &&
				m_pDoc->m_point[0]->m_y==y)
			{
				AfxMessageBox("The two point not suitable");
				break;
				//please 输入节点,跳出
			}
			m_pDoc->AddPoint(x,y);
			m_pDoc->m_con.SetAtGrow(1,1);						
			break;
		case 2 ://确保凸包顶点逆时针存储
			m_pDoc->AddPoint(x,y);
			s=m_pDoc->S(0,1,2);
			if(s==0)
			{						
				AfxMessageBox("please 输入节点 again,因三点共线,跳出");
				m_pDoc->m_point.RemoveAt(2,1);
				//m_pDoc->m_n.RemoveAt(2,1);
			}
			
			m_plen=m_pDoc->m_point.GetSize();
			m_pDoc->m_con.SetAtGrow(m_plen-1,m_plen-1);                    
			if(s<0) 
			{
				m_pDoc->m_con[0]=1;
				m_pDoc->m_con[1]=0;                          
			}																		
			CTriangle* pTriangle;
			pTriangle=new CTriangle(m_pDoc->m_con[0],
				m_pDoc->m_con[1],m_pDoc->m_con[2]);
			m_pDoc->Center(pTriangle);
			m_pDoc->BaryCenter(pTriangle);
			m_pDoc->m_tri.AddHead(pTriangle);                   
			break;
		default :
			m_pDoc->AddPoint(x,y);
			m_plen=m_pDoc->m_point.GetSize();				
			int i=DelTriList(x,y,m_plen-1);
			if(i==POS_ERROR){
				int k=m_pDoc->m_point.GetSize();
				m_pDoc->m_point.RemoveAt(k-1,1);
			}
			break;
		}
		Invalidate();
	
	////////////////////////////////////////////
	CView::OnLButtonDown(nFlags, point);
}

void CGenDelaunayView::OnSize(UINT nType, int cx, int cy) 
{
	CView::OnSize(nType, cx, cy);
	if(cy>0)
	{
		m_oldRect.right=cx;
		m_oldRect.bottom=cy;		
	}

	// TODO: Add your message handler code here
	
}

int CGenDelaunayView::DelTriList(double x, double y,int p)
{//record the position of triangles which are to be deleted
	//'x' and 'y' are the coordinates of the insert point
	//'p' is the mark or th insert point in 'm_point'
	
	CPointPos *point=new CPointPos(x,y);
	int j=0,i=0,k=0,max=0;
	array a;
	// GetInitEdges : ransack each trangle to record it's edges
	//when the piont belong it's circle
	k=m_pDoc->GetInitEdges(x,y,p);// the returned value 'k/2' is the number of cirecle the point belonged??
	if(k==POS_ERROR){
		return POS_ERROR;
	}
	//默认:插入点属于某个外接圆,且属于凸包
	//judge a point belong to the convexity or not
		  a=Wher(point);
		  /*return Value:a.a
		  POS_IN=1,a point  belong a triangle or convexity
		  POS_ON=2,a point belong a circle or on the edge of convexity
		  POS_OUT=0,a point out of a circle or convexity
		  a.b , a.c: record the point's mark in m_con */
		  max=m_pDoc->m_con.GetSize();
		  if(0==a.a && k>=2)//插入点属于某个外接圆,但不属于凸包
		  {  //delete an edge "belong to" the inserted polygon,the edge is also 
			  //belong  to the border of the convexity
			  if (max==3){
				  int t=m_pDoc->m_edge.GetSize();			      
				  for(j=0;j<t;j++){
					  if((m_pDoc->m_edge[j]->m_p1==m_pDoc->m_con[a.b]) & 
						  (m_pDoc->m_edge[j]->m_p2==m_pDoc->m_con[a.c]))
					  {
						  m_pDoc->m_edge.RemoveAt(j,1);
						  m_pDoc->m_con.InsertAt(a.c,p);
						  break;
					  }
				  }
			  }
			  else
			  {
				  CWordArray con_index;//save the point's mark can be saw on the con	
				  for(i=0;i<max-1;i++)
				  {
					  int t=m_pDoc->m_edge.GetSize();			      
					  for(j=0;j<t;j++){
						  if((m_pDoc->m_edge[j]->m_p1==m_pDoc->m_con[i]) & 
							  (m_pDoc->m_edge[j]->m_p2==m_pDoc->m_con[i+1]))
						  {
							  bool y=m_pDoc->DelEdgeOrNot(m_pDoc->m_edge[j]->m_p1,m_pDoc->m_edge[j]->m_p2,p);
							  if(y){
								  m_pDoc->m_edge.RemoveAt(j,1);
								  con_index.Add(i);
								  con_index.Add(i+1);					   
								  break;
							  }
						  }
					  }
				  }//end for i
				  int t=m_pDoc->m_edge.GetSize();			      
				  for(j=0;j<t;j++){       
					  if((m_pDoc->m_edge[j]->m_p1==m_pDoc->m_con[max-1]) && 
						  (m_pDoc->m_edge[j]->m_p2==m_pDoc->m_con[0]))
					  {
						  bool y=m_pDoc->DelEdgeOrNot(m_pDoc->m_edge[j]->m_p1,m_pDoc->m_edge[j]->m_p2,p);
						  if(y){
							  m_pDoc->m_edge.RemoveAt(j,1);
							  con_index.Add(max-1);
							  con_index.Add(0);					   
							  break;
						  }					 					  
					  }			
				  }
				  t=con_index.GetSize();
				  m_pDoc->EditCon(con_index[t-1],con_index[0],p);				
			  }	
		  }
		  if(k==0){//插入点不属于任意一个外接圆,显然也不属于凸包
			  CBorder * m_border;
			  m_border=new CBorder(m_pDoc->m_con[a.b],m_pDoc->m_con[a.c]);
			  m_pDoc->m_edge.Add(m_border);
			  m_pDoc->EditCon(a.c,a.b,p);
		  }	
		  //Delete triangles that have been marked
		  m_pDoc->DelTriMarked();
		  //add new triangles
		  m_pDoc->AddTriangle(p);
		  max=m_pDoc->m_index.GetSize();
		  m_pDoc->m_index.RemoveAt(0,max);//RemoveAll : no use ???
		  m_pDoc->m_edge.RemoveAll();
}



array CGenDelaunayView::Wher(CPointPos *pos)
{
	//Points and Convexity
	/*return Value:a.a
	POS_IN=1,a point  belong a triangle or convexity
	POS_ON=2,a point belong a circle or on the edge of convexity
	POS_OUT=0,a point out of a circle or convexity
	a.b , a.c: record the point's mark in m_con */
	//1. get a ponit in convexity:p
	array a;
	int max=m_pDoc->m_con.GetSize();
	int z=max/2;
	CPointPos *p1=new CPointPos(m_pDoc->m_point[m_pDoc->m_con[0]]->m_x,
		m_pDoc->m_point[m_pDoc->m_con[0]]->m_y);
    CPointPos *p2=new CPointPos(m_pDoc->m_point[m_pDoc->m_con[z]]->m_x,
		m_pDoc->m_point[m_pDoc->m_con[z]]->m_y);
    CPointPos *p3=new CPointPos(m_pDoc->m_point[m_pDoc->m_con[max-1]]->m_x,
		m_pDoc->m_point[m_pDoc->m_con[max-1]]->m_y);
	CPointPos *p=new CPointPos((p1->m_x+p2->m_x+p3->m_x)/3,
		(p1->m_y+p2->m_y+p3->m_y)/3);
	p3->m_x=double(pos->m_x);
	p3->m_y=double(pos->m_y);
	//遍寻Convexity
	double s1,s2,s;
	for(int i=0;i<max-1;i++)
	{
		p1->m_x=m_pDoc->m_point[m_pDoc->m_con[i]]->m_x;
		p1->m_y=m_pDoc->m_point[m_pDoc->m_con[i]]->m_y;
		p2->m_x=m_pDoc->m_point[m_pDoc->m_con[i+1]]->m_x;
		p2->m_y=m_pDoc->m_point[m_pDoc->m_con[i+1]]->m_y;
        
		s1=m_pDoc->S(p3,p,p1);
		s2=m_pDoc->S(p3,p,p2);
		if(s1>0 && s2<0)//the point in the 扇形 con[i],con[i+1] and p formed
		{
			a.b=i;
			a.c=i+1;
			s=m_pDoc->S(p1,p2,p3);
			if(s>0)
			{
				a.a=1;//POS_IN			 
			}
			if(s==0)
			{
				a.a=2;//POS_ON
			}
			if(s<0)
			{
				a.a=0;//POS_OUT
			}
			return a;
		}         		
	}
    p1->m_x=m_pDoc->m_point[m_pDoc->m_con[i]]->m_x;
	p1->m_y=m_pDoc->m_point[m_pDoc->m_con[i]]->m_y;
    p2->m_x=m_pDoc->m_point[m_pDoc->m_con[0]]->m_x;
	p2->m_y=m_pDoc->m_point[m_pDoc->m_con[0]]->m_y;
	s1=m_pDoc->S(p3,p,p1);
	s2=m_pDoc->S(p3,p,p2);
	if(s1>0 && s2<0)
	{
		a.b=i;
		a.c=0;
		s=m_pDoc->S(p1,p2,p3);
		if(s>0)
		{
			a.a=1;//POS_IN			 
		}
		if(s==0)
		{
			a.a=2;//POS_ON
		}
		if(s<0)
		{
			a.a=0;//POS_OUT
		}
		return a;
	}         		 
}

int CGenDelaunayView::OnCreate(LPCREATESTRUCT lpCreateStruct) 
{
	if (CView::OnCreate(lpCreateStruct) == -1)
		return -1;
	// TODO: Add your specialized creation code here
	m_pDoc=this->GetDocument();	
	
	return 0;
}


void CGenDelaunayView::DrawScene()
{	

		DrawPoints();
		DrawTris();

}
void CGenDelaunayView::DrawPoints()
{
	int max=m_pDoc->m_point.GetSize();

	for(int i=0;i<max;i++)
	{
		DrawPoint(i);
	}
}

void CGenDelaunayView::DrawPoint(int i)
{
	double x,y,z;
	x=m_pDoc->m_point[i]->m_x;
	y=m_pDoc->m_point[i]->m_y;
	z=m_pDoc->m_point[i]->m_z;

	CClientDC dc(this);

    CPen pen(PS_SOLID,5,RGB(255,0,0));
    dc.SelectObject(&pen);
    
    dc.Rectangle(x-1,y-1,x,y);


	//dc.SetPixel(x*100,y*100,RGB(255,0,0));
}

void CGenDelaunayView::DrawTris()
{
	POSITION POS;
	CTriangle* pTriangle;
	POS = m_pDoc->m_tri.GetHeadPosition();
	while(POS != NULL )
	{	
		DrawTri(m_pDoc->m_tri.GetAt(POS));	
		pTriangle=m_pDoc->m_tri.GetNext(POS);
	}   
}


void CGenDelaunayView::DrawTri(CTriangle *tri)
{
	int i;
	//POI normal;
	int p1,p2,p3;
	p1=tri->m_p1;
	p2=tri->m_p2;
	p3=tri->m_p3;

//		glVertex3d(m_pDoc->m_point[p1]->m_x,m_pDoc->m_point[p1]->m_y,0.0); 	
//    	glVertex3d(m_pDoc->m_point[p2]->m_x,m_pDoc->m_point[p2]->m_y,0.0);	
//		glVertex3d(m_pDoc->m_point[p3]->m_x,m_pDoc->m_point[p3]->m_y,0.0);


		CClientDC dc(this);
		dc.MoveTo(m_pDoc->m_point[p1]->m_x,m_pDoc->m_point[p1]->m_y);
		dc.LineTo(m_pDoc->m_point[p2]->m_x,m_pDoc->m_point[p2]->m_y);

		dc.MoveTo(m_pDoc->m_point[p2]->m_x,m_pDoc->m_point[p2]->m_y);
		dc.LineTo(m_pDoc->m_point[p3]->m_x,m_pDoc->m_point[p3]->m_y);

		dc.MoveTo(m_pDoc->m_point[p3]->m_x,m_pDoc->m_point[p3]->m_y);
		dc.LineTo(m_pDoc->m_point[p1]->m_x,m_pDoc->m_point[p1]->m_y);


}