Intersection of Point-line and line....

Intersection of Point-line and line....

Post by David Gambl » Thu, 14 Aug 1997 04:00:00

This is probably +really+ simple, but I'm hoping
to find the most optimised (mathematically) way of
doing it....

I need to establish if an intersection occurs
between a point+"vector" and a line....

Yes, I am talking about the basis for a doom engine :)

|   / \=view ray
|  /^  \   |
| line  X=viewer

My initial solution to the problem was to
(pre)calculate the angle of the line, and rotate
the line points around the view point by this angle,
and also transforming the gradient of the 'viewer ray'
thus projecting the line onto one axis, and so checking
if the intercept of this now 1d line with the "view ray"
was within the bounds of the 1d line....

(Kinda difficult for parallel object *8+)

But, I'm sure that isn't the Best way.....
I know it's a bit of a silly question, but my maths
ain't that great, and i need a hand :)

(Sorry if my blatant stupidity has offended anyone...)




1. 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
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


2. Questions on PSP 3.12

3. sweep line algorithm for line intersection

4. Trigger my application from other application by a mouse click.

5. How to: (3d) line with line intersection?

6. Attn! Need a graphics algorithm!?

7. Need line/line intersection algorithm

8. mac black screen?

9. Point of intersection of n lines

10. Finding 2d Line Intersection Points

11. Line-plane intersection point

12. Point of intersection between a line and a circle

13. intersection between a line segment and a sphere/point