点到多边形的切线(pointtangentpoly).txt

vc++中的点和直线之间的各种几何算法...对c++初学者或者ACM编程者有很大帮助

/* 求从多边形外一点p出发到一个简单多边形的切线,如果存在返回切点,其中rp点是右切点,lp是左切点 
注意：p点一定要在多边形外 
输入顶点序列是逆时针排列 
原 理:如果点在多边形内肯定无切线;凸多边形有唯一的两个切点,凹多边形就可能有多于两个的切点; 
如果polygon是凸多边形，切点只有两个只要找到就可以,可以化简此算法 
如果是凹多边形还有一种算法可以求解:先求凹多边形的凸包,然后求凸包的切线 
*/ 

/*讨论结果：P在多边形某边异侧时(即(!blp&&bln) || (blp&&!bln))，才进一步判断是否在先前切点上侧，是则替换原切点；否则继续。*/

void pointtangentpoly(int vcount,POINT polygon[],POINT p,POINT &rp,POINT &lp) 
{ 
	LINESEG ep,en; 
	bool blp,bln; 
	rp=polygon[0]; 
	lp=polygon[0]; 
	for(int i=1;i<vcount;i++) 
	{ 
		ep.s=polygon[(i+vcount-1)%vcount]; 
		ep.e=polygon[i]; 
		en.s=polygon[i]; 
		en.e=polygon[(i+1)%vcount]; 
		blp=multiply(ep.e,p,ep.s)>=0;                // p is to the left of pre edge 
		bln=multiply(en.e,p,en.s)>=0;                // p is to the left of next edge 
 	        if(!blp&&bln) 
		{ 
			if(multiply(polygon[i],rp,p)>0)           // polygon[i] is above rp 
				rp=polygon[i]; 
		} 
		if(blp&&!bln) 
		{ 
			if(multiply(lp,polygon[i],p)>0)           // polygon[i] is below lp 
				lp=polygon[i]; 
		} 
	} 
	return ; 
}