www.pudn.com > VoronoiDAC.rar > ConvexHull.cpp, change:2007-01-09,size:12572b

#include "StdAfx.h" 
#include "iostream.h" 
#include "stdio.h" 
#include "conio.h" 
#include "malloc.h" 
#include "ConvexHull.h" 
 
 
//struct edge; 
//struct site; 
//struct vertex; 
//struct face ; 
 
 
 
 
//判断(x3,y3)是不是在(x1,y1)(x2,y2)连线的左边.以(x1,y1)为出发点. 
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->x,pFirstSite->y,pSecondSite->x,pSecondSite->y,pThirdSite->x,pThirdSite->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(pFirstSite->x == pSecondSite->x && pFirstSite->y == pSecondSite->y) 
	{ 
		printf("wrong input ,the two Sites are the same.\n\n"); 
		return; 
 
	} 
 
	//选取位置在左边的点作为第一个点,如果x坐标一样,选择坐标靠上的点为第一个点. 
	if  ( (pFirstSite->x  pSecondSite->x)		|| 
		  (pFirstSite->x == pSecondSite->x && pFirstSite->y  pSecondSite->y) 
		) 
	{ 
		pFirstChain->pSite		= pFirstSite; 
		pSecondChain->pSite		= pSecondSite; 
	} 
	else 
	{ 
		pFirstChain->pSite		= pSecondSite; 
		pSecondChain->pSite		= pFirstSite; 
	}	 
	 
	//形成链表 
	pFirstChain->next		= pSecondChain; 
	pFirstChain->previous	= pSecondChain; 
 
	pSecondChain->next		= pFirstChain; 
	pSecondChain->previous	= pFirstChain; 
 
	m_pFirstPoint		= pFirstChain; 
	m_pLeftMostPoint	= pFirstChain; 
	m_pRightMostPoint	= pSecondChain; 
 
	m_iCount = 2;//两个元素 
 
 
} 
//返回点数 
int convex::GetCount() 
{ 
	return m_iCount;	 
} 
 
void convex::GetFirstPoint(point_chain * * pstruFirstPoint) 
{ 
	* pstruFirstPoint = m_pFirstPoint; 
} 
 
void convex::GetLeftMostPoint(point_chain * * pLeftMostPoint) 
{ 
	* pLeftMostPoint = m_pLeftMostPoint; 
} 
 
void convex::GetRightMostPoint(point_chain * * pRightMostPoint) 
{ 
	* pRightMostPoint = m_pRightMostPoint; 
} 
 
void convex::GetFourMergePoint(const convex * pRightConvex , point_chain * * ppLeftUpSite , point_chain * * ppLeftDownSite , point_chain  * * ppRightUpSite , point_chain * * ppRightDownSite) 
{ 
	point_chain * pLeftUpSite		= new point_chain; 
	point_chain * pLeftDownSite		= new point_chain; 
	point_chain * pRightDownSite	= new point_chain; 
	point_chain * pRightUpSite		= new point_chain; 
	 
	//初值 
	 pLeftUpSite			= m_pRightMostPoint; 
	 pLeftDownSite			= m_pRightMostPoint; 
	 pRightUpSite			= pRightConvex->m_pLeftMostPoint; 
	 pRightDownSite			= pRightConvex->m_pLeftMostPoint; 
	 
	 
	bool bBreakTag          =	true; 
	bool bInsideBreakTag1	=	true; 
	bool bInsideBreakTag2	=	true; 
 
	//上连线 
	while(bBreakTag) 
	{ 
		while(bInsideBreakTag1) 
		{ 
			int j =	 ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y,pLeftUpSite->pSite->x,pLeftUpSite->pSite->y,pLeftUpSite->next->pSite->x,pLeftUpSite->next->pSite->y); 
			//往上移动左边的点,知道左边的闭包已经在上连线的(左边),也就是下面 
			if ((  ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y,pLeftUpSite->pSite->x,pLeftUpSite->pSite->y,pLeftUpSite->next->pSite->x,pLeftUpSite->next->pSite->y) != 1)  
				|| (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y,pLeftUpSite->pSite->x,pLeftUpSite->pSite->y,pLeftUpSite->previous->pSite->x,pLeftUpSite->previous->pSite->y) != 1) 
			   ) 
				 
			{ 
					pLeftUpSite = pLeftUpSite->next; 
			} 
			//满足条件,不再移动 
			else 
			{ 
				bInsideBreakTag1 = false; 
			} 
		}//while(bInsideBreakTag1) 
		 
		while(bInsideBreakTag2) 
		{ 
			//往上移动右边的点,知道右边的闭包都在上连线的下面 
			if (  (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y, pLeftUpSite->pSite->x, pLeftUpSite->pSite->y,pRightUpSite->next->pSite->x, pRightUpSite->next->pSite->y)!=1) 
				||(ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y, pLeftUpSite->pSite->x, pLeftUpSite->pSite->y,pRightUpSite->previous->pSite->x, pRightUpSite->previous->pSite->y)!=1) 
			   ) 
			{ 
				pRightUpSite = pRightUpSite->previous; 
			} 
 
			else 
			{ 
				bInsideBreakTag2 = false; 
			} 
			 
		}//while(bInsideBreakTag2) 
 
		//是否已经满足了两个闭包都在上连线的下面?不是的话就再循环 
		if(    (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y,pLeftUpSite->pSite->x,pLeftUpSite->pSite->y,pLeftUpSite->next->pSite->x,pLeftUpSite->next->pSite->y) != 1)  
			|| (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y,pLeftUpSite->pSite->x,pLeftUpSite->pSite->y,pLeftUpSite->previous->pSite->x,pLeftUpSite->previous->pSite->y) != 1) 
			|| (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y, pLeftUpSite->pSite->x, pLeftUpSite->pSite->y,pRightUpSite->next->pSite->x, pRightUpSite->next->pSite->y)!=1) 
			|| (ToLeft(pRightUpSite->pSite->x, pRightUpSite->pSite->y, pLeftUpSite->pSite->x, pLeftUpSite->pSite->y,pRightUpSite->previous->pSite->x, pRightUpSite->previous->pSite->y)!=1) 
		  ) 
		{ 
			bInsideBreakTag1 = true; 
			bInsideBreakTag2 = true; 
		} 
		//已经找到了上连线. 
		else	 
		{ 
			bBreakTag = false; 
		} 
 
	}//while(bBreakTag) 
 
 
 
 
	bBreakTag =true; 
	//下连线 
	while(bBreakTag) 
	{ 
		while(bInsideBreakTag1) 
		{ 
			//往下移动左边的点,知道左边的闭包已经在上连线的(左边),也就是下面 
			if ((  ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y,pRightDownSite->pSite->x,pRightDownSite->pSite->y,pLeftDownSite->next->pSite->x,pLeftDownSite->next->pSite->y) != 1)  
				|| (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y,pRightDownSite->pSite->x,pRightDownSite->pSite->y,pLeftDownSite->previous->pSite->x,pLeftDownSite->previous->pSite->y) != 1) 
			   ) 
				 
			{ 
					pLeftDownSite = pLeftDownSite->previous; 
			} 
			//满足条件,不再移动 
			else 
			{ 
				bInsideBreakTag1 = false; 
			} 
		}//while(bInsideBreakTag1) 
		 
		while(bInsideBreakTag2) 
		{ 
			//往上移动右边的点,知道右边的闭包都在上连线的下面 
			if (  (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y, pRightDownSite->pSite->x, pRightDownSite->pSite->y,pRightDownSite->next->pSite->x, pRightDownSite->next->pSite->y)!=1) 
				||(ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y, pRightDownSite->pSite->x, pRightDownSite->pSite->y,pRightDownSite->previous->pSite->x, pRightDownSite->previous->pSite->y)!=1) 
			   ) 
			{ 
				pRightDownSite = pRightDownSite->next; 
			} 
 
			else 
			{ 
				bInsideBreakTag2 = false; 
			} 
			 
		}//while(bInsideBreakTag2) 
 
		//是否已经满足了两个闭包都在下连线的上面?不是的话就再循环 
		if(    (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y,pRightDownSite->pSite->x, pRightDownSite->pSite->y,pLeftDownSite->next->pSite->x,pLeftDownSite->next->pSite->y) != 1)  
			|| (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y,pRightDownSite->pSite->x, pRightDownSite->pSite->y,pLeftDownSite->previous->pSite->x,pLeftDownSite->previous->pSite->y) != 1) 
			|| (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y, pRightDownSite->pSite->x, pRightDownSite->pSite->y,pRightDownSite->next->pSite->x, pRightDownSite->next->pSite->y)!=1) 
			|| (ToLeft(pLeftDownSite->pSite->x, pLeftDownSite->pSite->y, pRightDownSite->pSite->x, pRightDownSite->pSite->y,pRightDownSite->previous->pSite->x, pRightDownSite->previous->pSite->y)!=1) 
		  ) 
		{ 
			bInsideBreakTag1 = true; 
			bInsideBreakTag2 = true; 
		} 
		//已经找到了上连线. 
		else	 
		{ 
			bBreakTag = false; 
			* ppLeftDownSite = pLeftDownSite; 
			* ppLeftUpSite	 = pLeftUpSite; 
			* ppRightUpSite	 = pRightUpSite; 
			* ppRightDownSite= pRightDownSite; 
		} 
 
	}//while(bBreakTag) 
 
} 
 
// NewConvex 开始为空的,立面的元素都是默认值 
void convex::MergeWithRightConvex(convex * pRightConvex ,convex * NewConvex) 
{ 
	point_chain * pLeftUpPoint ; 
	point_chain * pLeftDownPoint; 
	point_chain * pRightDownPoint; 
	point_chain * pRightUpPoint; 
	GetFourMergePoint(pRightConvex,&pLeftUpPoint,&pLeftDownPoint,&pRightUpPoint,&pRightDownPoint); 
 
	point_chain * ptmpChain; 
/*	point_chain * ptmpToBeDeletedChain; 
 
	ptmpChain = pLeftUpPoint; 
	while (ptmpChain!=pLeftDownPoint) 
	{ 
		ptmpToBeDeletedChain = ptmpChain->next; 
		free(ptmpToBeDeletedChain); 
	} 
 
	ptmpChain = pRightDownPoint; 
	while (ptmpChain!=pRightUpPoint) 
	{ 
		ptmpToBeDeletedChain = ptmpChain->next; 
		free(ptmpToBeDeletedChain); 
	} 
 
*/ 
	pLeftUpPoint->next			=	pRightUpPoint; 
	pRightUpPoint->previous		=	pLeftUpPoint; 
 
	pRightDownPoint->next		=	pLeftDownPoint; 
	pLeftDownPoint->previous	=	pRightDownPoint; 
	 
	 
	int iNewCount = 0; 
	ptmpChain = m_pFirstPoint->next; 
	iNewCount = 1;//已经有一个确定的元素,当前指向的元素还没有检验是不是重复的. 
	while(ptmpChain!=m_pFirstPoint) 
	{ 
		iNewCount++; 
		ptmpChain = ptmpChain->next; 
		 
	} 
	NewConvex->m_iCount = iNewCount; 
	NewConvex->m_pRightMostPoint	=	pRightConvex->m_pRightMostPoint; 
	NewConvex->m_pLeftMostPoint		=	m_pLeftMostPoint; 
	NewConvex->SetFirstPoint(m_pFirstPoint); 
 
 
} 
 
void convex::PrintAllSites() 
{ 
	point_chain * tmpPointChain = m_pFirstPoint; 
	for( int i=0; i<m_iCount; i++) 
	{ 
		printf("X:%f , Y:%f\n" ,tmpPointChain->pSite->x,tmpPointChain->pSite->y);	 
		tmpPointChain = tmpPointChain->next; 
	} 
	printf("\n"); 
} 
 
void convex::SetFirstPoint(point_chain * pFirstPoint) 
{ 
 
	m_pFirstPoint = pFirstPoint; 
} 
 
 
/* 
void main() 
{ 
	site * psite1 = new site; 
	site * psite2 = new site; 
	site * psite3 = new site; 
	site * psite4 = new site; 
	site * psite5 = new site; 
	site * psite6 = new site; 
 
 
	psite1->id =1; 
	psite1->x = 11; 
	psite1->y = 13; 
	//psite1->type =  
 
	psite2->id =2; 
	psite2->x = 14; 
	psite2->y = 33; 
 
	psite3->id =3; 
	psite3->x = 17; 
	psite3->y = 21; 
 
	psite4->id =4; 
	psite4->x = 21; 
	psite4->y = 17; 
 
	psite5->id =5; 
	psite5->x = 31; 
	psite5->y = 23; 
 
	psite6->id =6; 
	psite6->x = 33; 
	psite6->y = 15; 
 
 
	convex aConvex = convex(psite1,psite2,psite3); 
	convex bConvex = convex(psite4,psite5,psite6); 
	convex cConvex = convex(); 
 
	point_chain * pChain1 = new point_chain; 
	point_chain * pChain2 = new point_chain; 
	point_chain * pChain3 = new point_chain; 
	point_chain * pChain4 = new point_chain; 
 
	//aConvex.GetFourMergePoint(&bConvex, &pChain1, &pChain2 , &pChain3 , &pChain4); 
 
	aConvex.MergeWithRightConvex(&bConvex ,&cConvex); 
	aConvex.PrintAllSites(); 
	cConvex.PrintAllSites(); 
 
	 
 
 
} 
*/