Detecting intersection of convex polygons in 2D

Author: Wojciech Muła
Added on:2013-09-15
Updated on:2017-01-28 (spelling)

Contents

Introduction

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 return anything.

SAT recall

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

Number of operations in the worst case

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.

Another approach

2013-09-15-convex-polygon-intersection/sample.png

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.

Algorithm

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

Number of operations in the worst case

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.

Demo

Check interactive demonstration.