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