Wednesday, July 14, 2010

Intersection of two line segments

The JAVA code below finds intersection of two line segments (x00,y00)-(x01,y01) and (x10,y10)-(x11,y11)

It returns float array of the coordinates of the intersection, or null if there is no intersection,


public static float[] intersection(float x00, float y00, float x01, float y01,
float x10, float y10, float x11, float y11) {

float ABx=x01-x00, ABy=y01-y00;
float CDx=x11-x10, CDy=y11-y10;
float BCx=x10-x01, BCy=y10-y01;
float BDx=x11-x01, BDy=y11-y01;
float DAx=x00-x11, DAy=y00-y11;
float DBx=x01-x11, DBy=y01-y11;

// check if the line segments are not crossing
if((ABx*BCy-ABy*BCx)*(ABx*BDy-ABy*BDx)>=0) return null;
if((CDx*DAy-CDy*DAx)*(CDx*DBy-CDy*DBx)>=0) return null;
float d=(x00-x01)*(y10-y11)-(y00-y01)*(x10-x11);
if(d==0) return null;

float x=((x00*y01-y00*x01)*(x10-x11)-(x00-x01)*(x10*y11-y10*x11))/d;
float y=((x00*y01-y00*x01)*(y10-y11)-(y00-y01)*(x10*y11-y10*x11))/d;
float result[]={x,y};
return result;
}

No comments:

Post a Comment