两线段相交地相关算法.docVIP

两线段相交的相关算法 徐明龙2013-01-24 前提： 1)点的大小比较 a)设p1(x1,y1),p2(x2,y2) b)如果x1 x2 则p1 p2 c)如果x1 = x2 且 大小由y1与y2的关系决定 d)如果x1 x2 则 p1 p2 2)线的大小比较 a)设L1(p1,p2),L2(p3,p4) b)如果p1 p3 则L1L2 c)如果p1 = p3 则大小有p2,p4关系决定 d)如果p1 p3 则 L1L2 3)线的约束，线p1始终小于p2且p1 p2 算法： 获取线的直线斜率（X轴垂直时返回无穷大,X轴平行时为零。） (p2.y –p1.y)/(p2.x-p1.x) 判断点是否在线的直线上 a)2中特殊情况需要先考虑，一直垂直于X轴，和平行于X轴。 如果垂直于X轴，则p.x=p1.x即可。 如果平行于X轴，则p.y=p1.y即可。 b)其他情况根据点斜公式判断（p.y-p1.y）=斜率*(p.x-p1.x) 判断点是否在线段上. 先判断点是否在线段的直线上。 再判断点是否在线段的起始点与终止点之间。即（p1p2 且p在p1—p2的直线上，如果p=p1 且p =p2 则p必定在p1—p2的线段上。） 两点的向量公式： x=p1.x-p2.x y=p1.y-p2.y 向量的叉积（即向量相乘V1*V2）： v1*v2=v1.x*v2.y-v1.y*v2.x 获取两线段相交的类型。方法如下： 先判断是否端点相交的情况 端点相交有以下几种模式： p3在p1—p2的线段上，p4不在p1—p2的直线上 (图1) （图2） （图3） p3在p1—p2的线段上，p4在p1—p2的直线上 （图4） （图5） (图6) （图7） 其中图1、3、6的情况属于端点相交，图4、5、7属于部分重叠。图2属于一般相交。 p4在p1—p2的线段上，p3不在p1—p2的直线上（p4不可能与p1重叠） （图8） （图9） p4在p1—p2的线段上，p3在p1—p2的直线上（p3在p1—p2的直线必定在p1—p2的线段上） （图10） （图11） （图12） 其中图10的情况为两线段完全一致（即完全重叠），图9属于端点相交，图11与图12与图6图7一致，无需判断，图8为一般相交，图9为端点相交。 再根据判断p1,p2是否在p3—p4的线的两侧且p3,p4是否在p1—p2线的两侧，如果同时满足则两线相交。如图： 判断方法：使用向量方法，判断(V1*V3)*(V2*V3)是否为负，为负则p1,p2在p3—p4的两侧，同理再判断p3,p4是否在p1—p2的两侧。 获取两点相交的交点，只有一个交点的才返回，多个交点或无交点的返回null 代码如下: 线类代码 public class LineDraw implements ComparableLineDraw { private PointDraw p1; private PointDraw p2; public PointDraw getP1() { return p1; } public PointDraw getP2() { return p2; } /** * 根据点p1,p2构建一个线段，并始终保持坐标较小的点为起始坐标，较大的点为终止坐标。 * @param p1 * @param p2 * @throws Exception */ public LineDraw(PointDraw p1, PointDraw p2) throws Exception { super(); if(p1!=null p2!=null){ int c= pareTo(p2); if(c!=0){ if(c0){ //p1大于p2 this.p1 = p2; this.p2 = p1; }else{ this.p1 = p1; this.p2 = p2; } }else{ throw new Exception(线段起点不能与终点一致); } }else{ throw new NullPointerException(线段的点不能为空。); }