delaunaydoc.cpp

采用序列化对象CArchive读入原始数据构建Delaunay三角网的VC++代码。可以鼠标点击加新点进行构网

// DelaunayDoc.cpp : implementation of the CDelaunayDoc class
//

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

#include "DelaunayDoc.h"
#include "pointview.h"

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

/////////////////////////////////////////////////////////////////////////////
// CDelaunayDoc

IMPLEMENT_DYNCREATE(CDelaunayDoc, CDocument)

BEGIN_MESSAGE_MAP(CDelaunayDoc, CDocument)
	//{{AFX_MSG_MAP(CDelaunayDoc)
	ON_COMMAND(ID_BUTTON_ADD, OnButtonAdd)
	ON_UPDATE_COMMAND_UI(ID_BUTTON_ADD, OnUpdateButtonAdd)
	ON_COMMAND(ID_BUTTON_BB, OnButtonBB)
	ON_UPDATE_COMMAND_UI(ID_BUTTON_BB, OnUpdateButtonBB)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDelaunayDoc construction/destruction

CDelaunayDoc::CDelaunayDoc()
{
	// TODO: add one-time construction code here


}

CDelaunayDoc::~CDelaunayDoc()
{
}

BOOL CDelaunayDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)
	//CPointPos* temp=new CPointPos;
	//m_point.Add(temp);
	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CDelaunayDoc serialization

void CDelaunayDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		
	}
	else
	{
		// TODO: add loading code here
	}
	m_con.Serialize(ar);
	m_point.Serialize(ar);////////
	m_tri.Serialize(ar);
//	m_n.Serialize(ar);
}

/////////////////////////////////////////////////////////////////////////////
// CDelaunayDoc diagnostics

#ifdef _DEBUG
void CDelaunayDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CDelaunayDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CDelaunayDoc commands

void CDelaunayDoc::AddPoint(double x, double y)
{
	double z;
	int m_plen;//当前节点个数
	CPointPos *p;
	p=new CPointPos(x,y);
	if(x<=0.4)
	{
		z=0.03-(x-0.2)*(x-0.2)-(y-0.5)*(y-0.5);
	    if(z<0) z=0.1;
		p->m_z=sqrt(z)*double(3);
	}
	else{
	    if(x>=0.6)
		{
			z=0.05-(x-0.8)*(x-0.8)-(y-0.5)*(y-0.5);
	        if(z<0) z=0.1;
		    p->m_z=sqrt(z)*double(1.5);
		}
		else
            p->m_z=0.5;
	}
	//p->m_z=sin((x-0.5)*(y-0.5));
	//z=0.25-(x-0.5)*(x-0.5)-(y-0.5)*(y-0.5);
	//if(z<0) z=0;
	//p->m_z=sqrt(z)*double(4);//;
	//p->m_z = (float)sin(3.0*x)*cos(3.0*y)/3.0f;
	ASSERT(p!=NULL);	
	m_point.Add(p);
	POSITION pos;
	pos=GetFirstViewPosition();
	m_plen=m_point.GetSize();
	while(pos!=NULL)
	{
		CView *pp=GetNextView(pos);
		if(pp->IsKindOf(RUNTIME_CLASS(CPointView)))
		{
			CListCtrl &list=((CPointView*)pp)->GetListCtrl();
			LV_ITEM li;
			CString str;	
			str.Format("%d",m_plen-1);
			li.mask=LVIF_TEXT;
			li.pszText=str.GetBuffer(10);;
			li.iItem=m_plen-1;
			li.iSubItem=0;
			list.InsertItem(&li);
			str.ReleaseBuffer();
			str.Format("%f",p->m_x);
			li.pszText=str.GetBuffer(10);
			li.iItem=m_plen-1;
			li.iSubItem=1;
			list.SetItem(&li);
			str.ReleaseBuffer();
			str.Format("%f",p->m_y);
			li.pszText=str.GetBuffer(10);
			li.iItem=m_plen-1;
			li.iSubItem=2;
			list.SetItem(&li);
			str.ReleaseBuffer();
		}
	}
};
////////////////////////////////////////////
void CDelaunayDoc::DeleteContents() 
{
	int i,max;
	max=m_point.GetSize();
	for(i=0;i<max;i++)
	{
		if(m_point[i]!=NULL)
			delete m_point[i];
		//if(m_n[i]!=NULL)//????????
		//	delete m_n[i];
	}
	m_point.RemoveAll();
//	m_n.RemoveAll();

	POSITION pos = m_tri.GetHeadPosition();
	while( pos != NULL )
	{
		delete m_tri.GetNext( pos );
	}
	m_tri.RemoveAll();
    m_con.RemoveAll();
	m_index.RemoveAll();

	CDocument::DeleteContents();
}
///////////////////////////////////////////////////
void CDelaunayDoc::Center(CTriangle *temp)//外接圆心和半径
{
	ASSERT(temp!=NULL);
	int p1,p2,p3;
	p1=temp->m_p1;
	p2=temp->m_p2;
	p3=temp->m_p3;
    double k21,k31;
	CPointPos* p11=(CPointPos*)m_point[p1];
	CPointPos* p22=(CPointPos*)m_point[p2];
	CPointPos* p33=(CPointPos*)m_point[p3];
	if((p22->m_x-p11->m_x)==0) 
	{
		temp->m_yc=(p11->m_y+p22->m_y)/2;//circle 纵坐标
        k31=(p33->m_y-p11->m_y)/(p33->m_x-p11->m_x);
		if (k31==0)
		{
			temp->m_xc=(p11->m_x+p33->m_x)/2;
		}
		else
		{
		   temp->m_xc=(p11->m_x+p33->m_x)/2+
			   ((p11->m_y+p33->m_y)/2-temp->m_yc)*k31;
		}
	}
	else 
	{
		k21=(p22->m_y-p11->m_y)/(p22->m_x-p11->m_x);
		if (k21==0)
		{
			temp->m_xc=(p11->m_x+p22->m_x)/2;
			if((p22->m_x-p33->m_x)==0) 
			{
				temp->m_yc=(p11->m_y+p33->m_y)/2;
			}
		    else
			{
                k31=(p33->m_y-p11->m_y)/
		          	(p33->m_x-p11->m_x);
		        temp->m_yc=((p33->m_x+p11->m_x)/2-
					         temp->m_xc)/k31+
							 (p11->m_y+p33->m_y)/2;
			}
		}
		else
		{
		    if((p33->m_x-p11->m_x)==0)
			{
				temp->m_yc=(p33->m_y+p11->m_y)/2;
				temp->m_xc=k21*(p11->m_y/2+p22->m_y/2-temp->m_yc)+
								(p11->m_x+p22->m_x)/2;
			}
			else
			{
				 k31=(p33->m_y-p11->m_y)/(p33->m_x-p11->m_x);
				 if(k31==0)
				 {
	                      temp->m_xc=(p11->m_x+p33->m_x)/2;
					      temp->m_yc=((p11->m_x+p22->m_x)/2-
					         temp->m_xc)/k21+
							 (p11->m_y+p22->m_y)/2;
				 }
				 else
				 {
                          temp->m_xc=(k21*k31*(p22->m_y-p33->m_y)+
								(p11->m_x+p22->m_x)*k31-(p11->m_x+p33->m_x)*k21)/(k31-k21);
						  temp->m_xc=temp->m_xc/2;
                          temp->m_yc=((p11->m_x+p22->m_x)/2-
					         temp->m_xc)/k21+
							 (p11->m_y+p22->m_y)/2;
				 }
			}
		}
	}

	temp->m_rad=sqrt((p33->m_x-temp->m_xc)*(p33->m_x-temp->m_xc)
		              + (p33->m_y-temp->m_yc)*(p33->m_y-temp->m_yc));
	
}
///////////////////////////////////////////////////
void CDelaunayDoc::OnButtonAdd() 
{
	m_DoWhat=DO_ADD;	
}

void CDelaunayDoc::OnUpdateButtonAdd(CCmdUI* pCmdUI) 
{
	if(m_DoWhat==DO_ADD)
		pCmdUI->SetCheck(1);
	else 
		pCmdUI->SetCheck(0);
}



void CDelaunayDoc::AddTriangle(int p)
{
  	//add new triangles
	CTriangle* pTriangle;
	int max=m_edge.GetSize();	
	for(int i=0;i<max;i++)
	{
	   //Every triangle is stored anticlockwise,too.
	   if(S(m_edge[i]->m_p1,m_edge[i]->m_p2,p)>0){
				pTriangle=new CTriangle(m_edge[i]->m_p1,m_edge[i]->m_p2,p);
	   }
	   else{
              pTriangle=new CTriangle(m_edge[i]->m_p2,m_edge[i]->m_p1,p);
	   }
	   Center(pTriangle);
       BaryCenter(pTriangle);
	   m_tri.AddTail(pTriangle);						
	}
}



double CDelaunayDoc::S(int p1, int p2, int p3)
{
	//求三角形面积,以右下角为原点时,s>0为逆时针(左转),
	//s=0为三点重合
	double s;
	//POI m_p1,m_p2,m_p3;
	CPointPos *m_p1=new CPointPos(m_point[p1]->m_x,m_point[p1]->m_y);
    CPointPos *m_p2=new CPointPos(m_point[p2]->m_x,m_point[p2]->m_y);
    CPointPos *m_p3=new CPointPos(m_point[p3]->m_x,m_point[p3]->m_y);
	s=m_p1->m_x*m_p2->m_y+m_p2->m_x*m_p3->m_y+m_p1->m_y*
		m_p3->m_x-m_p2->m_y*m_p3->m_x-m_p1->m_y*m_p2->m_x-m_p1->m_x*m_p3->m_y;
	s=s/2;
	delete m_p1;
	delete m_p2;
	delete m_p3;

	return s;
}

int CDelaunayDoc::TwoEdgeSuperposition(CBorder *b1, CBorder *b2)
{
	if(b1==b2 || (b1->m_p1==b2->m_p2 && b1->m_p2==b2->m_p1) ) return 1;
	return 0;
}

int CDelaunayDoc::GetInitEdges(double x, double y, int p)
{
	// GetInitEdges : ransack each trangle to record it's edges
	//when the piont belong it's circle,record the triangle's position in m_tri to m_index
	//'x' and 'y' are the coordinates of the insert point
	//'p' is the mark or th insert point in 'm_point'
	// the returned value 'k/2' is the number of cirecle the point belonged
	POSITION POS;
	CBorder *m_border;
	CBorder *m_border1;
	CTriangle* pTriangle;
	int j=0,i=0,k=0,max=0;
	CPointPos *point=new CPointPos(x,y);
    POS = m_tri.GetHeadPosition();
	while(POS != NULL ){
       i= m_tri.GetAt( POS )->Where(point);
	   
	   if(i==POS_ERROR){
		   return POS_ERROR;
	   }
	   if(i==POS_ON)//in circle POS_ON=2
	   {
		  k=k+i;
		  m_index.Add(POS);
		  pTriangle=m_tri.GetAt(POS);
		  //ransack three edge of a triangle,if an edge of a triangle
		  //have belong to the array 'm_pDoc->m_edge' delete both of them to form 
		  // the border of the inserted polygon which is stored in the array
		  //'m_pDoc->m_edge'
		  int array[4];
		  array[0]=pTriangle->m_p1;
		  array[1]=pTriangle->m_p2;
		  array[2]=pTriangle->m_p3;
		  array[3]=pTriangle->m_p1;
          for(int h=0;h<3;h++)
		  {					  
			 m_border=new CBorder(array[h],array[h+1]);
			 max=m_edge.GetSize();
			 if(max==0)
			 {
                m_edge.Add(m_border);
			 }
			 else
			 {
			    j=0;
			    for(int m=0;m<max;m++)
				{						  				         
				   m_border1=m_edge[m];
				   if(TwoEdgeSuperposition(m_border,m_border1)==1)//?//???
				   {
				      m_edge.RemoveAt(m,1);
					  max=max-1;
					  j++;
				   }
				}
			    if(j==0)
				{
                   m_edge.Add(m_border);
				}				    
			}		 
		  }/////for
	   }/////////////if(POS_ON)
     pTriangle=m_tri.GetNext(POS);
	}//////////////while 
	//if(k==0)//the point don't belong any circle,
	//i.e.don't the convexity
	delete point;
return k;
}

void CDelaunayDoc::DelTriMarked()
{
   int max=m_index.GetSize();
   for(int i=0;i<max;i++)
   {
	  m_tri.RemoveAt(m_index[i]);
   }
}

void CDelaunayDoc::EditCon(int r, int l,int p)
{
	// r : save the value of i as 右支撑点 or 应去凸包边界节点右边界		  
	// l : save the value of i as 左支撑点 or 应去凸包边界节点左边界
	//'p' is the mark or th insert point in 'm_point'
	 CBorder *m_border;
     int hr=0;//record the number of points on edge of convexity that should be deleted before r(include r) 
	 int hl=0;//record the number of points on edge of convexity that should be deleted after l(include l)
	 int i=r;
	 int i1;
	 int h=hr+hl;
	 int max=m_con.GetSize();
	 //search rightward, first
	 if((i+1)>max-1)  i1=i+1-max;	 
	 else  	          i1=i+1;	
	 while(S(p,m_con[i],m_con[i1])<0){                  
			m_border=new CBorder(m_con[i],m_con[i1]);