分治法计算Voronoi图

分治法计算Voronoi图

#include “StdAfx.h“
#include “iostream“
#include “stdio.h“
#include “conio.h“
#include “malloc.h“
#include “ConvexHull.h“


//struct edge;
//struct site;
//struct vertex;
//struct face ;




//判断（x3y3）是不是在（x1y1）（x2y2）连线的左边.以（x1y1）为出发点.
int ToLeft（double x1  double y1 double x2 double y2 double x3 double y3）
{
/*
 （
			a.x * b.y - a.y * b.x
		+	b.x * c.y - b.y * c.x
		+	c.x * a.y - c.y * a.x）;
 */
		double itemp =	   x1 * y2 - y1 * x2 
					+  x2 * y3 - y2 * x3
					+  x3 * y1 - y3 * x1;
		return itemp <= 0 ;
}




convex::convex（）
{
	m_pFirstPoint		= NULL;
	m_iCount = 0;
	m_pLeftMostPoint	= NULL;
	m_pRightMostPoint	= NULL;

}

convex::convex（ int iCount）
{
	//为点分配空间
	m_pFirstPoint = （point_chain *）malloc（iCount * sizeof（point_chain））;
	m_iCount = 0;
	//初始化最右边和最左边的点为空
	m_pLeftMostPoint	= NULL;
	m_pRightMostPoint	= NULL;
}

//用三个点构造一个凸包
convex::convex（ site * pFirstSite    site * pSecondSite   site * pThirdSite）
{
	//生成三个元素
	point_chain * pFirstChain  = new point_chain;
	point_chain * pSecondChain = new point_chain;
	point_chain * pThirdChain  = new point_chain;

//	 site * pLeftSite ;
//	 site * pMidSite	 ;
//	 site * pRightSite;

	pFirstChain->pSite  = pFirstSite;
	pSecondChain->pSite = pSecondSite;
	pThirdChain->pSite  = pThirdSite;


	if （ToLeft（pFirstSite->xpFirstSite->ypSecondSite->xpSecondSite->ypThirdSite->xpThirdSite->y） > 0）
	{
		pThirdChain->next	= pSecondChain;
		pSecondChain->next	= pFirstChain;
		pFirstChain->next	= pThirdChain;
	

		pFirstChain->previous	 = pSecondChain;
		pSecondChain->previous	 = pThirdChain;
		pThirdChain->previous	 = pFirstChain;
	}
	else
	{
		pThirdChain->next	= pFirstChain;
		pSecondChain->next	= pThirdChain;
		pFirstChain->next	= pSecondChain;
	

		pFirstChain->previous	 = pThirdChain;
		pSecondChain->previous	 = pFirstChain;
		pThirdChain->previous	 = pSecondChain;
	}
	
	
	
	if （pFirstSite->x < pSecondSite->x ||（ pFirstSite->x == pSecondSite->x && pFirstSite->y < pSecondSite->y））
	{
		m_pLeftMostPoint	=	pFirstChain;
	}
	else
	{
		m_pLeftMostPoint	=	pSecondChain;
	}
	
	if （m_pLeftMostPoint->pSite->x > pThirdSite->x || （m_pLeftMostPoint->pSite->x == pThirdSite->x） && m_pLeftMostPoint->pSite->y > pThirdSite->y）
	{
		m_pLeftMostPoint	=	pThirdChain;
	}



	//最右边
	if （pFirstSite->x > pSecondSite->x ||（ pFirstSite->x == pSecondSite->x && pFirstSite->y > pSecondSite->y））
	{
		m_pRightMostPoint	=	pFirstChain;
	}
	else
	{
		m_pRightMostPoint	=	pSecondChain;
	}
	
	if （m_pRightMostPoint->pSite->x < pThirdSite->x || （m_pRightMostPoint->pSite->x == pThirdSite->x） && m_pRightMostPoint->pSite->y < pThirdSite->y）
	{
		m_pRightMostPoint	=	pThirdChain;
	}

	m_pFirstPoint		= pFirstChain;
	m_iCount = 3;//三个元素
}

//用两个点构造一个凸包
convex::convex（ site * pFirstSite   site * pSecondSite）
{
	point_chain * pFirstChain = new point_chain;
	point_chain * pSecondChain = new point_chain;

	if（

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      12570  2016-07-11 21:04  VoronoiDAC\ConvexHull.cpp

     文件       1450  2007-01-04 00:58  VoronoiDAC\ConvexHull.h

     文件       8284  2016-07-11 21:04  VoronoiDAC\Debug\BuildLog.htm

     文件      39755  2016-07-11 21:04  VoronoiDAC\Debug\ConvexHull.obj

     文件          0  2016-07-11 21:04  VoronoiDAC\Debug\ConvexHull.sbr

     文件      18640  2016-07-11 21:02  VoronoiDAC\Debug\inputdlg.obj

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\inputdlg.sbr

     文件      36108  2016-07-11 21:02  VoronoiDAC\Debug\MainFrm.obj

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\MainFrm.sbr

     文件         67  2016-07-11 21:04  VoronoiDAC\Debug\mt.dep

     文件      38698  2016-07-11 21:02  VoronoiDAC\Debug\Shape.obj

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\Shape.sbr

     文件     465407  2016-07-11 21:02  VoronoiDAC\Debug\StdAfx.obj

     文件    3356663  2016-07-11 21:02  VoronoiDAC\Debug\StdAfx.sbr

     文件     535552  2016-07-11 21:04  VoronoiDAC\Debug\vc90.idb

     文件    2158592  2016-07-11 21:04  VoronoiDAC\Debug\vc90.pdb

     文件     133781  2016-07-11 21:02  VoronoiDAC\Debug\Voronoi.obj

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\Voronoi.sbr

     文件    7728128  2016-07-11 21:04  VoronoiDAC\Debug\VoronoiDAC.bsc

     文件     149504  2016-07-11 21:04  VoronoiDAC\Debug\VoronoiDAC.exe

     文件        861  2016-07-11 21:04  VoronoiDAC\Debug\VoronoiDAC.exe.intermediate.manifest

     文件      36781  2016-07-11 21:02  VoronoiDAC\Debug\VoronoiDAC.obj

     文件   28508160  2016-07-11 21:02  VoronoiDAC\Debug\VoronoiDAC.pch

     文件    3697664  2016-07-11 21:04  VoronoiDAC\Debug\VoronoiDAC.pdb

     文件       8392  2016-07-11 21:04  VoronoiDAC\Debug\VoronoiDAC.res

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\VoronoiDAC.sbr

     文件      79144  2016-07-11 21:03  VoronoiDAC\Debug\VoronoiDACDoc.obj

     文件          0  2016-07-11 21:03  VoronoiDAC\Debug\VoronoiDACDoc.sbr

     文件     111782  2016-07-11 21:02  VoronoiDAC\Debug\VoronoiDACView.obj

     文件          0  2016-07-11 21:02  VoronoiDAC\Debug\VoronoiDACView.sbr

............此处省略54个文件信息