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?
Algebraically determine if lines intersect
-
0Maybe you can use the usual tests for [convex polygons](http://mathworld.wolfram.com/ConvexPolygon.html)? See [this](http://books.google.com/books?id=CCqzMm_-WucC&pg=PA138) for instance. – 2011-05-09
-
0@Arturo: Why not have this tagged [geometry] and [algebra-precalculus]? – 2011-05-09
-
0@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. – 2011-05-09
2 Answers
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.
-
0@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! – 2011-05-09
-
0@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. – 2011-05-09
-
0@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. ;) – 2011-05-09
-
0And now I have to adapt my program to use your technique, and I have one hour to do it. :P – 2011-05-09
-
0@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](http://en.wikipedia.org/wiki/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.) – 2011-05-09
-
0@Sean: If you have access to Mathematica, a TI-89, or some other computer algebra system, you can use that to explicitly solve the two equations I gave for $t$ and $u$ in terms of the four points, then program from that formula... (I don't have easy access to a CAS at this particular moment.) – 2011-05-09
-
0@Isaac: The shoelace method would probably work (my program already checks for 3 collinear points which would solve the one problem), and seems fairly easy (I wish I had heard of it before now). And I don't have a CAS at the moment either, of course. Thanks again for all of the input you have provided. – 2011-05-09
-
0@Sean: Be careful about trying to use the area test that I suggested. I suspect that if ABCD is a square, then ACBD will pass the area test that I suggested, even though it is self-intersecting (which you probably want to fail). – 2011-05-09
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
- $\overrightarrow{AB} \cdot (\overrightarrow{AC})^\bot$ and $\overrightarrow{AD} \cdot (\overrightarrow{AC})^\bot$ are nonzero with opposing signs (or equivalently their product is negative).
- $\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.
-
0The dot product approach is more or less what's done in the *Graphics Gems* chapter I linked to in the comments. – 2011-05-09
-
0@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? – 2011-05-09
-
0I think your criteria might exclude nonconvex quadrilaterals (e.g. "darts"). – 2011-05-09
-
0Sean, @Issac is correct. I was sloppy and didn't entertain the possibility of nonconvex quadrilaterals. This answer is probably not the one you want. – 2011-05-09
-
0@Mike: As it turns out, Isaac is right. (At least my program says so.) – 2011-05-09
-
0@Mike: You beat me to it, thanks for the answer, though! =D – 2011-05-09
-
0@Sean: My conditions 1 and 2 indeed hold if and only if AC and BD intersect at a unique point interior to both segments. The problem is that I claim the latter condition is equivalent to the nondegeneracy of quadrilateral ABCD. This is false when the quadrilateral is nonconvex (or if 2 consecutive sides are parallel for that matter). Sorry to have misled you. – 2011-05-09
-
0@Mike: How can consecutive sides of a non-degenerate polygon be parallel? – 2011-05-09
-
0@Isaac: What I meant was that the statements "AC and BD intersect at a unique point interior to both segments" and "ABCD is nondegenerate" are not equivalent when ABCD has consecutive sides parallel. – 2011-05-09
-
0@Mike: I'm thinking that if consecutive sides—say AB and BC—are parallel, then A, B, and C are collinear and the polygon is degenerate, and AC and BD will intersect at B, which is not interior to the polygon. So, it's not clear to me what breaks down when consecutive sides are parallel. – 2011-05-09
-
0@Isaac: In the statement "AC and BD intersect at a unique point interior to both segments" I was referring to the 1d interior of the segments not the 2d interior of the polygon. That is, I was requiring that the intersection of AC and BD not be an endpoint of either segment. So for me the statement is false when AC and BD intersect at B. I would agree with you that the polygon is degenerate in this case - hence the nonequivalence of the 2 statements above. More obviously the equivalence breaks down when the polygon is nonconvex. – 2011-05-09