# algorithm for calculation of point of intersection of two lines

6 replies [Last post]
Anonymous

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

Rolf Gabler-Mieck

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

>Does anybody have an algorithm for calculation of point of intersection of two lines(3d)?
>---
>[Message sent by forum member 'Pawlik_Krasnodar' (Pawlik_Krasnodar)]
>
>
>---------------------------------------------------------------------
>To unsubscribe, e-mail: interest-unsubscribe@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

Anonymous

thank you

Anonymous

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;

}

Matthew Hilliard

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

Anonymous

thank you very much

Rolf Gabler-Mieck

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

>Does anybody have an algorithm for calculation of point of intersection of two lines(3d)?
>---
>[Message sent by forum member 'Pawlik_Krasnodar' (Pawlik_Krasnodar)]
>
>
>---------------------------------------------------------------------
>To unsubscribe, e-mail: interest-unsubscribe@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