Como comparar a intersecção de dois intervalos · lvendrame

Um dos problemas que enfrentei muitas vezes foi a comparação de dois intervalos, sejam eles datas ou pontos no espaço, o que, aliás, é o que tratamos como uma colisão nos jogos.

Quando paramos para analisar o problema, de início, parecerá algo complexo, já que o natural seria realizar 8 comparações para garantir que a colisão ocorra.

Vamos ao exemplo abaixo para uma melhor compreensão: Suponhamos que a reunião A comece às 13:30 e termine às 15:30. Uma outra reunião, B, está sendo agendada para o horário das 15:00 até às 16:00. Como verificamos computacionalmente que elas não se intersectam uma com a outra? Na ilustração abaixo, temos todas as interseções possíveis que deveríamos verificar:

A1 = A-inicial,  A2 = A-final, B1 = B-inicial, B2 = B-final
        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
        |             |
        |             |

Dadas as condições acima, nosso algoritmo ficaria algo como:

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 verificarInterseccao(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 existeInterseccao = verificarInterseccao(a1, a2, b1, b2);
// true

Porém, podemos, em vez de analisar os casos onde existe a interseção, analisar os casos onde não existe a interseção:

A1 = A-inicial,  A2 = A-final, B1 = B-inicial, B2 = B-final
        A1            A2
        |             |
B1---B2 |             |                B2 < A1
        |             |
        |             | B1---B2        B1 > A2
        |             |

Com essa nova análise, podemos reescrever o algoritmo da seguinte forma:

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 verificarInterseccao(a1, a2, b1, b2) {
    if(b2 < a1)
        return false;
    if(b1 > a2)
        return false;
        
    return true;
}

const existeInterseccao = verificarInterseccao(a1, a2, b1, b2);
// true

Perceba que, com esse novo olhar sobre o problema, diminuímos de 8 comparações para apenas 2. Também note que agora o retorno de falso para as comparações ocorrerá antes, diferente do algoritmo anterior que retornava verdadeiro. Outro ponto importante é que cada período esteja ordenado do menor para o maior valor na hora da comparação.

Embora este caso, na maioria das aplicações, signifique apenas uma simplificação do problema, já que esta comparação não ocorre a todo momento, no caso de jogos, é um bom ganho de desempenho, já que estas comparações ocorrem aos montes a cada iteração do main loop, comparando os intervalos de objetos nos eixos X, Y e, no caso do 3D, eixo Z.

Portanto, quando se deparar com problemas desta espécie, tente desenhar um diagrama com possibilidades tanto para a verdade quanto para a não verdade e veja o que mais vale a pena ser utilizado na construção do algoritmo.

Muito bom!

Só pra complementar, a função também poderia ser assim:

function verificarInterseccao(a1, a2, b1, b2) {
    return !((b2 < a1) || (b1 > a2));
}

Ou seja, se uma das condições for verdade, retornará falso. Mas quando eu tenho algo como !(cond1 || cond2), eu posso trocar para (!cond1) && (!cond2) - as condições se invertem e troco o || por &&. Portanto, ficaria assim:

function verificarInterseccao(a1, a2, b1, b2) {
    return b2 >= a1 && b1 <= a2;
}

Como o operador && é short circuit, se a primeira condição não for verdadeira, ele nem testa a segunda, mantendo o funcionamento de já parar se o primeiro caso for falso.

Por fim, existe uma explicação parecida aqui, vale a leitura.