|
|
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. |
|
There is no answer at this time. |
|
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. |
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 Home - Answers FAQ - Terms of Service - Privacy Policy |