Newsgroups: sci.math
From: pmontgom@cwi.nl (Peter L. Montgomery)
Subject: Re: Intersection of two line segments?
Date: Wed, 15 Mar 1995 04:18:14 GMT
In article <3k4eb8$chg@crcnis3.unl.edu> zmievski@herbie.unl.edu
(Silicon) writes:
>Let's say I have two line segments and their starting and ending
>coordinates are known. How can I quickly find out if they intersect?
I will assume the problem is 2-dimensional.
Say line segment 1 goes from P1 = (x1, y1) to P2 = (x2, y2)
and line segment 2 goes from P3 = (x3, y3) to P4 = (x4, y4).
For simplicity, assume that no three of these points
lie in a straight line.
The sign of the determinant
| x1 y1 1 |
det(P1, P2, P3) = | x2 y2 1 |
| x3 y3 1 |
identifies which side (e.g., north or south) of (extended) line 1
contains P3. The line segment from P3 to P4 will intersect the
extended line 1 precisely when P3 and P4 are on opposite sides
of this line, which is when
det(P1, P2, P3) * det(P1, P2, P4) < 0.
In order that the point of intersection be between P1 and P2,
we also require
det(P3, P4, P1) * det(P3, P4, P2) < 0
We can evaluate all four determinants via minors
of the last column if we compute the six 2 x 2 determinants
x1*y2 - x2*y1 x1*y3 - x3*y1 x1*y4 - x4*y1
x2*y3 - x3*y2 x2*y4 - x4*y2 x3*y4 - x4*y3
and use 8 additions/subtractions to combine them.
The operation count goes down if we observe that
the original problem is invariant under translation.
Six subtractions let us replace P_i by P_i - P1 for i = 2, 3, 4.
Then only the last three 2 x 2 determinants are needed,
since the first three vanish when P1 = 0. Compute
(x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1) = det(P1, P2, P3)
(x2 - x1)*(y4 - y1) - (x4 - x1)*(y2 - y1) = det(P1, P2, P4)
(x3 - x1)*(y4 - y1) - (x4 - x1)*(y3 - y1) = det(P3, P4, P1)
det(P1, P2, P3) - det(P1, P2, P4) + det(P3, P4, P1) = det(P3, P4, P2)
(11 additions/subtractions, 6 multiplications).
Now test the signs of the determinants, and worry about the case
when a determinant is zero (in which our assumption about
no three points in a straight line is incorrect).
--
Peter L. Montgomery pmontgom@cwi.nl San Rafael, California
Mathematically gifted, unemployed, U.S. citizen. Interested in computer
architecture, program optimization, computer arithmetic, cryptography,
compilers, computational mathematics. 17 years industrial experience.
==============================================================================
From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Determine whether two line segment intersect
Date: 3 May 1995 14:37:52 GMT
In article <3o6g0l$kme@minnie.cs.ucsb.edu>,
Hyun J. Kim wrote:
>I need help on developing algorithm in C to determine whether two line
>segments intersect.
>
>I have four points. There is a line segment from point a to point b and
>another line segment from point c to point d. With these two segments, I
>have to determine whether they intersect or not.
Let me change the notation just a bit.
Write the one line as the set of points t*P1 + (1-t)*P0 where P0 and
P1 are the points on it. (These points show up when t=0 and t=1, respectively;
the rest of the line _segment_ comes from t between 0 and 1.)
Likewise the other segment is points of the form u*Q1 + (1-u)*Q0.
To see where they cross, set the x and y coordinates equal; that is,
you solve the equation
(a+bt, c+dt) = (e+fu, g+hu)
for t and u. The solution is that (t, u) = (1/det) * A * v where
A = matrix( (-h, f), (-d, b) )
v = columnvector( e-a, g-c )
det=-b*h+f*d (the determinant of A)
Once you know where the lines meet, you can see if the intersection is
on the _segments_ by checking to see if the t and u above lie
between 0 and 1. You can write it out as a collection of four
polynomials in the coordinates of P0, P1, Q0, and Q1 which must all
be non-negative, but I don't know if that's "better", especially if you
later need to know _where_ the segments cross.
(Of course you need to be careful if the segments are parallel or equal,
or close enough to appear so with machine precision.)
dave
(We're going to need a FAQ on vector geometry pretty soon.)
==============================================================================
From: rjohnson@apple.com (Robert Johnson)
Newsgroups: sci.math
Subject: Re: Determine whether two line segment intersect
Date: 5 May 1995 01:23:28 -0700
In article <3o6g0l$kme@minnie.cs.ucsb.edu>,
Hyun J. Kim wrote:
>I need help on developing algorithm in C to determine whether two line
>segments intersect.
>
>I have four points. There is a line segment from point a to point b and
>another line segment from point c to point d. With these two segments, I
>have to determine whether they intersect or not.
Define the function on three points
+- -+
| u_x v_x w_x |
f(u,v,w) = det | u_y v_y w_y |
| 1 1 1 |
+- -+
= (u_x-w_x)(v_y-w_y) - (u_y-w_y)(v_x-w_x)
Then iff sgn(f(a,b,c)) != sgn(f(a,b,d)) and sgn(f(a,c,d)) != sgn(f(b,c,d)),
the lines intersect (sgn(0) = 0 and sgn(x) = x/|x| if x != 0).
f(u,v,w) is twice the signed area of the triangle with vertices u, v, and w.
The sign of the area depends on the orientation of the axes and whether the
path u->v->w->u is clockwise or counterclockwise.
If c and d are on identical/opposite sides of the line containing a and b,
then the direction of the path a->b->c->a is identical/opposite to that of
a->b->d->a; therefore, the sign of f(a,b,c) is identical/opposite to that of
f(a,b,d).
The test checks if c and d are on opposite sides of the line containing
a and b and if a and b are on opposite sides of the line containing c and d.
In that case, and only in that case, the lines intersect.
Rob Johnson
Apple Computer, Inc.
rjohnson@apple.com
==============================================================================
From: Robin Chapman
Newsgroups: sci.math
Subject: Re: Need a geometry equation/algorithm
Date: Fri, 28 Aug 1998 07:25:52 GMT
>
> Hi,
>
> I'm looking for an equation or efficient algorithm to determine if two
> line segments intersect. Can anybody help?
>
See section 35.1 of Cormen/Leiserson/Rivest Introduction to Algorithms.
Briefly there are two steps
1. quick rejection: the bounding box of the segement from (x_1, y_1)
to (x_2, y_2) is the rectangle with sides x = x_1, x = x_2, y = y_1,
y = y_2. Unless their bounding boxes intersect the segments cannot.
2. straddling: two segments whose bounding boxes meet interesect
if they straddle each other: i.e., the endpoints of each lie on
opposite sides of the line determined by the other. If the segments
are P_1P_2 and P_3P_4 then P_3P_4 straddles P_1P_2 iff the
vector cross products (P_3 - P_1) x (P_2 - P_1) and (P_4 - P_1) x (P_2 - P_1)
have different signs. (If one vanishes then we do say the straddle).
Robin Chapman
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum