Intersecting Polygons

By Delacy on Saturday, May 12, 2001 - 02:54 pm:

Can anyone tell me how I would be able to test if two polygons are intersecting? The polygons can be concave, and each point is at an integer coordinate. Any help would be most appreciated.

By Dan Goodman (Dfmg2) on Monday, May 14, 2001 - 01:21 pm:

A simple minded approach (but slow) which works for all polygons (convex or not) is to try the following: call the first polygon P and the second polygon Q, call the vertices of the first polygon v₁ to v_n so that v₁ =v_n and they are listed counterclockwise and the vertices of the second polygon w₁ to w_m so that w₁ =w_m and they are listed counterclockwise. First of all, you want to check if P is entirely contained in Q. If you test whether v₁ is in Q this is enough. If v₁ is in Q then they are intersecting, if not then P is not entirely contained in Q. If P is not entirely contained in Q then one of the edges of P must intersect one of the edges of Q. So you just test each edge v_i v_i+1 of P against each edge w_j w_j+1 of Q. Using this method there are mn tests to do, which is not particularly efficient. To speed it up, you can do a bounding box test to start with. i.e. you draw a minimal box around P, a minimal box around Q and test if they intersect. If they don't, then clearly P and Q don't intersect. If you're doing ray tracing or collision detection for a game then you'll want to do this, because the number of poly-poly intersections will be small but the number of poly-poly tests will be large, and bounding box tests are very quick.

Do you know how to test if a point is in a polygon and how to test if a line segment intersects another line segment? If not, post again and I'll explain.

By Anonymous on Thursday, May 24, 2001 - 11:01 am:

Thanks for the great answer. Everything I'd looked at was just using points, but now I see that using edges will do exactly what I want - speed isn't an issue either, it doesn't need to be done at run time. I haven't done line segment collision, and I'm sure there's plenty of stuff on the net already, but if you have time I'd love to see your answer.

By Dan Goodman (Dfmg2) on Monday, June 04, 2001 - 08:39 pm:

OK, I realise this isn't very complicated so I've got time now after all.

Suppose you have four vectors $x$ , $y$ , $z$ , $w$ and you want to check if the line segment from $x$ to $y$ intersects the line segment from $z$ to $w$ .

Let $u = y - x$ and $v = w - z$ . The line segment $x y$ is the set of points $x + s u$ for $0 \leq s \leq 1$ and the line segment $z w$ is the set of points $z + t v$ for $0 \leq t \leq 1$ . So we need to solve:

$x + s u = z + t v$ (*)

Once we've solved this, we need to check that $0 \leq t \leq 1$ and $0 \leq s \leq 1$ , because if not then the lines intersect but the segments don't.

Let the vector $p$ be perpendicular to $u$ . If $u = (u_{x}, u_{y})$ then $p = (- u_{y}, u_{x})$ will do (I hope you're happy with the use of dot products, if not write back and I'll explain). Dot both sides of (*) with $p$ , to get:

$x . p + s u . p = z . p + t v . p$

But $u . p = 0$ , because $p$ is perpendicular to $u$ , so we have

$x . p = z . p + t v . p$

So $t = (x . p - z . p) / (v . p) = (x - z) . p / v . p$

Let $q$ be perpendicular to $v$ and dot it with (*) to get:

$x . q + s u . q = z . q$

So $s = (z - x) . q / u . q$

So now we have $s$ and $t$ , we check $0 \leq s$ , $t \leq 1$ and if so, we have an intersection, and moreover we know where the intersection is ( $x + s u = z + t v$ ).