Ray Line-Segment intersection in 2D - Graphics

The ray is defined by (cx, cy) + g * (dx, dy), where g >=0 and the line
segment is defined by (ax, ay) + h * ( bx - ax, by - ay ), where 0 <= h <=
1. This gives you two sets of equations (one for the x component, and one
for the y component). Just solve for the unknown reals g and h. If g or h
do not meet the conditions I mention above for them, then there is no
intersection, otherwise there is (and the point can be found by substituting
g or h into their respective ray or line equations).

If the ray and line are in 3D and are co-planar, then do the same but after
you orthogonally project them onto a primary plane (x=0, y=0 or z=0). To
choose the plane you want, compute the cross product between the direction
of the line and the direction of the segment (either orientation). Then
find the component with the largest unsigned magnitude if this is x use x=0,
y then use y=0, z then use z=0.

I am assuming the line and ray are not colinear.

- Shaun
--------------------
www.nirenstein.com

"Sherrie Laraurens" <sherrielaraurens@hotmail.com> wrote in message
news:1153281180.634553.215160@b28g2000cwb.googlegroups.com...
> Hi all,
>
> I'm wondering if anyone has any ideas on how to go about
> ascertaining whether or not a ray and a line segment intersect
> in 2D? assuming the ray is defined by the point cx,cy and
> the direction dx dy.
>
> My next question would be is it possible to use the same approach
> in 3d? I am aware of the nastiness involved in obtaining the
> intersection between two 3d line-segments, so I'm prepared to
> have some level of fuzziness in the calculations (I'll be making
> sure the line-segment and ray are planar).
>
>
> sherrie
>

Sherrie,

I think you're looking for something like this:

template<typename T>
inline bool intersect(const ray<T,2>& ray, const segment<T,2>& segment)
{
T t = ((ray.direction.x * ray.origin.y + ray.direction.y *
(segment[0].x - ray.origin.x)) -
(ray.direction.x * segment[1].y)) /
(ray.direction.y * (segment[0].x + segment[1].x) -
ray.direction.x * (segment[0].y + segment[1].y));

return (
greater_than_or_equal(t,T(0.0)) &&
less_than_or_equal(t,T(1.0))
);
}


Arash Partow
________________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net



Sherrie Laraurens wrote:
> Hi all,
>
> I'm wondering if anyone has any ideas on how to go about
> ascertaining whether or not a ray and a line segment intersect
> in 2D? assuming the ray is defined by the point cx,cy and
> the direction dx dy.
>
> My next question would be is it possible to use the same approach
> in 3d? I am aware of the nastiness involved in obtaining the
> intersection between two 3d line-segments, so I'm prepared to
> have some level of fuzziness in the calculations (I'll be making
> sure the line-segment and ray are planar).
>
>
> sherrie

"Sherrie Laraurens" <sherrielaraurens@hotmail.com> wrote in message
news:1153281180.634553.215160@b28g2000cwb.googlegroups.com...

> I'm wondering if anyone has any ideas on how to go about
> ascertaining whether or not a ray and a line segment intersect
> in 2D? assuming the ray is defined by the point cx,cy and
> the direction dx dy.
>
> My next question would be is it possible to use the same approach
> in 3d? I am aware of the nastiness involved in obtaining the
> intersection between two 3d line-segments, so I'm prepared to
> have some level of fuzziness in the calculations (I'll be making
> sure the line-segment and ray are planar).

As mentioned by others, the 2D problem may be solved by
equating the parametric equations. The ray is P0+s*D0, where
P0 is the ray origin, D0 is a direction vector (not necessarily
unit length), and s >= 0. The segment is P1+t*D1, where P1
and P1+D1 are the endpoints, and 0 <= t <= 1. Equating, you
have P0+s*D0 = P1+t*D1. Define perp(x,y) = (y,-x). Then
if Dot(perp(D1),D0) is not zero,
s = Dot(perp(D1),P1-P0)/Dot(perp(D1),D0)
t = Dot(perp(D0),P1-P0)/Dot(perp(D1),D0)
The s and t value are where the *lines* containing the ray
and segment intersect. The ray and segment intersect as
long as s >= 0 and 0 <= t <= 1. If Dot(perp(D1),D0) is zero,
then the ray and segment are parallel. If they do not lie on
the same line, there is no intersection. If they do lie on the
same line, you have to test for overlap, which is a 1D problem.

As noted by you, in 3D a ray and segment are not expected
to intersect. If you set up the equations mentioned in the
previous paragraph, you have three equations in two unknowns.
Instead, you should compute the *distance* between the ray
and segment. If the distance is "sufficiently close" to zero, you
can call it an intersection (in a "fuzzy" kind of way).

That said, you mentioned about making sure the ray and segment
are coplanar. In this case, compute the coordinates of the ray
and segment in terms of a coordinate system for that plane. Then
you are back to the 2D problem. For example, let the plane be
Dot(N,X-Q) = 0, where N is a unit-length normal to the plane and
where Q is a point on the plane. Let U and V be unit-length vectors
so that {U,V,N} are mutually perpendicular. Then
P0 = Q + x0*U + y0*V
D0 = Q + x1*U + y1*V
P1 = Q + x2*U + y2*V
D1 = Q + x3*U + y3*V
The 2D problem uses a ray (x0,y0)+s*(x1,y1) and a segment
(x2,y2)+t*(x3,y3).

I have 2D intersection code and 3D distance code for these
problems at my web site.

--
Dave Eberly
http://www.geometrictools.com

On 18 Jul 2006 20:53:00 -0700, "Sherrie Laraurens"
<sherrielaraurens@hotmail.com> wrote:
>My next question would be is it possible to use the same approach
>in 3d? I am aware of the nastiness involved in obtaining the
>intersection between two 3d line-segments, so I'm prepared to
>have some level of fuzziness in the calculations (I'll be making
>sure the line-segment and ray are planar).

Since you don't say, let's assume that the ray is given by a point and
a vector, and that the line segment is give by its end points. Call
these Pr, Vr, P0, and P1. Also assume Vr is nonzero and P0 is not P1.

Suppose Pr is not collinear with P0 and P1. Then the three points
determine the plane that must contain any intersection, and the cross
product N = (P0-Pr)x(P1-Pr) is normal to that plane. There can be no
intersection unless Vr lies in the plane, thus the dot product N.Vr
must be zero. Passing this test does not guarantee an intersection;
but it is relatively quick and does help us choose a 2D projection if
it succeeds.

If Pr *is* collinear with P0 and P1, careful ****ysis is required. In
case Pr lies between P0 and P1, it is a point of intersection. When Pr
itself is not on the segment, then we can only have an intersection if
Vr is parallel to the line segment and if (P0-Pr).Vr is positive; in
which case every point on the segment is also on the ray.

That said, lines in 3D essentially *never* intersect, and the chances
of a ray and a segment passing these tests in spite of floating point
errors is slim indeed. A more robust approach might be to calculate
the distance between the line of the ray and the line of the segment,
and if that's close enough then worry about the further details. This
still requires empirical decisions about collinearity and the like.
And certain configurations will be highly sensitive to perturbations,
like those accidentally introduced by floating point rounding.