Board index Graphics Algorithms

Question: 2D line segment intersection if colinear

Question: 2D line segment intersection if colinear

Post by Luke Thallmaye » Sat, 13 Jul 1996 04:00:00



Hello,

        I'm writing some routines for 2D polygons and I'd like some
pointer to where I can learn how to determine the endpoints of an
intersection of two line segments when they segments are colinear
(coincident) over some length.

        I've read the FAQ and followed that to some of the reference
books; I've looked at the code from graphic gems and while they`ve
all been helpful, none of them dealt with this issue.  Perhaps I've
misunderstood the material (I'm new to computational geometry) or
it may be in a reference I have not checked.

        I'd appreciate any help or any pointers to references (on-line
or off-line) where this is explained.

        TIA,
----->Luke

 
 
 
Top

Question: 2D line segment intersection if colinear

Post by Jonathan Coh » Sat, 13 Jul 1996 04:00:00




Quote:>Hello,

>    I'm writing some routines for 2D polygons and I'd like some
>pointer to where I can learn how to determine the endpoints of an
>intersection of two line segments when they segments are colinear
>(coincident) over some length.

If two line segments are colinear and overlapping, the endpoints of the
intersection(overlap) must be 2 of their 4 endpoints.  You should
create a 1D parameterization.  Pretend one of the endpoints is the
origin.  Calculate the _signed_ distance of each of the other points
from this origin.  Now you have reduced the problem of determining if 2
intervals overlap in 1D, which you can do simply by comparing these new
coordinates.

Jon
(sorry if that wasn't terriby clear, but I'm in a rush just now)

 
 
 
Top

Question: 2D line segment intersection if colinear

Post by Patrick Campbell-Prest » Tue, 16 Jul 1996 04:00:00





> >Hello,

> >       I'm writing some routines for 2D polygons and I'd like some
> >pointer to where I can learn how to determine the endpoints of an
> >intersection of two line segments when they segments are colinear
> >(coincident) over some length.

> If two line segments are colinear and overlapping, the endpoints of the
> intersection(overlap) must be 2 of their 4 endpoints.  You should
> create a 1D parameterization.  Pretend one of the endpoints is the
> origin.  Calculate the _signed_ distance of each of the other points
> from this origin.  Now you have reduced the problem of determining if 2
> intervals overlap in 1D, which you can do simply by comparing these new
> coordinates.

> Jon
> (sorry if that wasn't terriby clear, but I'm in a rush just now)

If you've already determined that the lines are collinear, you can just
compare the X coordinates of the endpoints (or Y, of course, if the lines
have large or infinite slope) to determine whether the segments overlap
and if so how. The coordinates *are* a 1D parameterisation, after all.

I'm sure this is Joe's book, anyway.

Patrick

--

, author =      "J. O'Rourke"
, title =       "Computational Geometry in {C}"
, publisher =   "Cambridge University Press"
, year =        1994
, note =        "ISBN 0-521-44592-2/Pb \$24.95,
                ISBN 0-521-44034-3/Hc \$49.95.
                Cambridge University Press
                40 West 20th Street
                New York, NY 10011-4211
                1-800-872-7423
                346+xi pages, 228 exercises, 200 figures, 219 references.
                C code and errata available by anonymous ftp from
                grendel.csc.smith.edu (131.229.222.23),
                in the directory /pub/compgeom; Third Printing: Dec. 1995"

- Show quoted text -

Quote:}

 
 
 
Top

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

2. recordable CD's

3. Help me with finding intersections of 2 2D line segments

4. Une créature de reve en cadeau

5. 2d line segment / rectangle intersection

6. VGA Pinouts Needed

7. Intersection of 2 2D line segments

8. Q: 2D intersection of a line segment and a circle

9. Intersection of line Segment and arc segment

10. Q: line segment-polygon intersection (yes, idiot question..)

11. Shorest Line Segment Between 2 3D Line Segments

12. Shortest line segment between two line segments


All times are UTC
Board index