几种几何算法.docVIP

?计算几何常用算法介绍 1. 矢量减法设二维矢量 P = （x1,y1） ，Q = (x2,y2)则矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )显然有性质 P - Q = - ( Q - P )如不加说明，下面所有的点都看作矢量，两点的减法就是矢量相减；2.矢量叉积设矢量P = （x1,y1） ，Q = (x2,y2)则矢量叉积定义为：? P × Q = x1*y2 - x2*y1?? 得到的是一个标量显然有性质 P × Q = - ( Q × P )?? P × ( - Q ) = - ( P × Q )如不加说明，下面所有的点都看作矢量，点的乘法看作矢量叉积；叉乘的重要性质：??????? 若 P × Q? 0 ,? 则P 在Q的顺时针方向??????? 若 P × Q? 0 ,? 则P 在Q的逆时针方向??????? 若 P × Q? = 0 ,? 则P 与Q共线，但可能同向也可能反向3.判断点在线段上设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0? 且 Q 在以 P1，P2为对角顶点的矩形内4.判断两线段是否相交我们分两步确定两条线段是否相交：(1)．?? 快速排斥试验设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交；(2)．?? 跨立试验如果两线段相交，则两线段必然相互跨立对方，如图1所示。在图1中，P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 )? *? ( P2 - Q1 ) × ( Q2 - Q1 )? ? 0上式可改写成?? ( P1 - Q1 ) × ( Q2 - Q1 )? *? ( Q2 - Q1 ) × ( P2 - Q1 )? ? 0当( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×( P2 - Q1 )? = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 )? *? ( Q2 - Q1 ) × ( P2 - Q1 )? ≥? 0同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 )? *? ( P2 - P1 ) × ( Q2 - P1 )? ≥? 0至此已经完全解决判断线段是否相交的问题。5.判断线段和直线是否相交如果线段 P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：( P1 - Q1 ) × ( Q2 - Q1 )? *? ( Q2 - Q1 ) × ( P2 - Q1 )? ≥? 06.判断矩形是否包含点只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。6.判断线段、折线、多边形是否在矩形中因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。7.判断矩形是否在矩形中只要比较左右边界和上下边界就可以了。8.判断圆是否在矩形中圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。9.判断点是否在多边形中以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个，有些情况下交点不应被计算（自己画个图就明白了）；如果L和多边形的一条边重合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：1. count 0;2. 以P为端点，作从右向左的射线L;3. for 多边形的每条边s4.?? do if P在边s上5.?????????