voronoidoc.cpp

一个很不错的求Voronoi线与最小凸壳的vc++源程序

// VoronoiDoc.cpp : implementation of the CVoronoiDoc class
//

#include "stdafx.h"
#include "Voronoi.h"

#include "VoronoiDoc.h"
#include <math.h>

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

/////////////////////////////////////////////////////////////////////////////
// CVoronoiDoc

IMPLEMENT_DYNCREATE(CVoronoiDoc, CDocument)

BEGIN_MESSAGE_MAP(CVoronoiDoc, CDocument)
	//{{AFX_MSG_MAP(CVoronoiDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CVoronoiDoc construction/destruction
CGraphPara *p_GraphPara;
CVoronoiDoc::CVoronoiDoc()
{
    p_GraphPara=&m_GraphPara;
	m_Index=new int[10000];
	// TODO: add one-time construction code here
}

CVoronoiDoc::~CVoronoiDoc()
{
	delete m_Index;
}

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

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CVoronoiDoc serialization

void CVoronoiDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CVoronoiDoc diagnostics

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

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

/////////////////////////////////////////////////////////////////////////////
// CVoronoiDoc commands

//////////////////////////////////////////////////////////////////////
// CGraphPara Class
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraphPara::CGraphPara()
{
    n_ColorNumb=500;
	n_LayerNumb=100;
	m_ColorList=new long[n_ColorNumb];
	m_LayerList=new LayerStruct[n_LayerNumb];
	n_ColorNumb=4;
	n_LayerNumb=1;
	m_ColorList[0]=RGB(0,0,0);
	m_ColorList[1]=RGB(255,0,0);
	m_ColorList[2]=RGB(0,255,0);
	m_ColorList[3]=RGB(0,0,255);
	m_LayerList[0].b_Display=1;
	strcpy(m_LayerList[0].m_Name,"Layer 0");
	
}

CGraphPara::~CGraphPara()
{
   delete m_LayerList;
   delete m_ColorList;
}
COLORREF CGraphPara::GetColor(int n)
{
	return m_ColorList[n];
}
BOOL CGraphPara::GetDisplayStatue(int n)
{
	return m_LayerList[n].b_Display;
}
CNetPoint* CVoronoiDoc::AddNetPoint(double x,double y,double rRadiu,short Layer,int id_only,short ColorPen)
{   
	CNetPoint* p_Point=new CNetPoint(ColorPen,x,y,rRadiu,Layer,id_only);
    m_NetPointArray.Add(p_Point);
	return p_Point;
}

CPline* CVoronoiDoc::AddPLine(short ColorPen,short ColorBrush,float LineWide,short LineType,
		             short Layer,int id_only,int Number,PointStruct* PointList)
{
	CPline* p_Pline=new CPline(ColorPen,ColorBrush,LineWide,LineType,
		                      Layer,id_only,0,Number,PointList);
	m_PLineArray.Add(p_Pline);
	return p_Pline;
}
CPlineRgn* CVoronoiDoc::AddPLineRgn(short ColorPen,short ColorBrush,float LineWide,short LineType,
		                   short Layer,int id_only,int Number,PointStruct* PointList,
						   BOOL bTransparent,BOOL bFill)
{
    CPlineRgn* p_Plinergn=new CPlineRgn(ColorPen,ColorBrush,LineWide,LineType,
		                                Layer,id_only,0,Number,PointList,bTransparent,bFill);
	m_PLineRgnArray.Add(p_Plinergn);
	return p_Plinergn;
}
CDraw* CVoronoiDoc::GetGraph(short Lb,int Index)
{
	switch(Lb)
	{
	case 1:
		if(Index<0||Index>m_NetPointArray.GetUpperBound())
			return 0;
		return m_NetPointArray.GetAt(Index);
		break;
	case 2:
		if(Index<0||Index>m_PLineArray.GetUpperBound())
			return 0;
		return m_PLineArray.GetAt(Index);
		break;
	case 3:
		if(Index<0||Index>m_PLineRgnArray.GetUpperBound())
			return 0;
		return m_PLineRgnArray.GetAt(Index);
		break;
	default:
		return 0;
	}
}
int CVoronoiDoc::GetGraphNumb(short Lb)
{
	switch(Lb)
	{
	case 1:
		return m_NetPointArray.GetSize();
		break;
	case 2:
		return m_PLineArray.GetSize();
		break;
	case 3:
		return m_PLineRgnArray.GetSize();
		break;
	default:
		return 0;
	}
}
int CVoronoiDoc::GetGraphUpperBound(short Lb)
{
	switch(Lb)
	{
	case 1:
		return m_NetPointArray.GetUpperBound();
		break;
	case 2:
		return m_PLineArray.GetUpperBound();
		break;
	case 3:
		return m_PLineRgnArray.GetUpperBound();
		break;
	default:
		return -1;
		break;
	}
	return -1;
}
int CVoronoiDoc::GetGraphID()
{
	int pn=GetGraphUpperBound(1)+1;
	for(int i=0;i<10000;i++)
		m_Index[i]=0;
    for(i=0;i<=pn;i++)
	{
		if(GetGraph(1,i))
			m_Index[GetGraph(1,i)->GetID()]=1;
	}
	for(i=0;i<10000;i++)
	{
		if(m_Index[i]==0)
			return i;
	}
	return -1;
}
void CVoronoiDoc::Draw(CDC *pDC,int m_DrawMode,int m_DrawModel,short BackColor)
{
	for(int i=1;i<=3;i++)
	{ 
       int nn=GetGraphUpperBound(i)+1;
	   int m=nn;
	   while(nn--)
	   GetGraph(i,m-nn-1)->Draw(pDC,m_DrawMode,m_DrawModel,BackColor,m-nn-1);
	}
}

void CVoronoiDoc::GetProtrude(CDC *pDC)
{
    int i;
	int n=m_NetPointArray.GetUpperBound();
	PointStruct* PointList;
    PointList=new PointStruct[n+1];
	for(i=0;i<=n;i++)
	{
		PointList[i].x=m_NetPointArray.GetAt(i)->ReturnX();
	    PointList[i].y=m_NetPointArray.GetAt(i)->ReturnY();
	}
	ConstructProtrude(PointList,n+1)->Draw(pDC,0,0,0,1);
}
CPlineRgn* CVoronoiDoc::ConstructProtrude(PointStruct *PointList,int n)
{
    int id=0,i,j,k=0;
	double ctan[10000];
    PointStruct* PointList1;
	for(i=0;i<n;i++)
	{
		if(PointList[id].y>PointList[i].y)
		   id=i;
	}
	ctan[id]=-1e20;
	for(i=0;i<n;i++)
	{
        if(i!=id)
		   ctan[i]=(PointList[i].x-PointList[id].x)/(PointList[i].y-PointList[id].y);
	}
	PointList1=new PointStruct[n];
	PointList1[0].x=PointList[id].x;
	PointList1[0].y=PointList[id].y;
    k=0;
    for(i=1;i<n;i++)
	{
	    for(j=0;j<n;j++)
		{
			if(ctan[k]<ctan[j])
				k=j;
		}
		PointList1[i].x=PointList[k].x;
	    PointList1[i].y=PointList[k].y;
        ctan[k]=-1e20;
	}
//	AddPLineRgn(3,1,5.0,1,1,1,n+1,PointList,FALSE,FALSE)->Draw(pDC,0,0,0,1);
	k=3;
	do
	{
        j=1;
		do
		{
	        if(!same(PointList1[0].x,PointList1[0].y,PointList1[k].x,PointList1[k].y,
		            PointList1[k-j-1].x,PointList1[k-j-1].y,PointList1[k-j].x,PointList1[k-j].y))
			{
		        for(i=k;i<n;i++)
				{
					PointList1[i-1].x=PointList1[i].x;
                    PointList1[i-1].y=PointList1[i].y;
                }
				n--;
				k=k-1;
		        j=j-1;
			}
	        j=j+1;
		}while(j<k-1);
	    k=k+1;
	}while(k<n);
	CPlineRgn* p_Plinergn=new CPlineRgn(1,1,5.0,1,1,1,0,n,PointList1,FALSE,FALSE);
	return p_Plinergn;
}

BOOL CVoronoiDoc::same(double x1,double y1,double x2,double y2,double lx1,double ly1,double lx2,double ly2)
{
    double dx,dy,dx1,dy1,dx2,dy2,same;
	dx=lx2-lx1;
	dy=ly2-ly1;
	dx1=x1-lx1;
	dy1=y1-ly1;
	dx2=x2-lx2;
	dy2=y2-ly2;
	same=(dx*dy1-dy*dx1)*(dx*dy2-dy*dx2);
	if(same>0)
		return TRUE;
	else 
		return FALSE;
}
void CVoronoiDoc::GetVoronoi(CDC *pDC)
{
    PointStruct* PointList;
	PointStruct* PointList1;
    LineStruct* LineList;
	int i,j,num;
	double t0,t1;
	int n=m_NetPointArray.GetUpperBound();
	PointList=new PointStruct[n+1];
	PointList1=new PointStruct[2];
	LineList=new LineStruct[10000];
    for(i=0;i<10000;i++)
	    LineList[i].exist=FALSE;
    for(i=0;i<=n;i++)
	{
		PointList[i].x=m_NetPointArray.GetAt(i)->ReturnX();
		PointList[i].y=m_NetPointArray.GetAt(i)->ReturnY();
	}
	for(i=1;i<=n;i++)
	{
		for(t0=PointList[i].x,t1=PointList[i].y,j=i-1;j>=0&&t0<PointList[j].x;j--)
		{
			PointList[j+1].x=PointList[j].x;
            PointList[j+1].y=PointList[j].y;
		}
		PointList[j+1].x=t0;
		PointList[j+1].y=t1;
	}
    num=ConstructVoronoi(n+1,PointList,pDC,LineList);
	i=0;
	for(i=0;i<num;i++)
	{
		if(LineList[i].exist==TRUE)
		{
            PointList1[0].x=LineList[i].x1;
		    PointList1[0].y=LineList[i].y1;
		    PointList1[1].x=LineList[i].x2;
		    PointList1[1].y=LineList[i].y2;
		    AddPLine(1,1,2.0,1,2,2,2,PointList1)->Draw(pDC,0,0,0,2);
		}
	}
}
int CVoronoiDoc::ConstructVoronoi(int n, PointStruct *PointList,CDC *pDC,LineStruct* LineList)
{
   int j,k,m;
   CString str;
   PointStruct* PointList1;
   PointStruct* PointList2;
   PointList1=PointList;
   PointList2=&PointList[n/2];
   if(n<=4)
   {
	   if(n==1)
		   return 0;
	   else if(n==2)
	   {
		   ZCX(&PointList[0],&PointList[1],LineList);
		   LineList[0].Point1=&PointList[0];
           LineList[0].Point2=&PointList[1];
		   LineList[0].exist=TRUE;
		   return 1;
        }
	  else if(n==3)
	  {
           TriangularVoronoi(PointList,LineList);
		   return 3;
	  }
	  else 
	  {   
           j=FourPointVoronoi(PointList,LineList);
		   return j;
	  } 
   }
   else
   {
      j=ConstructVoronoi(n/2,PointList1,pDC,LineList);
	  k=ConstructVoronoi(n-n/2,PointList2,pDC,LineList+j);
	  m=ZX(n,j,k,LineList,PointList);
	  return j+k+m;
   }
   
}

PointStruct* CVoronoiDoc::intersect(LineStruct* Line1, LineStruct* Line2)
{
   PointStruct* Point;
   Point=new PointStruct;
   double t1,t2,D;
   D=Line1->x1*(Line2->y2-Line2->y1)+Line1->x2*(Line2->y1-Line2->y2)+
     Line2->x2*(Line1->y2-Line1->y1)+Line2->x1*(Line1->y1-Line1->y2);
   t1=(Line1->x1*(Line2->y2-Line2->y1)+Line2->x1*(Line1->y1-Line2->y2)+
	   Line2->x2*(Line2->y1-Line1->y1))/D;
   t2=-(Line1->x1*(Line2->y1-Line1->y2)+Line1->x2*(Line1->y1-Line2->y1)+
       Line2->x1*(Line1->y2-Line1->y1))/D;
   Point->x=Line1->x1+t1*(Line1->x2-Line1->x1);
   Point->y=Line1->y1+t1*(Line1->y2-Line1->y1);
   return Point;
}

void CVoronoiDoc::ZCX(PointStruct *Point1, PointStruct *Point2, LineStruct* Line)
{
   if(Point1->x==Point2->x)
   {
	   Line->y1=(Point1->y+Point2->y)/2;
       Line->y2=(Point1->y+Point2->y)/2;
       Line->x1=-(1e+5);
       Line->x2=1e+5;
   }
   else if((Point2->y-Point1->y)/(Point2->x-Point1->x)<=1)
   {
	   Line->x1=((Point2->y*Point2->y-Point1->y*Point1->y+Point2->x*Point2->x-Point1->x*Point1->x)/
				(2*(Point2->y-Point1->y))+(1e+5))*(Point2->y-Point1->y)/(Point2->x-Point1->x);
       Line->y1=-(1e+5);
	   Line->y2=1e+5;
	   Line->x2=((Point2->y*Point2->y-Point1->y*Point1->y+Point2->x*Point2->x-Point1->x*Point1->x)/
				(2*(Point2->y-Point1->y))-(1e+5))*(Point2->y-Point1->y)/(Point2->x-Point1->x);
   }
   else
   {
       Line->x1=-(1e+5);
       Line->y1=-(Point2->x-Point1->x)/(Point2->y-Point1->y)*Line->x1+(Point2->y*Point2->y-
		        Point1->y*Point1->y+Point2->x*Point2->x-Point1->x*Point1->x)/(2*(Point2->y-Point1->y));
       Line->x2=1e+5;
	   Line->y2=-(Point2->x-Point1->x)/(Point2->y-Point1->y)*Line->x2+(Point2->y*Point2->y-
		        Point1->y*Point1->y+Point2->x*Point2->x-Point1->x*Point1->x)/(2*(Point2->y-Point1->y));
   }
   Line->Point1=Point1;
   Line->Point2=Point2;
}

BOOL CVoronoiDoc::IntersectOrNot(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
   if(!same(x1,y1,x2,y2,x3,y3,x4,y4)&&!same(x3,y3,x4,y4,x1,y1,x2,y2))
	   return TRUE;
   else
	   return FALSE;
}

short CVoronoiDoc::RZDJ(PointStruct* Point1,PointStruct* Point2,PointStruct* Point3)
{
   if((Point2->y-Point1->y)*(Point2->y-Point1->y)+(Point2->x-Point1->x)*(Point2->x-Point1->x)+
	  (Point2->y-Point3->y)*(Point2->y-Point3->y)+(Point2->x-Point3->x)*(Point2->x-Point3->x)-
	  (Point1->y-Point3->y)*(Point1->y-Point3->y)-(Point1->x-Point3->x)*(Point1->x-Point3->x)>0)
      return 1;
   else if((Point2->y-Point1->y)*(Point2->y-Point1->y)+(Point2->x-Point1->x)*(Point2->x-Point1->x)+
	  (Point2->y-Point3->y)*(Point2->y-Point3->y)+(Point2->x-Point3->x)*(Point2->x-Point3->x)-
	  (Point1->y-Point3->y)*(Point1->y-Point3->y)-(Point1->x-Point3->x)*(Point1->x-Point3->x)==0)
       return 2;
   else 
	   return 3;
}

void CVoronoiDoc::TriangularVoronoi(PointStruct *PointList,LineStruct* LineList)
{
   PointStruct* Point;