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