两线段相交的相关算法

《两线段相交的相关算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、两线段相交的相关算法徐明龙2013-01-24前提：1)点的大小比较a)设p1(x1,y1),p2(x2,y2)b)如果x1>x2则p1>p2c)如果x1=x2且大小由y1与y2的关系决定d)如果x1p3则L1>L23)线的约束，线p1始终小于p2且p1<>p2算法：1）获取线的直线斜率（X轴垂直时返回无穷大,X轴平行时为零。）(p2.y–p1.y)/(p2.x-p1.x)2）判断点是否在线的直线上a)

2、2中特殊情况需要先考虑，一直垂直于X轴，和平行于X轴。如果垂直于X轴，则p.x=p1.x即可。如果平行于X轴，则p.y=p1.y即可。b)其他情况根据点斜公式判断（p.y-p1.y）=斜率*(p.x-p1.x)3）判断点是否在线段上.a)先判断点是否在线段的直线上。b)再判断点是否在线段的起始点与终止点之间。即（p1p2的直线上，如果p>=p1且p<=p2则p必定在p1—p2的线段上。）4）两点的向量公式：x=p1.x-p2.xy=p1.y-p2.y5）向量的叉积（即向量相乘V1*V2）：v1*v2=v1.x*v2.y-v1.y*v2.x6）获取

3、两线段相交的类型。方法如下：a)先判断是否端点相交的情况端点相交有以下几种模式：（1）p3在p1—p2的线段上，p4不在p1—p2的直线上(图1)（图2）（图3）（1）p3在p1—p2的线段上，p4在p1—p2的直线上（图4）（图5）(图6)（图7）其中图1、3、6的情况属于端点相交，图4、5、7属于部分重叠。图2属于一般相交。（2）p4在p1—p2的线段上，p3不在p1—p2的直线上（p4不可能与p1重叠）（图8）（图9）（3）p4在p1—p2的线段上，p3在p1—p2的直线上（p3在p1—p2的直线必定在p1—p2的线段上）（图10）（图11）（图12）其中图1

4、0的情况为两线段完全一致（即完全重叠），图9属于端点相交，图11与图12与图6图7一致，无需判断，图8为一般相交，图9为端点相交。a)再根据判断p1,p2是否在p3—p4的线的两侧且p3,p4是否在p1—p2线的两侧，如果同时满足则两线相交。如图：b)判断方法：使用向量方法，判断(V1*V3)*(V2*V3)是否为负，为负则p1,p2在p3—p4的两侧，同理再判断p3,p4是否在p1—p2的两侧。2）获取两点相交的交点，只有一个交点的才返回，多个交点或无交点的返回null代码如下:线类代码publicclassLineDrawimplementsComparable

5、{privatePointDrawp1;privatePointDrawp2;publicPointDrawgetP1(){returnp1;}publicPointDrawgetP2(){returnp2;}/***根据点p1,p2构建一个线段，并始终保持坐标较小的点为起始坐标，较大的点为终止坐标。*@paramp1*@paramp2*@throwsException*/publicLineDraw(PointDrawp1,PointDrawp2)throwsException{super();if(p1!=null&&p2!=null){in

6、tc=p1.compareTo(p2);if(c!=0){if(c>0){//p1大于p2this.p1=p2;this.p2=p1;}else{this.p1=p1;this.p2=p2;}}else{thrownewException("线段起点不能与终点一致");}}else{thrownewNullPointerException("线段的点不能为空。");}}/***检查两线段是否只有唯一一次相交（即非重叠）*@paraml*@return*/publicbooleancheckOnly(LineDrawl){//即两线段相交（有重叠部分）且只有一个交点。

7、intk=this.getIntersect(l);returnk==3

8、

9、k==4;}/***获取两线段是否相交类型,无相交返回-1。
*即判断另一线段的两点是否在本线段两边，及本线段的两点同时在另一线段两边
*完全重叠返回:1
*部分重叠返回:2
*仅端点相交返回:3
*非端点相交返回:4
*@paraml*@return*/publicintgetIntersect(LineDrawl){if(l==null){thrownewNullPointerException("参数不能为null");}intc=t