# algorithm for calculation of point of intersection of two lines

Does anybody have an algorithm for calculation of point of intersection of two lines(3d)?

thank you

Iâ€™m trying now to write the algorithm for calculation of point of intersection of two lines. The lines always have got the point of intersection But the algorithm doesnâ€™t work. Can anybody tell me why it doesnâ€™t work?

many thanks

private PointSAT intersection(PointSAT point11, PointSAT point12, PointSAT point21, PointSAT point22)

{

PointSAT point = new PointSAT(-1,0,0,0);

//line 1

double x1 = point11.getX();

double y1 = point11.getY();

double z1 = point11.getZ();

double x2 = point12.getX();

double y2 = point12.getY();

double z2 = point12.getZ();

//line 2

double x3 = point21.getX();

double y3 = point21.getY();

double z3 = point21.getZ();

double x4 = point22.getX();

double y4 = point22.getY();

double z4 = point22.getZ();

double x=0;

double y=0;

double z=0;

int s=0;

double t=0;

double t1=0;

double t2=0;

// If line 1 is parallel to line 2 in Z â€“ dimension

double D =(y2-y1)*(x3-x4)-(y3-z4)*(x2-x1);

double D1=(y2-y1)*(x3-x1)-(y3-z1)*(x2-x1);

double D2=(y3-y1)*(x3-x4)-(y3-z4)*(x3-x1);

if(D!=0)

{

t1=D1/D;

t2=D2/D;

if( (t1<=1)&(t1>=0) & (t2>=0)&(t2<=1) )

{

x=x1+(x2-x1)*t2;

y=y1+(y2-y1)*t2;

z=z1+(z2-z1)*t2;

point.setX(x);

point.setY(y);

point.setZ(z);

return point;

}

}

// // If line 1 is parallel to line 2 in y â€“ dimension

D =(z2-z1)*(x3-x4)-(z3-z4)*(x2-x1);

D1=(z2-z1)*(x3-x1)-(z3-z1)*(x2-x1);

D2=(z3-z1)*(x3-x4)-(z3-z4)*(x3-x1);

if(D!=0)

{

t1=D1/D;

t2=D2/D;

x=x1+(x2-x1)*t2;

y=y1+(y2-y1)*t2;

z=z1+(z2-z1)*t2;

point.setX(x);

point.setY(y);

point.setZ(z);

return point;

}

// If line 1 is parallel to line 2 in x â€“ dimension

D =(y2-y1)*(z3-z4)-(y3-z4)*(z2-z1);

D1=(y2-y1)*(z3-z1)-(y3-z1)*(z2-z1);

D2=(y3-y1)*(z3-z4)-(y3-z4)*(z3-z1);

if(D!=0)

{

t1=D1/D;

t2=D2/D;

if( (t1<=1)&(t1>=0) & (t2>=0)&(t2<=1) )

{

x=x1+(x2-x1)*t2;

y=y1+(y2-y1)*t2;

z=z1+(z2-z1)*t2;

point.setX(x);

point.setY(y);

point.setZ(z);

return point;

}

}

return point;

}

Hey.

I could spend all day trying to break down this algorithm in an effort to

see where it doesn't work (it seems to be doing some kind of projection or

perhaps a more optimal but incorrect version of what I'm about to

present?), but its just not clear enough for me to try and figure out.

For the following algorithm, you'll need to devise a 3x3

reduced-row-echelon-form matrix-solving method, but the technique is

simple, pretty quick and well-understood so that shouldn't be too difficult.

I've used the keyword FAIL to express no intersection exists, you can

implement a failure however you like. You start by creating segments v1 (

= p12 - p11 ) and v2 ( = p22 - p21 ) and then store their respective

lengths L1 ( = ||v1|| ) and L2 ( = ||v2|| ) and finally use their unit

equivalents u1 ( = v1 / L1 ) and u2 ( = v2 / L2 ) to later detect any

potential collision.

You may want to do some basic tests like L1 and L2 != 0.

You want to calculate the intersection point Pint such that

Pint = p11 + (M)u1 and also Pint = p21 + (N)u2.

Then create a matrix to solve for constants M and N based on the idea:

(M)u1 - (N)u2 = p21 -p11

Create the matrix to solve:

| u1[x] u2[x] p21[x]-p11[x] |

| u1[y] u2[y] p21[y]-p11[y] |

| u1[z] u2[z] p21[z]-p11[z] |

Reduce the matrix to:

| 1 0 M |

| 0 1 -N |

| 0 0 0 |

If the bottom row comes out to something other than 0, 0, 0--you have

parallel segments.

Test if they are colinear and overlap as follows:

IF ( parallel )

THEN

try N = ||(p11 - p21)||,

IF ( p11 != p21 + (N)u2 AND p11 != p21 + (-N)u2 )

THEN

FAIL (the segments are not colinear and cannot overlap).

// END IF

IF ( N <= L2 )

THEN

return p11.

// END IF

If they are collinear but N is greater than L2, try these 2 tests:

try N = ||(p12 - p21)||,

IF ( p12 == p21 + (N)u2 AND N <= L2 )

THEN

return p12.

ELSE

try M = ||(p22 - p11)||,

IF ( p22 == p11 + (M)u1 AND M <= L1 )

THEN

return p22.

// END IF

// END IF

FAIL (colinear segments, but no overlap)

// END IF

Now, assuming the segment are NOT parallel, with the top left entry = 1,

the top-right entry will give you the value of M.

Likewise, with the center entry = 1, the center-right entry will give you -N.

Now you test the values of M and N to see if they fall in the domain of

"between the points".

IF ( M < 0 OR M > L1 )

THEN

FAIL (the intersection does not occur between p11 and p12).

IF ( N < 0 OR N > L2 )

THEN

FAIL (the intersection does not occur between p21 and p22).

Assuming both M and N pass these last tests, you can return a value for

Pint using either of the N or M equations: Pint = (p11 + (M)u1 or p21 + (N)u2)

---------------------------------------------------------------------

To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

For additional commands, e-mail: interest-help@java3d.dev.java.net

thank you very much

built the linear function of each line f+ g,

like :

f(x)=a1x+a0 using start & endpoints to define/determine the function

the set f=g and calculate x, get y by using f(xs=...) and proove it by

using

g(xs=...) then you got the intersection point

best regards

rolf

java3d-interest@javadesktop.org schrieb:

>Does anybody have an algorithm for calculation of point of intersection of two lines(3d)?

>---

>[Message sent by forum member 'Pawlik_Krasnodar' (Pawlik_Krasnodar)]

>

>http://www.javadesktop.org/forums/thread.jspa?messageID=54024팈

>

>---------------------------------------------------------------------

>To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

>For additional commands, e-mail: interest-help@java3d.dev.java.net

>

>

>

>

>

--

Rolf Gabler-Mieck

c/o

LGI-Geographisches Institut der CAU-Kiel

Ludewig-Meyen Str. 14

24098 Kiel

Tel: +49 431-880.2955

FAX: +49 431-880.4658

e-mail: gabler.mieck@geographie.uni-kiel.de

---------------------------------------------------------------------

To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

For additional commands, e-mail: interest-help@java3d.dev.java.net

sorry loosing the 3d-contex...

you have better to use the vectorial form..

r1,1 + LAMNDA1*v1= r1,2+LAMNDA2*v2

x1 xv1

x2 xv2

y1 +LAMNDA1* yv1 = y2 +LAMNDA2 * yv2

z1 zv1

z2 zv2

where v1 is a given vector, describing line1 - and r1,1 the

directionvector of poit 1 from line1

where v2 is a given vector, describing line2 - and r1,2 the

directionvector of poit 1 from line2

only if LAMNDA1 &2 are consistent calculateable there is an

intersection, otherwise not

regards

rolf

java3d-interest@javadesktop.org schrieb:

>Does anybody have an algorithm for calculation of point of intersection of two lines(3d)?

>---

>[Message sent by forum member 'Pawlik_Krasnodar' (Pawlik_Krasnodar)]

>

>http://www.javadesktop.org/forums/thread.jspa?messageID=54024팈

>

>---------------------------------------------------------------------

>To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

>For additional commands, e-mail: interest-help@java3d.dev.java.net

>

>

>

>

>

--

Rolf Gabler-Mieck

c/o

LGI-Geographisches Institut der CAU-Kiel

Ludewig-Meyen Str. 14

24098 Kiel

Tel: +49 431-880.2955

FAX: +49 431-880.4658

e-mail: gabler.mieck@geographie.uni-kiel.de

---------------------------------------------------------------------

To unsubscribe, e-mail: interest-unsubscribe@java3d.dev.java.net

For additional commands, e-mail: interest-help@java3d.dev.java.net