Please help me!
I have two line/ray
(A line/ray means 1point+1vector OR 2point)
I would like to calculate the intersection between the two line/ray.
Has anybody got a function what do this?
Thanx.
HunSoul
In 2D or 3D? In 3D two lines don’t usually intersect, so the best you can do is find the closest distance between them.
Originally posted by Rob:
In 2D or 3D? In 3D two lines don’t usually intersect, so the best you can do is find the closest distance between them.
Yes, i know…so i need a function what calc the closest distance between them - in 3D (sorry for my lack of precision)
Plese HELP me! - this is very urgent for me
There is a really good source for algorithms like this at:
http://www.magic-software.com/MgcDistance3D.html
They have algorithms for what you want there. Incidentally, the book is pretty good too.
– Zeno
Originally posted by hunsoul:
[b]Please help me!
I have two line/ray
(A line/ray means 1point+1vector OR 2point)
I would like to calculate the intersection between the two line/ray.
Has anybody got a function what do this?
Thanx.
HunSoul[/b]
Well this is a problem of simple(?) vector mathmatics.
First you need both lines in the form
line one:
a=p1 + t * d1
a,p1,d1 … vectors
t … scalar
a… set point of point on the ray
p1… initital point
d1… direction of the line
t… scalare which moves fromm negative infinity to positive infinity
in componemt writing it would be
(p11) (d11)
a=(p12) + t * (d12)
(p13) (d13)
line 2 (same as line one)
b=p2 + u * d2
(p21) (d21)
b=(p22) + u * (d22)
(p23) (d23)
Two lines interescting yields in following possibilities
-
the two lines lie in the same plane but arent identical (they are parallel)
condition:
d1 | | d2
p1 not on b or p2 not on a -
the two lines are identical
condition:
d1 | | d2
p1 lies on b or p2 lies on a
3)they intersect on one point
condition :
a=b woth one solution of this equotaion
4)they dont fullfill the other possibities
they have a point of minimal distance
then you have to set both lines equal
a=b
p1+ t * d1 = p2 + u * d2
then you get a linear equotaion system with 3 equotations and 2 unkonw variables
I p11 + t* d11 = p21 + u * d21
II p12 + t* d12 = p22 + u * d22
III p13 + t* d13 = p23 + u * d23
t and u are the variables
try to eliminate t and you will get u(or vice versa)
if possibility 3) you will get one solution
(u or t) uses this to calculate the points coordinates by setting t in a ot u in b
if possibility 1 or 4) you dont get a solution
to determine 1) or 4)
check if d1 | | d2 , if so you have 1) otherwise 4)
if possibility 2) you get a solution of true for all t, u for all numbers
now you have an idea how you can do it
hope it isnt to mathematical for you
the problem might be to solve the linear equotation system but with some if/else and some + / * - it would be possible
Bye
THANK YOU Zeno!
THANK YOU VERY MUCH ScottManDeath!
Now, i can solve the problem!
[This message has been edited by hunsoul (edited 03-30-2001).]
That got me satisfied but to get the ultimate kick 
i looked in my 2 years old mathmatics execise book from school and i found following…
to get the distance of two non intersecting non parallel lines you can do the following
just remind
a = p1 + t * d1
b= p2 + u * d2
you can create two planes being parallel, each containing one line by doing this:
e1 = p1 + f * d1 +g * d2
e2 = p2 + h * d1 +i* d2
e1,e2 two planes
p1,p2 points of the two lines
d1,d2 directions of the two lines
f,g,h,i scalarsc from -INF to + INF to determine all points on each plane.
but what did we there ?:
(pick one plane , I took e1)
we created a plane (e1)that contains line a
then we can calculate the distance of point p2(on b) to this plane. this is equal to the distance of the two lines because a element of e1 and b elemnt of e2.
we have to translate e1 in the “Hessesche Normalform” (in german mathmatic lesson,I don’t know if you use this expression but you should see it)
you need:
n …the normal vector of e1 (by crossproducting d1 and d2)
x0 …one point on e1 p1
you have to normalize the normal (game of words by dividing it by its length
n = n * 1/|n|
each point x on this plane can be calculated in this way(hessesche normalform)
(x-x0)* (n * 1/|n|) = 0 [dot product]
to get the distance d of p2 to e1 you use
d = (p2 -p1)( n 1/|n|)
perhaps you should take |d| otherwise you get the orientated distance
if line a | | line b the problem is calculating the distance from
point to line as done in this way:
distance line point:
l = p0 + t * d
p … point
create a plane e orthogonal to line l and containing p:
(hessesche normalform)
(x-p)d(1/|d1|)=0
then you intersect line l with this plane getting point s
just “dot” the plane(hessesche normalform) out and you get
Ax +By +C*z +D =0
then set line l in this equotation
A(p01 + t d1)+B(p02 + td2)+C(p03+ t*d3)+D=0
then you get t, use this to calc point s by placing t in l.
then you calc the size of vector (ps)
and you got it
to calc distance line line just calc distance point p2 to line a …
I hope it’s correct. ( if you hav a working version of your code please post it or mail it
[This message has been edited by ScottManDeath (edited 03-31-2001).]
Found a good explanation of the problem along with source on Paul Bourke’s great site:
http://astronomy.swin.edu.au/pbourke/geometry/lineline3d/
Cheers,
Toby