| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Проверить, пересекаются ли два прямоугольника |
| Автор: Kostt 28.10.2007, 08:51 |
| Как быстро проверить, пересекаются ли два плоских прямоугольника? Или по крайней мере, быстро установить факт того, что они не пересекаются (в рамках моей задачи, они пересекаться будут редко) |
| Автор: maxim1000 28.10.2007, 09:54 |
| стороны параллельны координатным осям или могут быть направлены произвольно? |
| Автор: ksili 28.10.2007, 10:22 |
| Если они пересекаются, значит пересекаются их стороны. Смотри в сторону пересечения отрезков. надо будет сделать 15 попарных проверок (максимум). Вообще 16 должно быть проверок, но если подумать, то одним отрезком они точно пересекаться не могут (то есть, я так понимаю, у прямоугольников должна быть общая площадь) |
| Автор: Kostt 28.10.2007, 11:56 |
| Стороны параллельны осям координат. Попарные проверки слишком долго, наверняка есть способ проще |
| Автор: ksili 28.10.2007, 12:22 |
| Если сторону параллельны осям, то вообще ничего сложного не вижу. Пусть прямоугольники заданы как коорд-ты противоположных углов - левый нижний и правый верхний: Прям1=(x11,y11,x12,y12), Прям2=(x21,y21,x22,y22) Тогда если x11<x22 и x12>x21 и y11<y22 и y12>y21, то пересечение есть |
| Автор: paladin80 7.6.2008, 09:14 |
| ksili, спасибо большое за условия! Все работает. |