Intersecting rectangles on a torus

Question

Description

Imagine a space like the arcade game Asteroids where everything wraps around right to left and bottom to top - effectively coordinates on a flat torus. The diagram shows an example of two intersecting rectangles. The red rectangle at bottom right is wrapping around so that portions off screen are shown on the top and left, likewise with the blue.

Code

The code takes in coordinates and width and height of two rectangles and the domain for x and y, and it returns whether they are intersecting given that they wrap around within the domain. I've included some test cases.

Asking for thoughts on improvements, optimisations, simplifications, bugs? etc...

// Preconditions: x1, w1, y1, h1, x2, w2, y2, h2 are between 0 and domain exclusive
bool IntersectsOnTorus(int x1, int w1, int y1, int h1, int x2, int w2, int y2, int h2, int domain)
{
    int r1 = x1 + w1;
    int r2 = x2 + w2;
    if (r1 < domain || r2 < domain)
    {
        r1 -= r1 >= domain ? domain : 0;
        r2 -= r2 >= domain ? domain : 0;
        if (x1 >= r2 && x2 >= r1 || x1 <= r1 && x2 <= r2 && (x1 >= r2 || x2 >= r1))
            return false;
    }
    int b1 = y1 + h1;
    int b2 = y2 + h2;
    if (b1 < domain || b2 < domain)
    {
        b1 -= b1 >= domain ? domain : 0;
        b2 -= b2 >= domain ? domain : 0;
        if (y1 >= b2 && y2 >= b1 || y1 <= b1 && y2 <= b2 && (y1 >= b2 || y2 >= b1))
            return false;
    }
    return true;
}

Test(5, 10, 5, 20, 20, 10, 20, 10, 50, false);
Test(5, 15, 5, 20, 20, 10, 20, 10, 50, false);
Test(5, 17, 5, 20, 20, 10, 20, 10, 50, true);
Test(5, 25, 5, 20, 20, 10, 20, 10, 50, true);
Test(5, 28, 5, 20, 20, 10, 20, 10, 50, true);
Test(5, 48, 5, 20, 20, 10, 20, 10, 50, true);
Test(25, 28, 5, 20, 20, 10, 20, 10, 50, true);
Test(30, 28, 5, 20, 20, 10, 20, 10, 50, false);
Test(30, 45, 5, 20, 20, 10, 20, 10, 50, true);

void Test(int x1, int w1, int y1, int h1, int x2, int w2, int y2, int h2, int domain, bool expected)
{
    bool result1 = IntersectsOnTorus(x1, w1, y1, h1, x2, w2, y2, h2, domain);
    bool result2 = IntersectsOnTorus(x2, w2, y2, h2, x1, w1, y1, h1, domain);
    bool result3 = IntersectsOnTorus(y1, h1, x1, w1, y2, h2, x2, w2, domain);
    bool result4 = IntersectsOnTorus(y2, h2, x2, w2, y1, h1, x1, w1, domain);
    bool success = result1 == result2 && result2 == result3 && result3 == result4 && result1 == expected;
    Console.WriteLine($"""{result1}, {result2}, {result3}, {result4}, {(success ? "Success" : "Fail")}""");
    Console.WriteLine();
}

Answer 1

bool IntersectsOnTorus(int x1, int w1, int y1, int h1, int x2, int w2, int y2, int h2, int domain)

Choosing to phrase it as (x, w, y, h) instead of (x, y, w, h) seems a bit odd, but OK, we can go with it.

---

    int r1 = x1 + w1;
    int r2 = x2 + w2;
    if (r1 < domain || r2 < domain)
    {
        r1 -= r1 >= domain ? domain : 0;
        r2 -= r2 >= domain ? domain : 0;

Didn't we want r1 >= domain rather than < ?

Is there some reason % modulo is not suitable here? If so, it's worth documenting in a // comment. If it's due to some timing measurement, include a URL that describes details.

---

        if (x1 >= r2 && x2 >= r1 || x1 <= r1 && x2 <= r2 && (x1 >= r2 || x2 >= r1))

I imagine this is mostly correct.

It would be helpful to name some of those sub-expressions, perhaps with identifiers like x1_wrapped.

Let's talk about some adjacent unit squares, with UL LR coords of (0, 1) (1, 0) and (1, 1) (2, 0). Now, are they "overlapping"? I'm inclined to think the answer is "no". I recommend using lo <= x < hi half-open intervals. The current approach uses lo <= x <= hi.

---

DRY. The "bottom" calculations are essentially identical to the "right" calculations. Consider rephrasing (x, y) as a single location. Then we could Extract Helper and pass in 0 for the "right" comparison and pass in 1 for the "bottom" comparison.

---

Wow, I really like the symmetries exposed by Test(), good job!

Answer 2

Let's take the simplest possible intersection test--1D intervals on an infinite line--and build up the function we want.

What I've found in determining when things intersect is that the test for non-intersection (disjoint) is much simpler. The intervals are disjoint if the left edge of one is to the right of the right edge of the other, or if the right edge of one is to the left of the left edge of the other. This is simpler to express in code. For the 1D case:

// Returns whether the 1D intervals defined by left edges l1 and l2
// and widths w1 and w2 on an infinite line are non-intersecting.
// Touching at edges or corners do not count as intersecting.
bool AreDisjoint1d(int l1, int w1, int l2, int w2)
{
    int r1 = l1 + w1;
    int r2 = l2 + w2;
    return l1 >= r2 || r1 <= l2;
}

bool AreIntersecting1d(int l1, int w1, int l2, int w2)
{
    return ! AreDisjoint1d(l1, w1, l2, w2);
}

We can use these 1D functions to define the 2D intersection by the following fact: rectangles intersect if both their X intervals and Y intervals intersect. So,

bool AreIntersecting2d(int x1, int w1, int y1, int h1, int x2, int w2, int y2, int h2)
{
    return AreIntersecting1d(x1, w1, x2, w2) && AreIntersecting1d(y1, h1, y2, h2);
}

Now we come to the problem of doing this on a torus. Changing your mental image of the problem can help here. Instead of imagining shapes split over the border of the domain, imagine that the domain is replicated infinitely on a 2D grid. This way, the shapes simply move into the next identical grid instead of warping to the other side of one grid. All of these grids are identical, so they all contain the same shapes, like this:

If any of the copies of one shape intersect any copy of the other shape, then they intersect. Now, we can write our intersection on a torus function:

bool IntersectsOnTorus(int x1, int w1, int y1, int h1, int x2, int w2, int y2, int h2, int domain)
{
    return AreIntersecting2d(x1, w1, y1, h1, x2, w2, y2, h2)                    // No wrapping
        || AreIntersecting2d(x1 + domain, w1, y1, h1, x2, w2, y2, h2)           // Shape 2 wraps left edge
        || AreIntersecting2d(x1, w1, y1 + domain, h1, x2, w2, y2, h2)           // Shape 2 wraps bottom edge
        || AreIntersecting2d(x1 + domain, w1, y1 + domain, h1, x2, w2, y2, h2)  // Shape 2 wraps bottom-left corner
        || AreIntersecting2d(x1, w1, y1, h1, x2 + domain, w2, y2, h2)           // Shape 1 wraps left edge
        || AreIntersecting2d(x1, w1, y1, h1, x2, w2, y2 + domain, h2)           // Shape 1 wraps bottom edge
        || AreIntersecting2d(x1, w1, y1, h1, x2 + domain, w2, y2 + domain, h2); // Shape 1 wraps bottom-left corner
}

There are other ways to write this. For the Shape 1 wrapping cases, you could also subtract the domain from the Shape 1 coordinates. I wrote it this way to keep all coordinates positive, in case that matters later, like if ints are replaced with unsigned ints in the future.

The best part of writing the code this way is that the tricky math is confined to one function, and that function only has to consider the simplest case. Every other function consists of combinations of calls to other functions that are much easier to read and check for correctness.

Answer 3

As a further answer I've found another method that maybe more efficient. It works by taking the centres of the rectangles and calculating the distance between them modulo the domain. If the centres are close enough, less than (w1 + w2) / 2, they are overlapping.

Again the modulo operator can be avoided in favour of comparisons because of the preconditions - yes, there is a measurable difference in benchmarks.

This version does however use doubles instead of ints, the int version breaks here.

// Preconditions: x1, y1, w1, h1, x2, y2, w2, h2 are between 0 and domain exclusive
bool IntersectsOnTorus(double x1, double y1, double w1, double h1, double x2, double y2, double w2, double h2, double domain)
{
    // Difference between the centres modulo domain
    double dx = (dx = x1 + w1 / 2 - x2 - w2 / 2) < 0
        ? dx + domain : dx >= domain ? dx - domain : dx;

    // Separation of centres when touching
    double sx = (w1 + w2) / 2;

    // Similar for y
    double dy = (dy = y1 + h1 / 2 - y2 - h2 / 2) < 0
        ? dy + domain : dy >= domain ? dy - domain : dy;
    double sy = (h1 + h2) / 2;

    // Return true if the absolute* difference between centres
    // is less than touching distance
    return (dx < sx || dx > domain - sx) && (dy < sy || dy > domain - sy);
}

• I'm using the span between 0 and domain as a signed number. Eg. in MOD 10 you'd have 0, 1, 2, 3, 4, -5, -4, -3, -2, -1. In this way you can avoid "date line" issues like there was in Defender arcade.

Orginal question Intersecting rectangles on a torus.