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