#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）為出發(fā)點(diǎn).
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）
{
	//為點(diǎn)分配空間
	m_pFirstPoint?=?（point_chain?*）malloc（iCount?*?sizeof（point_chain））;
	m_iCount?=?0;
	//初始化最右邊和最左邊的點(diǎn)為空
	m_pLeftMostPoint	=?NULL;
	m_pRightMostPoint	=?NULL;
}

//用三個(gè)點(diǎn)構(gòu)造一個(gè)凸包
convex::convex（?site?*?pFirstSite????site?*?pSecondSite???site?*?pThirdSite）
{
	//生成三個(gè)元素
	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?x?||（?pFirstSite->x?==?pSecondSite->x?&&?pFirstSite->y?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?x?||?（m_pRightMostPoint->pSite->x?==?pThirdSite->x）?&&?m_pRightMostPoint->pSite->y?y）
	{
		m_pRightMostPoint	=	pThirdChain;
	}

	m_pFirstPoint		=?pFirstChain;
	m_iCount?=?3;//三個(gè)元素
}

//用兩個(gè)點(diǎn)構(gòu)造一個(gè)凸包
convex::convex（?site?*?pFirstSite???site?*?pSecondSite）
{
	point_chain?*?pFirstChain?=?new?point_chain;
	point_chain?*?pSecondChain?=?new?point_chain;

	if（

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----

?????文件??????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個(gè)文件信息