## Intersection of line segment with bounding box or other line segment

### Intersection of line segment with bounding box or other line segment

Greetings

Working in 2-D, I have a line segment PQ, given by the end point
co-ordinates (Px,Py) and (Qx,Qy), and a bounding box B aligned to the x-y
axes, given by the maximum and minimum co-ordinates (Bx0,Bx1,By0,By1).  The
predicate is "PQ intersects B", i.e some point is common to both PQ and B
(including the border of B).  What is the most efficient way to calculate
the predicate?

I already have the coefficients of the equation of the infinite line through
P and Q in normalised general form, and a formula to calculate the
projection of (x,y) onto this line.  I believe that PQ intersects B iff any
corner of B projected onto PQ lies within the segment PQ and within B.  Is
this optimal?

I further evaluate "(x,y) lies within B" as

(x-Bx0)*(x-Bx1) <= 0 && (y-By0)*(y-B1) <= 0

and "(x,y) lies between P and Q (where (x,y) known to be on the line through
P and Q)"
by a similar formula (since P and Q define the bounding box for line segment
PQ).  Is this optimal?

For the predicate "line segment P1Q1 intersects line segment P2Q2", let
d(P,L) be the perpendicular distance of point P from line L.  I evaluate the
predicate as

d(P1,P2Q2)*d(Q1,P2Q2) <= 0 && d(P2,P1Q1)*d(Q2,P1Q1) <= 0

i.e. endpoints of each line segment are on the opposite sides of the other
line segment.  The special case is d(P1,P2Q2) == d(Q1,P2Q2) == 0, when all I
have proved is that the segments are collinear, and I have to check whether
any endpoint lies within the other segment.  Is this optimal?  It avoids the
problem of special casing small as well as zero determinants.  I get the
point of intersection by interpolating between the endpoints in the ratio of
the d values.

Is there a recommended text for this kind of nuts-and-bolts stuff?

Thanks for your input

Jeff

### Intersection of line segment with bounding box or other line segment

> Greetings

> Working in 2-D, I have a line segment PQ, given by the end point
> co-ordinates (Px,Py) and (Qx,Qy), and a bounding box B aligned to the x-y
> axes, given by the maximum and minimum co-ordinates (Bx0,Bx1,By0,By1).  The
> predicate is "PQ intersects B", i.e some point is common to both PQ and B
> (including the border of B).  What is the most efficient way to calculate

I recommend clipping the line to the box and seeing if any of the line
is remaining. This is done efficiently by storing for each vertex (P and
Q) a mask indicating what sides of the box that vertex is outside.

1010    1000    1001
________
|        |
0010 |  0000  | 0001
|________|

0110    0100    0101

By ANDing the 'outcodes' of P and Q, you can quickly reject most line
segments that have a combined outcode of something nonzero.

Say you have a 'difficult' line seqment P and Q that stars at region
1000 and ends at region 0101 but still doesn't touch the box.  Look at
their outcodes:

P 1000
Q 0101

Three bits are different, indicating that PQ may need be clipped with up
to three box sides. Let's start with the top one. Imagine a line
coincident with the top of teh box. Call it RS. Clip the line PQ to form
P`Q` such that P' and Q' are both below the line RS.

This is easy. Q' is the same as Q and P' is the intercept of PQ adn RS.
You know it's P that gets clipped to become P' because it has a '1' in
the outcode bit for 'top' (1xxx). P' must have its 'left' and 'right'
coutcode bits recalculated. In our example they haven't changed.

Now:
P' 0000
Q' 0101

AND these togther to see if the line's still obviously out side the box.
In this case, it's clear that PQ did not cross teh box boundaries

For other lines, you may have to clip against successive sides of teh
box.

Cheers.
Blancmange

### Intersection of line segment with bounding box or other line segment

Quote:> I recommend clipping the line to the box and seeing if any of the line
> is remaining.

If the goal is to determine only if there is an intersection, not
where one might occur, then clipping is too expensive.  You
can use the method of separating axes to test only if there is
an intersection.  Code for line segment and oriented bounding
box in 3D is at my web site, link Computer Graphics |
Dynamic Collision Detection, files ln3bx3ti.{h,cpp}.  It should
be straightforward to specialize to 2D with axis-aligned boxes.

--
Dave Eberly

http://www.magic-software.com

### Intersection of line segment with bounding box or other line segment

Thanks for your replies.

Jeff

>> I recommend clipping the line to the box and seeing if any of the line
>> is remaining.

>If the goal is to determine only if there is an intersection, not
>where one might occur, then clipping is too expensive.  You
>can use the method of separating axes to test only if there is
>an intersection.  Code for line segment and oriented bounding
>box in 3D is at my web site, link Computer Graphics |
>Dynamic Collision Detection, files ln3bx3ti.{h,cpp}.  It should
>be straightforward to specialize to 2D with axis-aligned boxes.

>--
>Dave Eberly

>http://www.magic-software.com

### Intersection of line segment with bounding box or other line segment

> Thanks for your replies.

> Jeff

> >> I recommend clipping the line to the box and seeing if any of the line
> >> is remaining.

> >If the goal is to determine only if there is an intersection, not
> >where one might occur, then clipping is too expensive.  You
> >can use the method of separating axes to test only if there is
> >an intersection.  Code for line segment and oriented bounding
> >box in 3D is at my web site, link Computer Graphics |
> >Dynamic Collision Detection, files ln3bx3ti.{h,cpp}.  It should
> >be straightforward to specialize to 2D with axis-aligned boxes.

> >--
> >Dave Eberly

> >http://www.magic-software.com

A separating-axis approach for segment-box intersection testing
(although presented as a minkowski sum test, which basically boils down
to the same thing) can also be found in Green and Hatch 'Fast
polygon-cube intersection testing' in Graphics Gems V.

For the final story on line segment clipping, I would recommend Jim
Blinn's 'A trip down the graphics pipeline', either the 1991 IEEE CGA
11(1) column, or the book.