Olá meus amigos nerds. Hoje vamos fazer um algoritmo para detectar se dois retângulos se interceptam ou não. Já que é isso que o problema 19958. Detectando Colisões nos pede para fazer. Mais especificamente, dados dois retângulos, que tem seus lados paralelos aos eixos, determinar se há alguma interseção entre eles.
Solução
O caso geral desse problema, que é determinar se dois polígonos tem pontos de interseção é bem complexo. Para nos ajudar, o problema trata apenas de retângulos e ainda fixa que seus lados são paralelos aos eixos. Ai fica fácil né!
O problema nos fornece os cantos inferior esquerdo e superior direito de cada retângulo. Vamos tentar estabelecer as condições para que os dois retângulos não possam se interceptar.
Caso o canto superior direito de um dos retângulos esteja 'atráz' do canto inferior esquerdo do outro não há como haver interseção pois nesse caso um retângulo 'termina' antes que o outro comece. Da mesma forma, se o canto superior direito de um dos retângulos estiver 'abaixo' do canto inferior esquerdo do outro um dos retângulos terá 'terminado' antes do outro começar. Pensando nas coordenadas x,y desses pontos teríamos (sendo a e b os retângulos):
if (a_sup_dir_x < b_inf_esq_x ||
a_sup_dir_y < b_inf_esq_y ||
b_sup_dir_x < a_inf_esq_x ||
b_sup_dir_y < a_inf_esq_y )
responda não
A condição acima é necessária. Agora vou mostrar que ela é suficiente. Observe que na situação dos dois cantos superiores da direita estarem no sub espaço acima e a direita dos cantos inferiores, os seguimentos (a_inf_esq, a_sup_dir) e (b_inf_esq, b_sup_dir) seriam tanto diagonais do retângulo formado pelos pontos (a_inf_esq, b_sup_dir, a_sup_dir, b_inf_esq) quanto dos retângulos originais, mas como as diagonais de um retângulo sempre se interseptam, resulta que esse ponto pertencerá a uma diagonal de cada um dos retângulos a e b e assim eles também se interceptam.
O problema nos fornece os cantos inferior esquerdo e superior direito de cada retângulo. Vamos tentar estabelecer as condições para que os dois retângulos não possam se interceptar.
Caso o canto superior direito de um dos retângulos esteja 'atráz' do canto inferior esquerdo do outro não há como haver interseção pois nesse caso um retângulo 'termina' antes que o outro comece. Da mesma forma, se o canto superior direito de um dos retângulos estiver 'abaixo' do canto inferior esquerdo do outro um dos retângulos terá 'terminado' antes do outro começar. Pensando nas coordenadas x,y desses pontos teríamos (sendo a e b os retângulos):
if (a_sup_dir_x < b_inf_esq_x ||
a_sup_dir_y < b_inf_esq_y ||
b_sup_dir_x < a_inf_esq_x ||
b_sup_dir_y < a_inf_esq_y )
responda não
A condição acima é necessária. Agora vou mostrar que ela é suficiente. Observe que na situação dos dois cantos superiores da direita estarem no sub espaço acima e a direita dos cantos inferiores, os seguimentos (a_inf_esq, a_sup_dir) e (b_inf_esq, b_sup_dir) seriam tanto diagonais do retângulo formado pelos pontos (a_inf_esq, b_sup_dir, a_sup_dir, b_inf_esq) quanto dos retângulos originais, mas como as diagonais de um retângulo sempre se interseptam, resulta que esse ponto pertencerá a uma diagonal de cada um dos retângulos a e b e assim eles também se interceptam.
Nenhum comentário:
Postar um comentário