Как определить что прямоугольники пересекаются
как проверить пересекаются ли два прямоугольника
Часто при разработке различных интерфейсов возникает задача проверки пересекаются ли два заданных прямоугольника. Решение в данном случае очень простое, однако мной нигде не найденное и поэтому в очередной раз пришлось писать свой велосипед. При этом грабли на которые наступают разработчики одни и те же, а решение выдаваемые гуру на форумах работают лишь в частных случаях и не покрывают все варианты расстановки двух прямоугольников на плоскости.
Функция работает только для прямоугольников, чьи стороны параллельны осям координат. В общем-то задача сведена к проецированию сторон на оси координат и попарной проверке пересечений двух отрезков. Если две пары отрезков пересекаются между собой то значит один из прямоугольников лежит на другом. Однако здесь есть подвох: нужно проверять также случай, когда одна сторона прямоугольника №1 лежит внутри той же стороны прямоугольника №2, а другая, сторона у №2 сама лежит внутри такой же в №1. Этот случай представлен на рисунке выше, под номером 1.
Пусть есть два прямоугольника A и B.
тогда проверку на пересечение двух этих прямоугольников произведет следующая функция
а Вы думали все просто. Я тоже так думал, пока не поймал ряд вариантов, которые не подходят под решения названные на форумах. Первая половина этой «многоэтажки» проверяет все случаи, кроме первого, вторая создана специально для случая №1.
Благодаря пользователю с ником Ruslan и его комментарию узнаем, что есть еще один достаточно просто способ проверить. Нужно действовать от обратного, проверять не 1,3,4 а только 2
Просто, как дважды два. Проверяем если верхняя грань первого прямоугольника находится ниже второго, или нижняя выше верхней грани первого. Тоже самое и для оси X.
Платная консультация по вопросам 2500 руб/час
Прочитали статью и остались вопросы? Меня зовут Валерий и я её автор. С радостью объясню Вам в скайпе все затруднительные моменты, которые остались за рамками статьи!
Пересекаются эти 2 прямоугольника или нет
Для просмотра формул ваш браузер должен поддерживать MathML.
| Объявления | Последний пост | |
|---|---|---|
 | Правила и принципы форума «Высшая математика» | 28.10.2009 15:17 |
| Senior lecturer in Mathematics Linkoping (Швеция) | 04.09.2021 23:16 |
| Постдок позиция по математике в Гетеборге (Швеция) | 10.09.2021 19:11 |
Скажите, пожалуйста, формулу, что определения пересекаются эти 2 прямоугольника или нет?
Есть 2 прямоугольника на плоскости.
Мы знаем углы их поворота и координаты их 8 вершин.
Редактировалось 1 раз(а). Последний 01.03.2021 03:38.
Дело в том, что Есть игра gta vice city.
авто там прямоугольники.
Мы можем узнать угол авто и координаты всех четырех вершин(x1,y1,x2,y2,x3,y3,x4,y4)
Также мы знаем всё вышеперечисленное у другого авто.
Как определить было ли столкновения двух авто или нет?
Нужна формула.
Проверки пересекаются 2 прямоугольника или нет?
спасибо большое за Ваш ответ, я его перечитываю, пытаюсь понять.
вот мой код на с++, как проверить было ли столкновения или нет?
pos = car->m_placement.pos + car->m_placement.right * width + car->m_placement.up * length;
x = pos.x; y = pos.y;//правый верхний угол первого авто.
pos = car1->m_pHandlingData->m_vDimensions; length = pos.x; width = pos.y; height = pos.z;
length =+0.6 ; width = width / 2;
pos = car1->m_placement.pos + car1->m_placement.right * width + car1->m_placement.up * length;
ruangle_x1 = pos.x; ruangle_y1 = pos.y;//правый верхний угол второго авто.
float angle1;// переменная хранить угол авто.
angle1 = car1->GetHeading();// получить угол второго авто.
Редактировалось 1 раз(а). Последний 01.03.2021 22:14.
Алгоритм обнаружения пересечения двух прямоугольников?
Я ищу алгоритм для обнаружения пересечения двух прямоугольников (один под произвольным углом, другой только с вертикальными/горизонтальными линиями).
тестирование, если угол одного находится в другом, почти работает. Он терпит неудачу, если прямоугольники образуют крестообразную форму.
кажется хорошей идеей избегать использования наклонов линий, что потребует особых случаев для вертикальных линий.
18 ответов
стандартным методом было бы сделать разделяя тест оси (сделайте поиск google на этом).
самое интересное, что достаточно просто проверить все края двух прямоугольников. Если прямоугольники не перекрывают один из ребер, будьте разделяющей осью.
в 2D вы можете сделать это без использования склонов. Ребро просто определяется как разница между двумя вершинами, например,
вы можете получить перпендикуляр к этой, повернув его на 90°. В 2D это легко, как:
таким образом, тригонометрия или склоны не участвуют. Нормализация вектора до единичной длины также не требуется.
Если вы хотите проверить, находится ли точка на той или иной стороне линии, вы можете просто использовать скалярное произведение. знак скажет вам, на чьей вы стороне:
тест работает с любым выпуклым полигоны, кстати..
поправка: чтобы определить разделяющее ребро, недостаточно протестировать все точки одного прямоугольника против каждого края другого. Ребро-кандидат E (ниже) как таковое будет идентифицировано как разделяющее ребро, поскольку все точки в A находятся в одной полуплоскости E. Однако это не разделяющее ребро, потому что вершины Vb1 и Vb2 B также находятся в этой полуплоскости. Это был бы только разделяющий край, если бы не случай http://www.iassess.com/collision.png
в основном посмотрите на следующее изображение:
Если две коробки сталкиваются, линии A и B будут перекрываться.
обратите внимание, что это должно быть сделано как на оси X, так и на оси Y, и оба должны перекрываться для столкновения прямоугольников.
есть хорошая статья в gamasutra.com который отвечает на вопрос (Изображение от статья.) Я сделал подобный алгоритм 5 лет назад, и я должен найти свой фрагмент кода, чтобы опубликовать его здесь позже
поправка: Теорема о разделяющей оси гласит, что две выпуклые формы не перекрытие, если существует разделительная ось (т. е. та, где проекции, как показано не перекрытие). Таким образом,» разделительная ось существует » = > «нет перекрытия». Это не двусмысленность, поэтому вы не можете заключить обратное.
ответ m_pGladiator правильный, и я предпочитаю его. разделяя испытание оси самый простой и стандартный метод для обнаружения перекрытия прямоугольника. Линию, для которой интервалы проекции не перекрываются, мы называем разделяющей оси. Решение Нильса Пайпенбринка слишком общее. Это использовать скалярное произведение чтобы проверить, является ли одна форма полностью на одной стороне края другой. Это решение фактически может индуцировать N-реберные выпуклые многоугольники. Тем не менее, это не optmized для двух прямоугольников.
критическая точка ответа m_pGladiator заключается в том, что мы должны проверить проекцию двух прямоугольников на обе оси (x и y). Если две проекции перекрываются, то можно сказать, что эти два прямоугольника перекрываются. Поэтому в комментариях выше ответ m_pGladiator ошибочны.
для простой ситуации, если два прямоугольника не поворачивается, представляем прямоугольник со структурой:
мы называем прямоугольник A, B с Квадра, rectB.
если один из двух прямоугольников вращаются, Для определения проекции их на оси x и y могут потребоваться некоторые усилия. Определите struct RotatedRect следующим образом:
разница в том, как ширина теперь немного отличается: widthA ‘ для rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB ‘ для прямой кишки: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)
Проверьте, пересекаются ли какие-либо линии из одного прямоугольника с линиями из другого. Наивное пересечение отрезка линии легко закодировать.
Если вам нужна больше скорости, то предварительные алгоритмы для пересечения отрезка линии (стреловидност-линии). См.http://en.wikipedia.org/wiki/Line_segment_intersection
выход один-использовать то, что называется не пригодный полигон. Этот многоугольник вычисляется из двух многоугольников (концептуально путем скольжения одного вокруг другого) и определяет область, для которой многоугольники перекрываются с учетом их относительного смещения. Как только у вас есть этот NFP, вам просто нужно сделать тест включения с точкой, заданной относительным смещением двух полигонов. Этот тест включения быстр и легок но вы должны создать NFP сперва.
есть поиск нет Установите полигон в интернете и посмотрите, можете ли вы найти алгоритм для выпуклых полигонов (он становится намного сложнее, если у вас есть вогнутые полигоны). Если вы ничего не можете найти, напишите Мне по адресу howard dot J dot may gmail dot com
вот что я думаю, будет заботиться обо всех возможных случаях. Выполните следующие тесты.
Если вышеуказанные 2 теста возвращают false, то эти 2 прямоугольника не перекрываются.
Получить точки пересечения из 2 прямоугольников
Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.
Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.
постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.
Решение
Постскриптум Как обычно, мелкие детали будут зависеть от того, нужно ли учитывать трогательный прямоугольники как пересекающиеся.
Другие решения
Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:
Итак, как мы можем видеть из изображения, если x3, y3 больше или равно x1, y1 и меньше или равно x2, y2, то оно находится внутри первого прямоугольника, аналогично вам нужно будет проверить, попадает ли x4, y4 внутрь диапазон от х1, у1 до х2, у2, а также.
если оба условия оказываются верными, то вы можете быть уверены, что второй прямоугольник полностью охватывается первым. 
Вам нужно будет проверить и обратное, если узнаете, что внутри, что важно для вас.
Также необходимо, чтобы прямоугольники были выровнены по оси, иначе это не будет работать надежно.
Дайте мне знать, если вам нужно больше подробностей, хотя я думаю, что быстрый поиск в Google очень легко раскроет для вас более подробную информацию, но дайте мне знать, и я могу сделать учебник по столкновению с прямоугольником, если хотите.
Более подробно:
Чтобы выяснить, имеют ли прямоугольники пересечения, вы можете проверить координаты их определяющих точек, для наших целей мы будем использовать координаты верхнего левого и нижнего правого углов.
Мы можем использовать класс, чтобы сделать это проще для нас, и для максимального удобства использования кода мы можем использовать 2d Vector и 2d Point:
2dVectorPoint.h
Используемый код адаптирован из Вот чтобы сохранить мои пальцы.
Тогда мы можем использовать это, чтобы легко сравнить:
мы можем определить прямоугольник 1 как имеющий P1 и P2 как его границы и прямоугольник 2 как имеющий P3 и P4 как его границы, давая нам следующее сравнение:
Это вернет истинное значение для любого экземпляра пересечения или для прямоугольника 1, полностью охватывающего прямоугольник 2.
Чтобы проверить только пересечения, просто удалите проверку на равенство (возьмите все = из вышеприведенного уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.
Скажем, у блока есть радиус X и радиус Y (я знаю, что его нет, но этот термин здесь полезен).
Теперь, если прямоугольные средние точки находятся дальше, чем сумма их радиусов в соответствующем направлении — они не сталкиваются.
В противном случае они делают — этого намека должно хватить.
Теперь вы должны быть в состоянии выполнить задание.
ОБНОВИТЬ:
Хорошо — давайте решим это для 1D — позже вы решите это для 2D. Посмотрите на этот кусок … искусства 😉
Вы видите 2 сегмента — теперь некоторые расчеты:
Теперь, как проверить, происходит ли столкновение? Как я уже сказал, если сумма «радиусов» меньше расстояния сегментов — столкновения нет:
Теперь ваша задача — вычислить пересечение / общую часть в 1D и 2D. Теперь все зависит от вас (вы можете прочитать ответ Андрея).
Здесь та же самая ситуация, но в 2D — две одномерные ситуации:
Вы можете иметь дело с x а также y Направление отдельно.
Если в обоих направлениях перекрытие, то перекрытие прямоугольника. Вы можете найти координаты, отсортировав x а также y координаты и выбрав два средних.