Intersection of line segment with bounding box or other line segment
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 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
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
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