两线段相交的相关算法.doc

两线段相交的相关算法
徐明龙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 则L1<L2
c)如果p1 = p3 则大小有p2,p4关系决定
d)如果p1 > p3 则 L1>L2
3)线的约束，线p1始终小于p2且p1 <> p2

算法：
1） 获取线的直线斜率（X轴垂直时返回无穷大,X轴平行时为零。）
(p2.y –p1.y)/(p2.x-p1.x)
2） 判断点是否在线的直线上
a)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) 再判断点是否在线段的起始点与终止点之间。即（p1<p2 且p在p1—>p2的直线上，如果p>=p1 且p <=p2 则p必定在p1—p2的线段上。）

4） 两点的向量公式：
x=p1.x-p2.x
y=p1.y-p2.y
5） 向量的叉积（即向量相乘V1*V2）：
v1*v2=v1.x*v2.y-v1.y*v2.x
6） 获取两线段相交的类型。方法如下：
a) 先判断是否端点相交的情况
端点相交有以下几种模式：
（1） p3在p1—p2的线段上，p4不在p1—p2的直线上

(图1) （图2） （图3）
（2） p3在p1—p2的线段上，p4在p1—p2的直线上

（图4） （图5）

(图6) （图7）
其中图1、3、6的情况属于端点相交，图4、5、7属于部分重叠。图2属于一般相交。
（3） p4在p1—p2的线段上，p3不在p1—p2的直线上（p4不可能与p1重叠）

（图8） （图9）
（4） p4在p1—p2的线段上，p3在p1—p2的直线上（p3在p1—p2的直线必定在p1—p2的线段上）

（图10）

（图11） （图12）
其中图10的情况为两线段完全一致（即完全重叠），图9属于端点相交，图11与图12与图6图7一致，无需判断，图8为一般相交，图9为端点相交。

b) 再根据判断p1,p2是否在p3—p4的线的两侧且p3,p4是否在p1—p2线的两侧，如果同时满足则两线相交。如图：

c) 判断方法：使用向量方法，判断(V1*V3)*(V2*V3)是否为负，为负则p1,p2在p3—p4的两侧，同理再判断p3,p4是否在p1—p2的两侧。
7） 获取两点相交的交点，只有一个交点的才返回，多个交点或无交点的返回null

代码如下:

线类代码
public class LineDraw implements Comparable<LineDraw> {
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(c>0){ //p1大于p2
this.p1 = p2;
this.p2 = p1;

}else{
this.p1 = p1;
this.p2 = p2;
}

}else{
throw new Exception("线段起点不能与终点一致");
}
}else{
throw new NullPointerException("线段的点不能为空。");
}

}

/**
* 检查两线段是否只有唯一一次相交（即非重叠）
* @param l
* @return
*/
public boolean checkOnly(LineDraw l){

//即两线段相交（有重叠部分）且只有一个交点。
int k = this.getIntersect(l);
return k ==3 ||k==4 ;
}

/**
* 获取两线段是否相交类型,无相交返回-1。<br/>
* 即判断另一线段的两点是否在本线段两边，及本线段的两点同时在另一线段两边<br/>
* 完全重叠返回:1<br/>
* 部分重叠返回:2<br/>
* 仅端点相交返回:3<br/>
* 非端点相交返回:4<br/>
* @param l
* @return
*/
public int getIntersect(LineDraw l){
if(l==null){
throw new NullPointerException("参数不能为null");
}

int c = pareTo(l);//比较两线段的大小
if(c==0){ //两线完全重叠，返回true
return 1 ;
}

LineDraw l1; //较小的线段
LineDraw l2; //较大的线段
if(c<0){
l1 = this;
l2 = l;
}else{
l1=l;
l2 =this;
}
//判断L2的起点是否在l1的线段上，在则说明相交，再判断是否是部分重叠
if(l1.isOn(l2.p1)){
//判断L2的终点是否在l1的直线上，在则说明重叠，否则判断是端点相交还是非端点相交
if(l1.isOnStraightLine(l2.p2)){
if(l1.p2.equals(l2.p1)){ //终点等于起点时，则为端点相交
return 3;
}else{
return 2; //部分重叠（其实本次已包含全部重叠，但全部重叠前面已判断，所以本次仅有部分重叠）
}

}else{
if(l1.p1.equals(l2.p1) || l1.p2.equals(l2.p1)){ //某个端点相等，则为端点相交，否则为非端点相交
return 3;
}else{
return 4;
}
}

}
//判断L2的终点是否在l1的线段上
if(l1.isOn(l2.p2)){
//同样判断l2的起点是否在l1的直线上，在则说明重叠，否则判断端点相交还是非端点相交
if(l1.isOnStraightLine(l2.p1)){
return 2;
}else{
if(l1.p2.equals(l2.p2)){ //由于l2线段大于l1线段，因此l2的终点不可能等于l1的起点
return 3;
}else{
return 4;
}
}
}

//非端点相交
//获取三个向量直线一段分别到三个点的向量
PointDraw v1 =PointDraw.getVector(l1.p1, l1.p2);
PointDraw v2 =PointDraw.getVector(l1.p1, l2.p1);
PointDraw v3 =PointDraw.getVector(l1.p1, l2.p2);
//计算三个向量的叉积,
double k1 = PointDraw.mathCrossProduct(v2, v1) ;
k1 = k1 * PointDraw.mathCrossProduct(v3, v1);
//两点在线段的两边是，三向量的叉积为负（即两边向量的叉积正负不一致）

//获取另三个向量,另一条直线的一端分别到三个点的向量
v1=PointDraw.getVector(l2.p1, l2.p2);
v2 =PointDraw.getVector(l2.p1, l1.p1);
v3 =PointDraw.getVector(l2.p1, l1.p2);
double k2 = PointDraw.mathCrossProduct(v2, v1) ;
k2 = k2 * PointDraw.mathCrossProduct(v3, v1);

if( k1<=0&&k2<=0?true:false){
return 4;
}else{
return -1;
}

}

/**
* 获取两线段的交点,无交点则返回null<br/>
* （斜率公式计算:ax+bx+c=0）<br/>
* 仅端点相交，返回相交的端点,多个相交点返回null
* @param l1
* @param l2
* @return
*/
public static PointDraw getIntersectPoint(LineDraw l1,LineDraw l2){

//两线段只有一个交点
int i = l1.getIntersect(l2);
if(i==3){ //仅端点相交，返回相交的端点
if(l1.p1.equals(l2.p1) || l1.p1.equals(l2.p2)){
return l1.p1;
}
if(l1.p2.equals(l2.p1) || l1.p2.equals(l2.p2)){
return l1.p2;
}
}
if(i==4){
double a1,b1,c1,a2,b2,c2;
double[] par1 = l1.getParam();
double[] par2 = l2.getParam();
a1=par1[0];
b1=par1[1];
c1=par1[2];
a2=par2[0];
b2=par2[1];
c2=par2[2];
double m= a1*b2-a2*b1;
if(m==0){
return null ;
}
double x=(c2*b1-c1*b2)/m;
double y=(c1*a2-c2*a1)/m;
return new PointDraw(x,y);
}else{
return null;
}

}

/**
* 直线方程为ax+bx+c=0 ，计算直线方程的a,b,c
* @param l1
* @return
*/
public double[] getParam(){
double x1 = this.p1.getX();
double x2 = this.p2.getX();
double y1= this.p1.getY();
double y2= this.p2.getY();
double a1,b1,c1;
a1=y2-y1;
b1=x1-x2;
c1=(x2-x1)*y1-(y2-y1)*x1;
if(b1<0){
a1= a1*-1;
b1=b1*-1;
c1=c1*-1;
}else if(b1==0 && a1<0){
a1=a1*-1;
c1=c1*-1;
}
return new double[]{a1,b1,c1};

}
/**
* 如果本线段的起点小于o线段起点，则本线段小于o线段。<br/>
* 如果本线段的起点等于o线段起点，则大小关系由本线段的终点和o线段的终点决定。<br/>
* 否则本线段大于o线段。
*/
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(LineDraw o) {
// TODO Auto-generated method stub
if(o==null){
throw new NullPointerException();
}else{

int c = pareTo(o.p1);
if(c<0){ //本线段起点小于o线段起点，则本线段小于o线段
return -1;
}
if(c==0){ //起点相等，判断终点大小
return pareTo(o.p2);
}
return 1;

}

}

/**
* 判断点是否在线段的直线上
* @param p
* @return
*/
public boolean isOnStraightLine(PointDraw p){
//获取线段的斜率
double k = this.getGradient();
if(k==Double.POSITIVE_INFINITY || k==Double.NEGATIVE_INFINITY ){//线段垂直
if(this.p1.getX()==p.getX()){ //垂直时，X轴相等则在同一直线上
return true;
}else{
return false ;
}

}
if(k==0){//线段水平，Y轴相等则在同一直线上
if(this.p1.getY()==p.getY()){
return true ;
}else{
return false;
}

}

//有斜率的线段根据点斜公式判断
if(p.getY()-this.p1.getY()==k*(p.getX()-this.p1.getX())){ //点在直线上
return true ;
}else{
return false;
}
}
/**
* 判断点p是否在线段上。
* @param p
* @return
*/
public boolean isOn(PointDraw p){
//判断点是否在线段的直线上
if(this.isOnStraightLine(p)){
if(pareTo(p)<=0 && pareTo(p)>=0){ //点在线段终点与起点之间则在线段上
return true;
}else{
return false;
}
}else{
return false;
}

}

/**
* 获取线段的斜率。无斜率时,X轴垂直时返回无穷大,X轴平行时为零。
* @return
*/
public double getGradient(){

return (p2.getY()-p1.getY())/(p2.getX()-p1.getX());
}

/**
* 计算以线段l1构造的向量与l2线段构造的向量的叉积（外积）(由l1到l2线段）<br/>
* 外积为负则l1线段—>l2线段是顺时针转动<br/>
* 外积为证则为逆时针转动<br/>
* 0则二者平行（方向相同）
* @param l
* @return
*/
public static double mathCrossProduct(LineDraw l1,LineDraw l2){

return PointDraw.mathCrossProduct(
l1.getVector(),
l1.getVector());
}

/**
* 获取线段的向量
* @param l
* @return
*/
public PointDraw getVector(){
return PointDraw.getVector(this.p1, this.p2);
}
}

点类代码
public class PointDraw implements Comparable<PointDraw> {

private double x;
private double y;

/**
* 创建个默认坐标为0,0的点。
*/
public PointDraw(){
this(0.0,0.0);
}

public PointDraw(double x, double y) {
super();
this.x = x;
this.y = y;
}

public double getX() {
return x;
}

public void setX(double x) {
this.x = x;
}

public double getY() {
return y;
}

public void setY(double y) {
this.y = y;
}

/**
* 根据两点获取两点的向量坐标
* @param p1
* @param p2
* @return
*/
public static PointDraw getVector(PointDraw p1,PointDraw p2){
double x = p1.x-p2.x;
double y = p1.y-p2.y;
return new PointDraw(x,y);
}

/**
* 计算向量v1至v2的叉积（外积）
* @param v1
* @param v2
* @return
*/
public static double mathCrossProduct(PointDraw v1,PointDraw v2){
return v1.x*v2.y-v1.y*v2.x;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
return pareTo((PointDraw)obj)==0;
}

/**
* 如果本点的X轴坐标大于o点的X轴坐标，则本点大于o点。<br/>
* 如果本点的X轴坐标等于o点的X轴坐标，则大小关系由本点的Y轴坐标与o点的Y轴坐标的大小决定。<br/>
* 否则本点小于o点。
*/
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(PointDraw o) {
// TODO Auto-generated method stub
if(o==null){
throw new NullPointerException();
}else{
if (this.x > o.x){
return 1;
}else if(this.x==o.x && this.y >o.y){
return 1;
}else if(this.x== o.x && this.y == o.y){
return 0;
}else {
return -1;
}
}

}

}