Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a programming problem that involves determining if any 4 line segments intersect. (I am testing to see if four points [in a specific order] comprise a quadrilateral). Mathematically speaking, using the four "endpoints," what is the easiest way to determine whether any of the segments intersect?

share|improve this question
    
Maybe you can use the usual tests for convex polygons? See this for instance. –  J. M. May 9 '11 at 15:41
    
@Arturo: Why not have this tagged [geometry] and [algebra-precalculus]? –  Isaac May 9 '11 at 16:37
    
@Isaac: Why tag it [geometry]? This is a problem in analytic geometry, little more. Sure, you use algebra; you also use arithmetic and real numbers. No point in overlabeling. –  Arturo Magidin May 9 '11 at 16:41

2 Answers 2

up vote 3 down vote accepted

Suppose that you have four points, $A=(x_a,y_a)$, $B=(x_b,y_b)$, $C=(x_c,y_c)$, and $D=(x_d,y_d)$. The line segment joining $A$ and $B$ contains the points $(tx_a+(1-t)x_b,ty_a+(1-t)y_b)$ for $0\le t\le 1$; the line segment joining $C$ and $D$ contains the points $(ux_c+(1-u)x_d,uy_c+(1-u)y_d)$ for $0\le u\le 1$. If the two segments intersect, then the system $$\begin{align} tx_a+(1-t)x_b&=ux_c+(1-u)x_d \\ ty_a+(1-t)y_b&=uy_c+(1-u)y_d \end{align}$$ has a solution for $t$ and $u$ where $0\le t\le 1$ and $0\le u\le 1$.

It should be relatively straight-forward to write explicit formulas for the solutions of that system in terms of the points and check if the solutions are between 0 and 1, inclusive.

share|improve this answer
    
@Isaac: This is a really good way of approaching the situation. And solving by hand, I would definitely prefer this approach. When dealing with the problem in terms of python, though, I found the other solution more convenient in terms of calculations. Thanks! –  Sir Winford May 9 '11 at 20:30
    
@Sean: That's perfectly understandable. Just make sure that either I'm wrong about that answer excluding nonconvex quadrilaterals or you don't want to accept nonconvex quadrilaterals. –  Isaac May 9 '11 at 20:33
    
@Isaac: I failed to check that until reading your comment(s)...after putting points of a nonconvex quadrilateral in my program it said it wasn't a quadrilateral, so apparently the other method does not always work. I have to make yours the best answer now. ;) –  Sir Winford May 9 '11 at 20:53
    
And now I have to adapt my program to use your technique, and I have one hour to do it. :P –  Sir Winford May 9 '11 at 20:58
    
@Sean: Thanks. It may be possible to test it using some area formulas—I suspect that if the area of ABCD as given by the shoelace method is equal to the sum of the areas of ABC and ACD or the sum of the areas of BCD and ABD (checking both covers the nonconvex case), then the four points determine a quadrilateral, though probably including the degenerate case where three points are collinear. (I say that I suspect this because I haven't quite thought through all the possible cases.) –  Isaac May 9 '11 at 20:59

I think there may be a way to avoid the "parameterized" approach. Suppose we wish to determine whether the points $A,B,C,D$ in order determine a nondegenerate quadrilateral. This will occur precisely when the "diagonals" $AC$ and $BD$ have a unique point of intersection interior to both line segments. This happens precisely when $A$ and $C$ lie on different "sides" of $BD$ and $B$ and $D$ lie on different "sides" of $AC$. This last condition can easily be re-expressed in terms of dot products (recall that for vectors $u$ and $v$ their dot product $u \cdot v$ will be positive, zero or negative according as the smallest positive angle between $u,v$ is less than, equal to, or greater than $90$ degrees). For instance, $A,B,C,D$ in that order will form a nondegenerate quadrilateral if and only if both of

  1. $\overrightarrow{AB} \cdot (\overrightarrow{AC})^\bot$ and $\overrightarrow{AD} \cdot (\overrightarrow{AC})^\bot$ are nonzero with opposing signs (or equivalently their product is negative).
  2. $\overrightarrow{BA} \cdot (\overrightarrow{BD})^\bot$ and $\overrightarrow{BC} \cdot (\overrightarrow{BD})^\bot$ are nonzero with opposing signs.

hold where, for points $X,Y$, $\overrightarrow{XY} := Y - X$ is the vector from a $X$ to $Y$ and for a vector $v=(x,y)$, $v^\bot := (-y,x)$ is $v$ rotated counterclockwise by $90$ degrees.

share|improve this answer
    
The dot product approach is more or less what's done in the Graphics Gems chapter I linked to in the comments. –  J. M. May 9 '11 at 18:35
    
@J.M. OK thanks. I didn't actually notice your link, but I'm not at all surprised the approach is the same. After all, how many ways can there possibly be to check if four points form a quadrilateral? –  Mike F May 9 '11 at 18:57
    
I think your criteria might exclude nonconvex quadrilaterals (e.g. "darts"). –  Isaac May 9 '11 at 19:41
    
Sean, @Issac is correct. I was sloppy and didn't entertain the possibility of nonconvex quadrilaterals. This answer is probably not the one you want. –  Mike F May 9 '11 at 20:52
    
@Mike: As it turns out, Isaac is right. (At least my program says so.) –  Sir Winford May 9 '11 at 20:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.