Author: | Wojciech Muła |
---|---|

Added on: | 2013-09-15 |

Updated on: | 2017-01-28 (spelling) |

Treść

Detecting intersection of convex polygons is a common problem in a wide range
of problems. The method of **separated axis theorm** (SAT) is widely used, and
considered as the easiest and the fastest.

This article presents a quite naive algorithm, that in terms of processing polygon vertices is better than SAT — in the worst case it requires fewer additions & multiplications. However, in practice SAT is faster.

I believe that the approach was already discussed, but quick search didn't returned anything.

SAT algorithm: for each face of both polygons find its normal, project both polygons on the normal. If projections are disjoint then the polygons do not intersect.

Projection of polygon requires calculation a cross product of each vertex and the normal.

If the first polygon consist *k* vertices, and the second *m* vertices,
then *k* + *m* normals have to be checked; each projection requires *k* + *m*
projections on normals (a cross product).

In the worst case (*k* + *m*)^{2} cross products have to be calculated.
A cross product costs two multiplications and one addition.

There are *k* + *m* normals, finding the normal for a face costs two subtracts.

The number of additions/subtractions is 2 ⋅ (*k* + *m*) + (*k* + *m*)^{2}, and
the number of multiplications is 2 ⋅ (*k* + *m*)^{2}.

If convex polygons have no intersection then exists a line, that divides the plane in two halfplanes containing each polygon.

A line is represented as *f*(*x*, *y*) = 0 where function *f*(*x*, *y*) = *a* ⋅ *x* + *b* ⋅ *y* + *c*. If there is no intersection, then the sign of *f* for vertices
from the first polygon is opposite to the sign of vertices from the second polygon.

There are infinity number of separating lines, but fortunately we can easily
find one if we allow that a separating line goes through a vertex (or an edge) of
both polygons. This assumption looses mathematical definition (i.e. sometimes sign
of *f* is 0), but in practice brings the same "corner case" as other methods.

We check all possible lines going through all vertices of both polygons, and check which one separates them:

for vertice1 in polygon1: for vertice2 in polygon2: line = line(vertice1, vertice2) s1 = side_of_line(line, polygon1) s2 = side_of_line(line, polygon2) if s1 and s1 are not undefined and s1 * s2 < 0: return 'polygons do not intersect'

Determining position of polygon against the line can be done in **constant time**.
Let `p` is the current vertex (`vertice1` or `vertice2`, depending on
a polygon), and then `p0` is the previous & `p1` is the next vertex.

If both `p0` and `p1` lie on the same side of the line, then whole polygon lies
on that side. Since the polygon is convex, it's not possible that any other edge cross
the line. Pseudocode:

function side_of_line(line, p0, p2) begin side0 = side(line, p0) side2 = side(line, p1) if side0 * side2 < 0 then return undefined; # crossing the line if side0 = side2 then return side0 if side0 = 0 then return side2 if side2 = 0 then return side0 end; function side(line, x, y) begin retun sign(line.a * x + line.b * y + line.c) end

In the worst case most *k* ⋅ *m* lines are processed.

Finding the line equation costs three subtracts and two multiplications.

Checking a line side requires evaluation of the line equation (two multiplications and two additions), this is done four times (two points per polygon).

The number of additions/subtractions is 11 ⋅ *k* ⋅ *m*
and the number of multiplications is 10 ⋅ *k* ⋅ *m*.

Check interactive demonstration.