Как найти пересечение прямоугольников по координатам

Как найти площадь пересечения двух прямоугольников?

Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно:

(x1,y1) — левая нижняя точка первого прямоугольника

(x2,y2) — правая верхняя точка первого прямоугольника

(x3,y3) — левая нижняя точка второго прямоугольника

(x4,y4) — правая верхняя точка второго прямоугольника

И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.

Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:

Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).

Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):

Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

UniLecs #Task. Rectangle intersection

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

Входные данные:

• (x1,y1) — координаты левого нижнего угла 1го прямоугольника;
• (x2,y2) — координаты правого верхнего угла 1го прямоугольника;
• (x3,y3) — координаты левого нижнего угла 2го прямоугольника;
• (x4,y4) — координаты правого верхнего угла 2го прямоугольника;

Примечание: координаты — целые числа в диапазоне [−10000, 10000].

Вывод: площадь пересечения данных прямоугольников.

Пример:

Разбор

Задачу можно решить следующим способом:

1. Сначала нужно найти координаты пересечения прямоугольников:

• левая граница пересечения это максимум из левых границ данных прямоугольников,
• правая граница — минимум из правых границ,
• нижняя граница — максимум из нижних границ прямоугольников,
• верхняя граница — минимум из верхних границ.

2. Затем посчитаем длины сторон прямоугольника и перемножим их.

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

Получить точки пересечения из 2 прямоугольников

Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.

Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.

постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.

Решение

Если входные прямоугольники нормализованы, то есть вы уже знаете, что x1 < x2 , y1 < y2 (и то же самое для второго прямоугольника), тогда все, что вам нужно сделать, это рассчитать

и это даст вам ваше пересечение в виде прямоугольника (x5, y5)-(x6, y6) , Если исходные прямоугольники не пересекаются, результатом будет «вырожденный» прямоугольник (с x5 >= x6 и / или y5 >= y6 ), который вы можете легко проверить.

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

Другие решения

Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:

Итак, как мы можем видеть из изображения, если 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 Направление отдельно.

Предположим, что x1 <= x3 (первая коробка как минимум так же далеко, как и вторая). Тогда есть совпадение, если и только если x1 <= x3 <= x2 ,

Аналогично предположим y1 <= y3 (первая коробка, по крайней мере, так же далеко, как и вторая). Тогда есть совпадение, если и только если y1 <= y3 <= y2 ,

Если в обоих направлениях перекрытие, то перекрытие прямоугольника. Вы можете найти координаты, отсортировав x а также y координаты и выбрав два средних.

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

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

Проверка, находится ли угол одного в другом, ПОЧТИ работает. Не получится, если прямоугольники образуют крестообразную форму.

Кажется хорошей идеей избегать использования наклонов линий, которые потребовали бы особых случаев для вертикальных линий.

20 ответов

Стандартным методом было бы выполнение теста разделительной оси (выполните поиск в Google).

• Два объекта не пересекаются, если вы можете найти линию, разделяющую два объекта. например объекты / все точки объекта находятся по разные стороны от линии.

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

В 2D вы можете сделать это без использования откосов. Ребро просто определяется как разница между двумя вершинами, например

Вы можете получить перпендикуляр к нему, повернув его на 90 °. В 2D это просто:

Так что никакой тригонометрии или наклонов. Нормализация вектора к единичной длине также не требуется.

Если вы хотите проверить, находится ли точка на той или иной стороне линии, вы можете просто использовать скалярное произведение. знак подскажет, на чьей вы стороне:

Теперь сравните все точки прямоугольника A с краями прямоугольника B и наоборот. Если вы обнаружите разделяющую кромку, объекты не пересекаются (при условии, что все другие точки в B находятся по другую сторону от проверяемой кромки — см. Рисунок ниже). Если вы не обнаружите разделяющего края, либо прямоугольники пересекаются, либо один прямоугольник содержится в другом.

Тест работает с любыми выпуклыми многоугольниками, кстати.

Поправка: чтобы определить разделяющую кромку, недостаточно проверить все точки одного прямоугольника относительно каждого края другого. Ребро-кандидат E (ниже) как таковое будет идентифицировано как разделяющее ребро, поскольку все точки в A находятся в одной полуплоскости E. Однако это не разделяющее ребро, потому что вершины Vb1 и Vb2 из B также находятся в этой полуплоскости. Это было бы только разделительным краем, если бы этого не было. http://www.iassess.com/collision.png

В основном посмотрите на следующую картинку:

Если два прямоугольника сталкиваются, линии A и B будут перекрываться.

Обратите внимание, что это нужно будет сделать как по оси X, так и по оси Y, и обе должны перекрываться, чтобы прямоугольники столкнулись.

На gamasutra.com есть хорошая статья, которая отвечает на этот вопрос (рисунок из статьи). Я использовал аналогичный алгоритм 5 лет назад, и мне нужно найти фрагмент кода, чтобы опубликовать его здесь позже.

Поправка . Теорема о разделяющей оси утверждает, что две выпуклые формы не перекрываются, если существует разделяющая ось (т. е. та, где выступы, как показано, не перекрывать). Итак, «Разделительная ось существует» => «Нет перекрытия». Это не двусмысленный вывод, поэтому вы не можете сделать обратный вывод.

В Какао вы можете легко определить, пересекает ли прямоугольник selectedArea прямоугольник вашего повернутого кадра NSView. Вам даже не нужно рассчитывать полигоны, нормали и тому подобное. Просто добавьте эти методы в свой подкласс NSView. Например, пользователь выбирает область в супервизоре NSView, затем вы вызываете метод DoesThisRectSelectMe, передавая прямоугольник selectedArea. API convertRect: выполнит эту работу. Тот же трюк работает, когда вы щелкаете NSView, чтобы выбрать его. В этом случае просто переопределите метод hitTest, как показано ниже. API convertPoint: выполнит эту работу 😉

Ответ m_pGladiator правильный, и я предпочитаю его. Тест разделительной оси — это самый простой и стандартный метод обнаружения перекрытия прямоугольников. Линия, для которой интервалы проекции не перекрываются, мы называем разделительной осью . Решение Нильса Пипенбринка слишком общее. Он использует скалярное произведение , чтобы проверить, находится ли одна фигура полностью с одной стороны от края другой. Это решение действительно могло бы создать выпуклые многоугольники с n ребрами. Однако он не подходит для двух прямоугольников.

Критическая точка ответа m_pGladiator заключается в том, что мы должны проверить проекцию двух прямоугольников на обе оси (x и y). Если две проекции перекрываются, то можно сказать, что эти два прямоугольника перекрываются. Таким образом, комментарии выше к ответу m_pGladiator неверны.

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

Мы называем прямоугольник A, B как rectA, rectB.

Если любой из двух прямоугольников повернут, может потребоваться некоторое усилие, чтобы определить их проекцию на оси x и y. Определите структуру RotatedRect следующим образом:

Разница в том, как ширина теперь немного отличается: widthA ‘для rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB ‘для rectB: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

Может ссылаться на PPT GDC (Конференция по разработке игр 2007) www.realtimecollisiondetection.net/pubs/GDC07_Eric

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

Если вам нужно больше скорости, есть продвинутые алгоритмы пересечения отрезков линии (sweep-line). См. http://en.wikipedia.org/wiki/Line_segment_intersection.

Одно из решений — использовать что-то, что называется «Не подходит многоугольник». Этот многоугольник вычисляется из двух многоугольников (концептуально путем скольжения друг вокруг друга) и определяет область, для которой многоугольники перекрываются с учетом их относительного смещения. Когда у вас есть этот NFP, вам просто нужно провести тест на включение с точкой, заданной относительным смещением двух полигонов. Этот тест на включение выполняется быстро и легко, но сначала вам нужно создать NFP.

Поищите в Интернете запрос «Не подходит многоугольник» и посмотрите, сможете ли вы найти алгоритм для выпуклых многоугольников (он становится НАМНОГО сложнее, если у вас есть вогнутые многоугольники). Если вы ничего не можете найти, напишите мне по адресу howard dot J dot may gmail dot com

принятый ответ о тесте на разделительную ось был очень показательным, но я все же чувствовал, что это нетривиально применять. Я поделюсь псевдокодом, который, как я думал, сначала «оптимизируется» с помощью теста ограничивающего круга (см. этот другой ответ), если это может помочь другим людям. Я рассмотрел два прямоугольника A и B одинакового размера (но общую ситуацию рассмотреть несложно).

1 Тест ограничивающего круга:

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

2 Испытание разделительной оси

Рассмотрим один прямоугольник. Прокрутите его по вершинам V (i).

Вычислите вектор Si + 1: V (i + 1) — V (i).

Рассчитайте вектор Ni, используя Si + 1: Ni = (-Si + 1.y, Si + 1.x). Этот вектор — синий на изображении. Знак скалярного произведения между векторами от V (i) до других вершин и Ni будет определять разделяющую ось (пурпурная пунктирная линия).

Вычислите вектор Si-1: V (i-1) — V (i). Знак скалярного произведения между Si-1 и Ni будет определять положение первого прямоугольника относительно разделяющей оси. В примере на картинке они идут в разные стороны, поэтому знак будет отрицательным.

Проходим цикл по всем j-м вершинам второго квадрата и вычисляем вектор Sij = V (j) — V (i).

Если для любой вершины V (j) знак скалярного произведения вектора Sij с Ni такой же, как и у скалярного произведения вектора Si-1 с Ni, это означает, что обе вершины V (i) и V (j ) находятся по одну сторону от пурпурной пунктирной линии, поэтому вершина V (i) не имеет разделяющей оси. Таким образом, мы можем просто пропустить вершину V (i) и повторить для следующей вершины V (i + 1). Но сначала обновляем Si-1 = — Si + 1. Когда мы достигаем последней вершины (i = 4), если мы не нашли разделяющую ось, мы повторяем для другого прямоугольника. И если мы все еще не находим разделительную ось, это означает, что разделительной оси нет и оба прямоугольника сталкиваются.

Если для данной вершины V (i) и всех вершин V (j) знак скалярного произведения вектора Sij с Ni отличается от знака скалярного произведения вектора Si-1 с Ni (как показано на изображении), это означает мы обнаружили, что разделяющая ось и прямоугольники не пересекаются.

Вы можете найти код в Python здесь.

Примечание. В этом другом ответе они также предлагают для оптимизации попробовать перед проверкой разделяющей оси, находятся ли вершины одного прямоугольника внутри другого. как достаточное условие для столкновения. Однако в своих испытаниях я обнаружил, что этот промежуточный шаг на самом деле менее эффективен.

Вот что, я думаю, поможет во всех возможных случаях. Сделайте следующие тесты.

1. Убедитесь, что любая из вершин прямоугольника 1 находится внутри прямоугольника 2 и наоборот. Каждый раз, когда вы находите вершину, которая находится внутри другого прямоугольника, вы можете сделать вывод, что они пересекаются, и прекратить поиск. Это позаботится о том, чтобы один прямоугольник полностью находился внутри другого.
2. Если вышеуказанный тест не дает результатов, найдите точки пересечения каждой линии одного прямоугольника с каждой линией другого прямоугольника. Как только точка пересечения найдена, проверьте, находится ли она внутри воображаемого прямоугольника, созданного соответствующими 4 точками. Когда такая точка будет найдена, сделайте вывод, что они пересекаются, и прекратите поиск.

Если два вышеуказанных теста возвращают false, то эти два прямоугольника не перекрываются.

Если вы используете Java, все реализации интерфейса Shape имеют пересекает метод, который принимает прямоугольник.