Note: This post has been updated to work with HiGHS.

A fun geometry problem to think about is: given two polygons, do they intersect? That is, do they touch on the border or overlap? Does one reside entirely within the other? While this question has obvious applications in computer graphics (see: arcade games of the 1980s), it’s also important in areas such as cutting and packing problems.

There are a number of way to answer this. In computer graphics, the problem is often approached using a clipping algorithm. This post examines a couple of simpler techniques using linear inequalities and properties of convexity. To simplify the presentation, we assume we’re only interested in convex polygons in two dimensions. We also assume that rotation is not an issue. That is, if one of the polygons is rotated, we can simply re-test to see if they overlap.

Don’t get clobbered by an asteroid!

Problem

Let’s say we have two objects: a right triangle and a square. We can place them anywhere inside a larger rectangle. The triangle has vertices:

$$\{\left(x_t, y_t\right), \left(x_t, y_t + a\right), \left(x_t + a, y_t\right)\}$$

The square has vertices:

$$\{\left(x_s, y_s\right), \left(x_s, y_s + a\right), \left(x_s + a, y_s + a\right), \left(x_s + a, y_s\right)\}$$

We will be given $\left(x_t, y_t\right)$, $\left(x_s, y_s\right)$, and $a$, but we do not know them a priori. We would like to know, for any set of values these can take, whether or not the triangle and square they define intersect.

$\left(x_t, y_t\right)$ and $\left(x_s, y_s\right)$ are the offsets of the triangle and square with respect to the bottom left corner of the rectangle. If they are far enough apart in any direction, the two objects do not intersect. The figure below shows such a case, with small gray circles representing $\left(x_t, y_t\right)$ and $\left(x_s, y_s\right)$.

Polygons that do not intersect

However, if they are too close in some manner, the objects will either touch or overlap, as shown below.

Polygons that intersect

he two polygons can intersect in a few different ways. They may touch on their borders, in which case they will share a single point or line segment. They may overlap such that their intersecting region has nonzero relative interior but each polygon contains points outside the other. Or one of them might live entirely within the other, so that the former is a subset of the latter. Our goal is to determine if any of these cases are true given any $\left(x_t, y_t\right)$, $\left(x_s, y_s\right)$, and $a$.

Method 1. Define the intersecting polygon with linear inequalities

The first method we use to detect intersection is based on the fact that our polygons themselves are the intersections of finite numbers of linear inequalities. Instead of defining them based on their vertices, we can equivalently represent them as the set of $\left(x, y\right)$ that satisfy a known inequality for each edge.

Let $S_t$ be the set of points in our triangle. It can be defined as follows. $x$ must be greater than or equal to $x_t$. $y$ must be greater than or equal to $y_t$. And $x + y$ must be left of or lower than the triangle’s hypotenuse. There are three sides on the triangle, so we have three inequalities.

$$ \begin{array}{rcl} S_t = \{\,\left(x, y\right) & | & x \ge x_t,\\ & & y \ge y_t,\\ & & x + y \le x_t + y_t + a \,\} \end{array} $$

Similarly, let $S_s$ be the set of points in our square. This set is defined using four inequalities, which are shown in a slightly compacted form.

$$ \begin{array}{rcl} S_s = \{\,\left(x, y\right) & | & x_s \le x \le x_s + a,\\ & & y_s \le y \le y_s + a \,\} \end{array} $$

Finally, let $S_i = S_t \cap S_s$ be the set of points that satisfy all seven inequalities.

$$ \begin{array}{rcl} S_i = \{\,\left(x, y\right) & | & x \ge x_t,\\ & & y \ge y_t,\\ & & x + y \le x_t + y_t + a,\\ & & x_s \le x \le x_s + a,\\ & & y_s \le y \le y_s + a \,\} \end{array} $$

If $S_i \ne \emptyset$, then there must exist some point that satisfies the inequalities of both the triangle and the square. This point resides in both of them, therefore they intersect. If $S_i = \emptyset$, then there is no such point and they do not intersect.

Method 2. Use convex combinations of the polygon vertices

Both of our polygons are convex. That is, they contain every convex combination of their vertices. So every point in the triangle, regardless of where it is located, can be represented as a linear combination of ${\left(x_t, y_t\right), \left(x_t + a, y_t\right), \left(x_t, y_t + a\right)}$ where $\lambda_1, \lambda_2, \lambda_3 \ge 0$ and $\lambda_1 + \lambda_2 + \lambda_3 = 1$.

We can define the set $S_t$ equivalently using this concept.

$$ S_t = \{\, \lambda_1 \left(\begin{array}{c} x_t \\ y_t \end{array}\right) + \lambda_2 \left(\begin{array}{c} x_t + a \\ y_t \end{array}\right) + \lambda_3 \left(\begin{array}{c} x_t \\ y_t + a \end{array}\right) \, | \\ \lambda_1 + \lambda_2 + \lambda_3 = 1, \\ \lambda_i \ge 0, , i = {1, \ldots, 3 } \, \} $$

Similarly, the square is defined a the convex combination of its vertices.

$$ S_s = \{\, \lambda_4 \left(\begin{array}{c} x_s \\ y_s \end{array}\right) + \lambda_5 \left(\begin{array}{c} x_s + a \\ y_s \end{array}\right) + \lambda_6 \left(\begin{array}{c} x_s \\ y_s + a \end{array}\right) + \lambda_7 \left(\begin{array}{c} x_s + a \\ y_s + a \end{array}\right) \, | \\ \lambda_4 + \lambda_5 + \lambda_6 + \lambda_7 = 1, \\ \lambda_i \ge 0, , i = {4, \ldots, 7 } \, \} $$

If there exists a point inside both the triangle and the square, then it must satisfy both convex combinations. Thus we can define our intersecting set $S_i$ as follows. (This is a little loose with the notation, but I think it makes the point a bit better.)

$$ \begin{array}{rl} S_i = \{\, & \\ & \lambda_1 \left(\begin{array}{c} x_t \\ y_t \end{array}\right) + \lambda_2 \left(\begin{array}{c} x_t + a \\ y_t \end{array}\right) + \lambda_3 \left(\begin{array}{c} x_t \\ y_t + a \end{array}\right) =\\ & \lambda_4 \left(\begin{array}{c} x_s \\ y_s \end{array}\right) + \lambda_5 \left(\begin{array}{c} x_s + a \\ y_s \end{array}\right) + \lambda_6 \left(\begin{array}{c} x_s \\ y_s + a \end{array}\right) + \lambda_7 \left(\begin{array}{c} x_s + a \\ y_s + a \end{array}\right),\\ & \lambda_1 + \lambda_2 + \lambda_3 = 1,\\ & \lambda_4 + \lambda_5 + \lambda_6 + \lambda_7 = 1,\\ & \lambda_i \ge 0, \, i = {1, \ldots, 7}\\ \,\} & \end{array} $$

Just as before, if $S_i \ne \emptyset$, our polygons intersect.

Code

Both models are pretty easy to implement using an LP Solver. But they look very different. That’s because in the first method we’re thinking about the problem in terms of inequalities and in the second we’re thinking about it in terms of vertices. The code below generates a thousand random instances of the problem and tests that each method produces the same result.

import highspy
import random


def method1(xy_t, xy_s, a):
    x_t, y_t = xy_t
    x_s, y_s = xy_s

    h = highspy.Highs()
    h.silent()

    x = h.addVariable()
    y = h.addVariable()
    h.addConstrs(
        x_t <= x <= x_t + a,
        x_s <= x <= x_s + a,
        y_t <= y <= y_t + a,
        y_s <= y <= y_s + a,
        x + y <= x_t + y_t + a,
    )

    return h


def method2(xy_t, xy_s, a):
    x_t, y_t = xy_t
    x_s, y_s = xy_s

    h = highspy.Highs()
    h.silent()

    lm = [h.addVariable(lb=0, ub=1) for _ in range(7)]

    conv_xt = lm[0] * x_t + lm[1] * (x_t + a) + lm[2] * x_t
    conv_xs = lm[3] * x_s + lm[4] * (x_s + a) + lm[5] * x_s + lm[6] * (x_s + a)

    conv_yt = lm[0] * y_t + lm[1] * y_t + lm[2] * (y_t + a)
    conv_ys = lm[3] * y_s + lm[4] * y_s + lm[5] * (y_s + a) + lm[6] * (y_s + a)

    h.addConstrs(
        conv_xt == conv_xs,
        conv_yt == conv_ys,
        sum(lm[:3]) == 1,
        sum(lm[3:]) == 1,
    )

    return h


if __name__ == "__main__":
    problems1 = []
    problems2 = []

    for _ in range(1000):
        a = random.random() * 2.5 + 1
        x_t = random.random() * 10
        y_t = random.random() * 10
        x_s = random.random() * 10
        y_s = random.random() * 10

        problems1.append(method1([x_t, y_t], [x_s, y_s], a))
        problems2.append(method2([x_t, y_t], [x_s, y_s], a))

    overlap1 = []
    for h in problems1:
        h.solve()
        overlap1.append(h.getModelStatus())

    overlap2 = []
    for h in problems2:
        h.solve()
        overlap2.append(h.getModelStatus())

    assert overlap1 == overlap2

These aren’t necessarily the best ways to solve this particular problem, but they are quick and flexible. And they leverage existing solver technology. One downside is that they aren’t easy to adapt to certain decision making contexts. That is, we can use them to determine whether objects overlap, but not to force objects not to overlap. In the next post, we’ll go over another tool from computational geometry that allows us to embed decisions about the relative locations of objects in our models.

Exercises

  • We assumed convex polygons in this presentation. How might one extend the model to work on non-convex polygons? What problems does this introduce?
  • The two methods shown above are equivalent. How can this be proven?
  • This post only answers the question of whether two convex polygons intersect. Devise models for determining if they only touch, or if one is a subset of the other.