I have a circle, ellipse, square or a rectangle, and I want to determine if it intersects a given triangle.
I am looking for the easiest way to determine if there exists a geometrical intersection between them.
I am only interested in a true/false result. (One point counts as an intersection, more than one point is also intersection.)
Is there such a formula, and, if so, what is it?
Edit: I need to account for any point within as well, not just the lines around each shape, as in two edge cases where the triangle is either completely within the other shape or the shape is within the triangle. In both cases there are no intersections of sides.
$\endgroup$ 22 Answers
$\begingroup$There are a few different approaches.
If the answer doesn't need to be very accurate, you can just "scan convert" each shape into a pixel array (in computer graphics terms). If there is an intersection, you will find that some pixel has been "painted" twice. You can do this sort of thing very very quickly on modern hardware. You don't need to limit yourself to the kind of resolution/accuracy found on typical graphics screens -- your pixel array can be as large as you like, as long as you have enough memory to hold it. The nice thing about this approach is that it's extremely fast and you don't have to write very much special code for each type of shape (just the scan conversion, which is typically very easy).
The other approach is the mathematical one. You compute intersections of curves, basically. This is much more difficult, but the answers will be much more accurate. You'll have to treat each problem individually, so you will end up with a large number of functions, one for each pair of shape types. From a mathematical point of view, most of the functions are easy to implement; intersecting two ellipses is the only one that requires any special knowledge. But writing reliable software is surprisingly difficult. Even intersecting two line segments can get messy because there are so many special cases that have to be handled (near concidences of one sort or another, for example). A good start would the software on this web site. I highly recommend the associated book, too.
Also, take a look at this answer.
Do I get some sort of "badge" for writing an answer that doesn't have a single mathematical symbol in it?? :-)
$\endgroup$ 2 $\begingroup$This Question has a nice mathematical approach. For closed bounded convex shapes the Hyperplane Separation Theorem gives a practical method for checking that two figures do not intersect.
Of the specific cases asked about here, an affine transformation will reduce the ellipse case to one for a circle, and similarly the rectangle case to one for a square. For simplicity let's detail just those two cases.
For two convex polygons it suffices to check the edges of both polygons as candidates for weakly separating lines, i.e. weak in the sense that a convex polygon obviously intersects the line containing one of its edges but is otherwise entirely on one side of that line. If the other convex polygon lies strictly on the opposite side of that line from the first polygon, then they never intersect.
The case involving a circle is not quite so simple to describe since it doesn't have a finite number of edges, but the procedure to check is still easy.
Test for a Triangle Not Intersecting a Circle
The write-up Circle-Triangle Intersection Method aims to optimize programming by avoiding square roots and normals, but we will use them for discussion. [WARNING: My notation/labelling differs from that article.] We assume a non-degenerate triangle, i.e. the 3 vertices are not colinear.
Let $cx + sy = b$ be the normal form of equation for a line containing one edge of the triangle $AC$, i.e. using real coefficients satisfying $c^2 + s^2 = 1$. Then $f(x,y) = cx + sy - b$ represents a signed distance of a point $(x,y)$ to line $\overline{AC}$. Let $(u,v)$ be the center of the circle with radius $r$, and let $(s,t)$ be the third vertex $B$ of the triangle (the one not on that line).
Check for an edge $AC$ of the triangle where the circle's center $O = (u,v)$ is on the opposite side from the third vertex $B = (s,t)$:
$$f(u,v) \cdot f(s,t) \lt 0$$
If no such triangle edge exists, then the test FAILS: the circle's center is inside or on the triangle.
If such a triangle edge is found, then compare the perpendicular distance $p = |f(u,v)|$ from the circle's center to line $\overline{AC}$ to the circle's radius $r$. If $p \gt r$, then the test SUCCEEDS: the circle and triangle do not intersect.
Now check the distances from center $O = (u,v)$ to the triangle vertices $A,C$ which are endpoints of that edge:
$$d_A = \text{dist}(O,A)$$
$$d_C = \text{dist}(O,C)$$
If either of these is less than or equal to radius $r$, then the test FAILS: a vertex is inside the circle.
Finally we compare two projected distances along line $\overline{AC}$ with the length of edge $AC$, namely:
$$k_A = \sqrt{d_A^2 - p^2} \gt \text{dist}(A,C) $$
$$k_C = \sqrt{d_C^2 - p^2} \gt \text{dist}(A,C) $$
If either of these inequalities is true, the test SUCCEEDS: the circle and the triangle do not intersect. Otherwise the test FAILS: they do intersect along edge $AC$.
Test for a Triangle Not Intersecting a Square
As above let a line containing one edge of the triangle have normal equation $cx + sy = b$, so that $f(x,y) = cx + sy - b$ represents a signed distance from point $(x,y)$ to that line, and let $(s,t)$ be the third vertex of the triangle (not on the line).
Let the four vertices of the square be $(x_i,y_i)$ for $i=1,2,3,4$. Vertex $(x_i,y_i)$ lies strictly on the opposite side of the line from $(s,t)$ if and only if $f(x_i,y_i) \cdot f(s,t) \lt 0$.
If all four vertices of the square lie strictly on the opposite side of the line from $(s,t)$, then the test succeeds: the square and the triangle do not intersect. Otherwise continue with testing the remaining edges of the triangle.
If there are no further edges to test, perform a similar check with each edge of the square. If all three vertices of the triangle lie across an edge of the square from the rest of the square, then the test SUCCEEDS: the triangle and square do not intersect.
Otherwise if all edges of the square have been tested without success, the test FAILS: the triangle and square do intersect.
Tests of this type generalize to convex polygons with any number of sides, and also to convex figures in higher dimensions. Tests on nonconvex polygons are often handed by subdividing them into convex subpolygons, e.g. triangulation by ear clipping.
$\endgroup$ 3
