Google Answers Logo
View Question
 
Q: Determine Ray / Line Intersection ( No Answer,   2 Comments )
Question  
Subject: Determine Ray / Line Intersection
Category: Science > Math
Asked by: djohnsto-ga
List Price: $5.00
Posted: 23 Oct 2005 04:39 PDT
Expires: 25 Oct 2005 02:38 PDT
Question ID: 583784
If I have a ray, defined by a starting point (R0) and a direction
Vector (Rdir), and a line defined by two points, (P0, P1), how does
one compute the Point, P` they intersect at? I cannot find any
resources anywhere to solve this.
Answer  
There is no answer at this time.

Comments  
Subject: Re: Determine Ray / Line Intersection
From: manuka-ga on 23 Oct 2005 23:49 PDT
 
It's not clear how many dimensions you're operating in. Fortunately
the procedure is the same - but in general you'll only get a result in
2D. In 3D (or higher) most of the time the two lines will miss each
other. 8-)

Let x = (x_1, x_2, ..., x_n) be the intersection point, if any.

The general equation of your ray is:
x = R0 + t Rdir, t >= 0
The general equation of the line is:
x = P0 + s (P1-P0), s any real number

When you equate these, you get n simultaneous equations in s and t.
Solve these and you will find the intersection point, if one exists.
Note there are three possible cases:
1. All equations are multiples of each other (linearly dependent, if
you know that term) - the ray is on the line, the solution set is the
whole ray.
2. At least two equations are independent and there is a single
solution for s and t - this is the most common case in 2D. There is an
intersection if t>=0, otherwise the point found is on the wrong side
of the ray.
3. The equations are inconsistent, i.e. there are no solutions - this
is the most common case in 3D or higher, but will also occur in 2D if
the ray and line are parallel but separated.

For example, in 2D let the ray go from (1, 2) in the direction (1, 1)
and let the points P0 and P1 be (0, 1) and (1, 0). We get the
equations
(1, 2) + t (1, 1) = (0, 1) + s (1, -1)
i.e. {1 + t = s
     {2 + t = -s
Solving these gives s = -1/2, t = -3/2. You can check that these
values satisfy both equations, and we can substitute either s or t to
get the point (-1/2, 1/2). However, since t<0 this is on the wrong
side of the ray, so they do not intersect.

For a 3D example, let the ray go from (1, 2, 3) in the direction of
(1, 0, -1) and let P0 be (1, 1, 1) and P2 be (3, 2, 1). We get
(1, 2, 3) + t (1, 0, -1) = (1, 1, 1) + s (2, 1, 0)
which gives the simultaneous equations
{ 1 + t = 1 + 2s
{ 2     = 1 +  s
{ 3 - t = 1
The last two equations give us s = 1, t = 2. Substituting this into
the first equation gives 3 = 3, so this is a valid solution. Since t >
0 the point is on the right side of the ray, so they intersect at (3,
2, 1) (which happens to be P2, but only by coincidence - this wouldn't
normally be the case).

If in the last example we had set P0 = (0, 1, 1) instead, the second
and third equations would be the same, giving us the same values for s
and t, but the first equation would become 1 + t = 2s. Substituting in
s and t would then give us 3 = 2, which means that there is no
solution; the line and ray do not intersect.
Subject: Re: Determine Ray / Line Intersection
From: ticbol-ga on 24 Oct 2005 03:33 PDT
 
My Dad told me not to join in a discussion I don't understand. He was
right. But I have worked with many nationalities and many of them I
cannot understand their languages. Yet we worked together allright and
greek-languages [ :-} ] were the least of our problems.

Now here, you are talking in a language that is greek to some of us
who understand only the usual Math languages taught for the masses in
school. Rdir?
Suppose you translate your question above into our garden-variety Math
languages. Like Rdir could be "something (radius?) that is angled
theta from the horizontal" [Zeez, even that is greek to others!]. Or,
direction vector is same as position vector, or something.

If I could understand your "body language" re your greek above, I'd
say you have a line segment (ray) whose one end is R0, whose length is
R, and it is at an angle theta from the horizontal. Then there is
another line segment, whose ends are P0 and P1, that the ray
intersects at point P'. (P' is anywhere between P0 and P1).

If that is really what you meant, then try to put both line segments
on the x,y plane, or plot them on the x,y coordinate axes setup. Put
the R0 at the origin (0,0). Find the coordinates of P0 and P1 based on
the (x=0,y=0) at R0.
Then solve for the equations of the two line segments in terms of x and y.

>>>1st line sement:
tan(theta) = y/x
So,
y = [tan(theta)]*x  ----(1)

>>>2nd line segment:
Say, P0 is point(x0,y0), and P1 is point(x1,y1)
By way of point-slope form of the equation of the line,
(y -y0) = [(y1 -y0)/(x1 -x0)]*(x -x0)
y = [(y1 -y0)/(x1 -x0)]*(x -x0) +y0  ---------(2)

Then, at the intersection point, P', the coordinates of both line
segments are the same, so, equate the y from (1) to the y from (2),
[tan(theta)]*x = [(y1 -y0)/(x1 -x0)]*(x -x0) +y0   -----(3)
From this Eq.(3) you will get the x-coordinate of P'.
See if the x you got here is within or can be projected vertically to
given length of the ray. If it does, then the there is an
intersection. It it does not, then the ray doesn't touch the second
line segment, hence, no intersection, no P'.
If the found x projects up to the ray, hence there is an intersection,
you can get the y-coordinate of P' by plugging the value of the said x
to either of the
y's of Eq.(1) or (2).

-------
Ray. Your ray has a definite length? Is it not long enough that the
other end cannot be seen from R0? Is it like those props in Star Wars?
Darth Vader's ray sword?

---------
If your ray and the other line segment are in 3-D, or the x,y,z setup
is needed, rather than the 2-D x,y setup, then the idea is the same
but you have to knock your (and your computer's) brain a little bit
more.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy