Проверка точек пересечения между двумя прямоугольниками?

Если у меня есть два прямоугольника, позиции которых определены с использованием двух 2D-векторов (т.е. вверху слева, внизу справа), как я могу проверить точки, которые они пересекают?


c++ testing intersection
person meds    schedule 04.12.2009    source источник

Ответы (4)


arrow_upward
4
arrow_downward

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

Пересечение rect1 = (l1, t1, r1, b1) и rect2 = (l2, t2, r2, b2) снова представляет собой прямоугольник:

rectIntersection = ( max(l1, l2), max(t1, t2), min(r1, r2), min(b1, b2) )

rectIntersection, конечно, пуст, если left >= right || top >= bottom предполагает, что прямоугольник является левым/верхним и правым/нижним.

Прямоугольники пересекаются, если

l1 < r2 && l2<r1 && t1<b2 && t2<t1
person Sebastian    schedule 04.12.2009
comment
Версии разделительной оси более эффективны, эта версия означает, что вам всегда придется делать четыре сравнения. - person Andreas Brinck; 04.12.2009
comment
+ Вам нужно будет сделать хотя бы один дополнительный тест, чтобы увидеть, пуст ли результирующий прямоугольник. То есть в этой версии 5-6 условностей по сравнению с 1-4 для SAT-версии. - person Andreas Brinck; 04.12.2009
comment
Я действительно думаю, что постер действительно хочет получить результирующий набор пересекающихся точек, а не только тест, если они пересекаются. В зависимости от контекста может быть лучше вычислить пересечение и утверждать, что оно не пусто. - person Sebastian; 04.12.2009
comment
Довольно часто код работает быстрее на современных процессорах, если вы не выполняете ветвление. Макс и Мин часто превращаются в фсел. Таким образом, в приведенном выше коде seudo нет ветвления кода. Единственный реальный ответ - это, конечно, профиль. - person Charles Beattie; 04.12.2009
comment
Извините, что не прочитал вопрос должным образом, действительно ли процессоры Intel имеют fsel, я думал, что это инструкция PPC/CELL? (Visual Studio 2008 генерирует код ветвления для a < b ? a : b) - person Andreas Brinck; 04.12.2009
comment
Даже если fsel не используется, современный компилятор вполне способен оптимизировать такой код за вас. Если только не мешать, т. В любом случае, это решение дает правильные результаты (в отличие от некоторых других). При необходимости его можно оптимизировать позже. - person Tomek Szpakowicz; 04.12.2009
comment
Не быстрее ли просто проверить, представляет ли r3 - l3 < 0 || b3 - t3 < 0, если l3, t3, r3, b3 результат промежуточного пересечения? - person Philip Kamenarsky; 24.08.2011

arrow_upward
2
arrow_downward

Предполагая, что источник находится на left-top экрана.

Если проверить, меньше ли верхний левый угол одного прямоугольника (x3,y3), чем нижний правый угол другого прямоугольника (x2,y2), то они пересекаются.

Точки (x2,|y2-y3|) и (|x2-x3|,y2).

Это для прямоугольника1 и прямоугольника2 справа от прямоугольника1.

Применить инверсию к левому переносу.

person tomkaith13    schedule 04.12.2009

arrow_upward
1
arrow_downward

Два прямоугольника перекрываются, если есть хотя бы одна внутренняя точка X, Y, общая для обоих. Пусть первый прямоугольник будет {T1, L1, B1, R1}, а второй {T2, L2, B2, R2} (верхний, левый, нижний, правый). Теперь следует, что (X>L1) и (X<R1) и (Y>T1) и (Y<B1), и аналогично для прямоугольника 2. Из (X>L1) и (X<R2) следует (L1<R2). Точно так же (L2<R1), (T1<B2) и (T2<B1).

Таким образом, эти 4 условия необходимы. Не совсем очевидно, что их также достаточно, но это тоже так.

person MSalters    schedule 04.12.2009

arrow_upward
0
arrow_downward

Если вас больше интересует функция для выполнения работы, чем реализация алгоритма,
ознакомьтесь с Функция IntersectRect в Windows.

person Nick Dandoulakis    schedule 04.12.2009