Как определить, находится ли определенный диапазон (частично) в другом диапазоне?

Question

Допустим, у меня есть два квадрата, и я знаю их позиции, красный и синий квадрат:

redTopX;
redTopY;
redBotX;
redBotY;
blueTopX;
blueTopY;
blueBotX;
blueBotY;

Теперь я хочу проверить, находится ли квадратный синий (частично) внутри (или вокруг)красный квадратЭто может происходить во многих ситуациях, как вы можете видеть на этом изображении, которое я создал, чтобы лучше проиллюстрировать мою ситуацию: альтернативный текст http://www.feedpostal.com/etc/ranges.gif

Обратите внимание, что всегда есть только один синий и один красный квадрат, я только что добавилкратный, так что мне не пришлось перерисовывать 18 раз.

Моя оригинальная логика была проста, я бы проверил все углы квадрата синего цвета и посмотрел, есть ли какие-либо из них внутри квадрата красного цвета:

if (
((redTopX >= blueTopX) && (redTopY >= blueTopY) && (redTopX <= blueBotX) && (redTopY <= blueBotY)) || //top left
((redBotX >= blueTopX) && (redTopY >= blueTopY) && (redBotX <= blueBotX) && (redTopY <= blueBotY)) || //top right
((redTopX >= blueTopX) && (redBotY >= blueTopY) && (redTopX <= blueBotX) && (redBotY <= blueBotY)) || //bottom left
((redBotX >= blueTopX) && (redBotY >= blueTopY) && (redBotX <= blueBotX) && (redBotY <= blueBotY)) //bottom right
) {
    //blue resides in red
}

К сожалению, в этой логике есть пара недостатков.Например, что, если красный цвет окружает синий (как в ситуации 1)?

Я думал, что это будет довольно легко, но у меня проблемы с придуманием хорошего способа охватить все эти ситуации ... может кто-нибудь помочь мнездесь?

С уважением, Том

Answer 1

Тест, который проверяет, находится ли красный прямоугольник полностью снаружи синий прямоугольник выглядит следующим образом

bool outside = 
  redBotX > blueTopX || redTopX < blueBotX || 
  redBotY > blueTopY || redTopY < blueBotY;

Теперь, отрицание этого скажет вам, пересекает ли красный прямоугольник синий прямоугольник

bool intersects =
  !(redBotX > blueTopX || redTopX < blueBotX || 
    redBotY > blueTopY || redTopY < blueBotY);

Если хотите, вы можете применить правило Де Моргана и переписать его как

bool intersects =
  redBotX <= blueTopX && redTopX >= blueBotX && 
  redBotY <= blueTopY && redTopY >= blueBotY;

Конечно, в приведенных выше тестах предполагается, что координаты "нормализованы *, т.е.

assert(redBotX <= redTopX && redBotY <= redTopY);
assert(blueBotX <= blueTopX && blueBotY <= blueTopY);

Кроме того, сравнение может быть строгим или не строгим в зависимости от того, считаете ли вы касание прямоугольников пересекающимися или нет.

РЕДАКТИРОВАТЬ: Я вижу, что вы используете другое соглашение для координат прямоугольника: Top является нижней координатой и Bot является более высокой, т.е.

assert(redTopX <= redBotX && redTopY <= redBotY);
assert(blueTopX <= blueBotX && blueTopY <= blueBotY);

Для обработки этого случая вам просто нужно поменять координаты Bot и Top при любых условиях. Например, последний теперь будет выглядеть следующим образом

bool intersects =
  redTopX <= blueBotX && redBotX >= blueTopX && 
  redTopY <= blueBotY && redBotY >= blueTopY;

Answer 2

Предполагая, что оба квадрата выровнены, как вы указали:

Квадраты пересекаются, если выполняются все следующие условия:

1. Сторона слева красного цвета слева стороны справа синего цвета.
2. Сторона справа красного цвета справа стороны слева синего цвета.
3. верх красного цвета выше низ синего цвета.
4. низ Красного * на ниже верх Синего.

(Убедите себя, что это правда!)

Answer 3

Для более многомерных диапазонов или если вы хотите проверить много диапазонов, может быть целесообразно сохранить ваши диапазоны (например, их центры) в R дереве и найти его, где углы ваш диапазон.

Answer 4

for each blue corner:
  if corner is between all four red sides:
    return true
return false

Answer 5

if (blueTopY < redBotY) return (0);
if (blueBotY > redTopY) return (0);
if (blueBotX < redTopX) return (0);
if (blueTopX > redBotX) return (0);
return (1); // there must clash

Answer 6

Одна формула для пересечения двух прямоугольников будет

! ( (redTopX > blueBotX) || (blueTopX > redBotX) || (redTopY < blueBotY) || (blueTopY < redBotY))

Вы можете использовать теорему Деморгана для упрощения.