How to compare the intersection of two intervals
Tags: programming, algorithms, gamedev, tutorial
Published: 2024-02-28 12:50:16

One of the problems I have often faced is comparing two intervals, whether they are dates or points in space, which, by the way, is what we refer to as a collision in games.

When we stop to analyze the problem at first, it may seem complex, as the natural approach would be to perform 8 comparisons to ensure that a collision occurs.

Let's look at the example below for a better understanding: Suppose meeting A starts at 13:30 and ends at 15:30. Another meeting, B, is being scheduled from 15:00 to 16:00. How do we computationally verify that they do not intersect with each other? In the illustration below, we have all possible intersections that we should check:
```shell
A1 = Start of A, A2 = End of A, B1 = Start of B, B2 = End of B
        A1            A2
        |             |
    B1-----B2         |                B1 <= A1 && B2 >= A1
        |             |
    B1-------------------B2            B1 <= A1 && B2 >= A2
        |             |
        |         B1-----B2            B1 <= A2 && B2 >= A2
        |             |
        |  B1-----B2  |                B1 >= A1 && B2 <= A2
        |             |
        |             |
        
```

Given the conditions above, our algorithm would look something like this:
```javascript
const a1 = new Date(2024, 02, 28, 13, 30);
const a2 = new Date(2024, 02, 28, 15, 30);
const b1 = new Date(2024, 02, 28, 15, 00);
const b2 = new Date(2024, 02, 28, 16, 00);

function verifyIntersection(a1, a2, b1, b2) {
    if(b1 <= a1 && b2 >= a1)
        return true;
    if(b1 <= a1 && b2 >= a2)
        return true;
    if(b1 <= a2 && b2 >= a2)
        return true;
    if(b1 >= a1 && b2 <= a2)
        return true;
        
    return false;
}

const doesIntersectionExist = verifyIntersection(a1, a2, b1, b2);
// true        
```

However, instead of analyzing cases where there is an intersection, we can analyze cases where there is no intersection:

```shell
A1 = Start of A, A2 = End of A, B1 = Start of B, B2 = End of B
        A1            A2
        |             |
B1---B2 |             |                B2 < A1
        |             |
        |             | B1---B2        B1 > A2
        |             |
        
```

With this new analysis, we can rewrite the algorithm as follows:
```javascript
const a1 = new Date(2024, 02, 28, 13, 30);
const a2 = new Date(2024, 02, 28, 15, 30);
const b1 = new Date(2024, 02, 28, 15, 00);
const b2 = new Date(2024, 02, 28, 16, 00);

function verifyIntersection(a1, a2, b1, b2) {
    if(b2 < a1)
        return false;
    if(b1 > a2)
        return false;
        
    return true;
}

const doesIntersectionExist = verifyIntersection(a1, a2, b1, b2);
// true        
```

Notice that with this new perspective on the problem, we've reduced from 8 comparisons to just 2. Also, note that now the return of false for comparisons will occur earlier, unlike the previous algorithm that returned true. Another important point is that each period should be ordered from the lowest to the highest value at the time of comparison.

Although in most applications, this case just simplifies the problem, as this comparison does not occur all the time, in the case of games, it is a significant performance gain, as these comparisons occur in large numbers at each iteration of the `main loop`, comparing the intervals of objects on the X, Y axes, and in the case of 3D, the Z axis.

Therefore, when faced with such problems, try drawing a diagram with possibilities for both truth and falsehood and see what is most worthwhile to be used in algorithm construction.