Executando verificação de segurança...
20

Como comparar a intersecção de dois intervalos

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.

4

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.

1

Muito bom, especialmente pela aplicação dos teoremas de Morgan para simplificação boleana, porém apesar de simplificar a expressão e ser muito útil para a construção de circuitos, temos que tomar cuidado pois prejudica a leitura do código, contudo, dependendo do cenário e de quantas comparações serão evitadas, é um ótimo recurso. Neste meu exemplo quis trazer uma explicação mais básica e didática.

0

Partindo da premissa de que os intervalos foram ordenados de forma crescente pela data inicial e que a data final sempre será maior que a data inicial, pode-se concluir que b2 sempre será maior que a1 e assim é possível omitir essa comparação, restando apenas:

function verificarInterseccao(a2, b1) {
    return b1 <= a2;
}