Я ищу алгоритм, чтобы определить, пересекаются ли два прямоугольника (один под произвольным углом, другой только с вертикальными / горизонтальными линиями).
Тестирование, если угол одного находится в другом, ПОЧТИ работает. Сбой, если прямоугольники образуют крестообразную форму.
Кажется хорошей идеей избегать использования наклонов линий, что потребовало бы особых случаев для вертикальных линий.
Ответы:
Стандартный метод состоит в том, чтобы выполнить тест по разделительной оси (выполните поиск в 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 лет назад, и я должен найти свой фрагмент кода, чтобы опубликовать его здесь позже
Поправка : Теорема о разделяющей оси утверждает, что две выпуклые формы не перекрываются, если существует разделяющая ось (то есть та, где проекции, как показано , не перекрываются). Так что «Разделительная ось существует» => «Нет перекрытия». Это не двусмысленность, поэтому вы не можете сделать вывод об обратном.
источник
Ответ m_pGladiator правильный, и я предпочитаю его. Тест с разделительной осью - это самый простой и стандартный метод определения перекрытия прямоугольников. Линия, для которой проекционные интервалы не перекрываются, мы называем разделяющей осью . Решение Нильса Пипенбринка слишком общее. Он использует точечное произведение, чтобы проверить, находится ли одна фигура полностью на одной стороне края другой. Такое решение фактически могло бы привести к n-ребрам выпуклых многоугольников. Тем не менее, он не выбран для двух прямоугольников.
критическая точка ответа m_pGladiator заключается в том, что мы должны проверить проекцию двух прямоугольников на обе оси (x и y). Если две проекции перекрываются, то мы можем сказать, что эти два прямоугольника перекрываются. Так что комментарии выше к ответу m_pGladiator неверны.
для простой ситуации, если два прямоугольника не повернуты, мы представляем прямоугольник со структурой:
мы называем прямоугольник A, B с помощью rectA, rectB.
если любой из двух прямоугольников повернут, может потребоваться некоторое усилие, чтобы определить их проекцию на оси x и y. Определите struct 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)
Может ссылаться на GDC (Конференция по разработке игр 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
источник
В Какао вы могли легко определить, пересекает ли выбранный прямоугольник прямоугольник повернутого кадра NSView. Вам даже не нужно вычислять полигоны, нормали такие. Просто добавьте эти методы в ваш подкласс NSView. Например, пользователь выбирает область в суперпредставлении NSView, затем вы вызываете метод DoesThisRectSelectMe, передавая прямоугольник selectedArea. API convertRect: сделает эту работу. Тот же трюк работает, когда вы нажимаете на NSView, чтобы выбрать его. В этом случае просто переопределите метод hitTest, как показано ниже. API convertPoint: сделает эту работу ;-)
источник
Проверьте, не пересекаются ли какие-либо линии из одного прямоугольника с какой-либо из линий другого. Наивное пересечение отрезка линии легко закодировать.
Если вам нужна большая скорость, существуют усовершенствованные алгоритмы пересечения отрезков (sweep-line). Смотрите http://en.wikipedia.org/wiki/Line_segment_intersection
источник
Одним из решений является использование того, что называется полигоном No Fit. Этот многоугольник рассчитывается из двух многоугольников (концептуально путем скольжения одного вокруг другого) и определяет область, для которой многоугольники перекрываются, учитывая их относительное смещение. Получив этот NFP, вы просто должны выполнить тест на включение с точкой, заданной относительным смещением двух полигонов. Этот тест на включение является быстрым и легким, но вы должны сначала создать NFP.
Поищите в сети «Не подходит многоугольник» и посмотрите, сможете ли вы найти алгоритм для выпуклых многоугольников (он становится намного сложнее, если у вас есть вогнутые многоугольники). Если вы не можете ничего найти, напишите мне на Говард точка J точка может Gmail точка ком
источник
Вот что я думаю позаботится обо всех возможных случаях. Сделайте следующие тесты.
Если вышеупомянутые 2 теста возвращают false, то эти 2 прямоугольника не перекрываются.
источник
Если вы используете Java, все реализации интерфейса Shape имеют метод пересечений, который принимает прямоугольник.
источник
Хорошо, метод грубой силы состоит в том, чтобы пройти края горизонтального прямоугольника и проверить каждую точку вдоль края, чтобы видеть, падает ли она на или в другом прямоугольнике.
Математический ответ - сформировать уравнения, описывающие каждое ребро обоих прямоугольников. Теперь вы можете просто найти, пересекаются ли какие-либо из четырех линий из прямоугольника A с любой из линий прямоугольника B, который должен быть простым (быстрым) решателем линейных уравнений.
-Адам
источник
Вы можете найти пересечение каждой стороны углового прямоугольника с каждой стороной выровненного по оси. Сделайте это, найдя уравнение бесконечной линии, на которой лежит каждая сторона (т.е. v1 + t (v2-v1) и v'1 + t '(v'2-v'1) в основном), найдя точку, в которой линии встречаются путем решения для t, когда эти два уравнения равны (если они параллельны, вы можете проверить это), а затем проверяете, лежит ли эта точка на отрезке между двумя вершинами, т.е. верно ли, что 0 <= t <= 1 и 0 <= t '<= 1.
Однако это не относится к случаю, когда один прямоугольник полностью покрывает другой. Это можно проверить, проверив, все ли четыре точки одного прямоугольника лежат внутри другого прямоугольника.
источник
Вот что я бы сделал для 3D- версии этой проблемы:
Смоделируйте 2 прямоугольника как плоскости, описываемые уравнениями P1 и P2, затем напишите P1 = P2 и выведите из этого линию уравнения пересечения, которая не будет существовать, если плоскости параллельны (нет пересечений) или находятся в одной плоскости, в этом случае вы получите 0 = 0. В этом случае вам нужно будет использовать алгоритм пересечения 2D-прямоугольника.
Тогда я бы посмотрел, проходит ли эта линия, которая находится в плоскости обоих прямоугольников, через оба прямоугольника. Если это так, то у вас есть пересечение 2-х прямоугольников, иначе вы этого не сделаете (или не должны, я мог пропустить угловой случай в моей голове).
Чтобы определить, проходит ли линия через прямоугольник в той же плоскости, я бы нашел 2 точки пересечения линии и стороны прямоугольника (моделируя их с помощью линейных уравнений), а затем убедившись, что точки пересечения находятся в ассортимент.
Это математические описания, к сожалению, у меня нет кода, чтобы сделать выше.
источник
Другой способ сделать тест, который немного быстрее, чем тест с разделительной осью, состоит в использовании алгоритма чисел намотки (только на квадрантах, а не суммировании углов, которое ужасно медленно) в каждой вершине любого прямоугольника (произвольно выбранного). Если какая-либо из вершин имеет ненулевое число обмоток, два прямоугольника перекрываются.
Этот алгоритм несколько длиннее, чем тест с разделительной осью, но он быстрее, потому что он требует только теста полуплоскости, если ребра пересекают два квадранта (в отличие от до 32 тестов с использованием метода разделительной оси)
Алгоритм имеет дополнительное преимущество в том, что его можно использовать для проверки перекрытия любого многоугольника (выпуклого или вогнутого). Насколько я знаю, алгоритм работает только в 2D пространстве.
источник
Либо я что-то упускаю, зачем делать это так сложно?
если (x1, y1) и (X1, Y1) являются углами прямоугольников, то для поиска пересечения выполните:
источник
Я реализовал это так:
Матрица mB - это любая матрица аффинного преобразования, которая преобразует точки в пространстве B в точки в пространстве A. Это включает в себя простое вращение и перемещение, вращение с масштабированием и полные аффинные деформации, но не перспективные деформации.
Это может быть не так оптимально, как это возможно. Скорость не была большой проблемой. Однако, похоже, у меня все в порядке.
источник
Вот математическая реализация принятого ответа:
источник
Это обычный метод, переходите строка за строкой и проверяйте, пересекаются ли линии. Это код в MATLAB.
Функцию InterX можно загрузить по адресу : https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function
источник
У меня есть более простой метод, если у нас есть 2 прямоугольника:
R1 = (min_x1, max_x1, min_y1, max_y1)
R2 = (min_x2, max_x2, min_y2, max_y2)
Они перекрываются, если и только если:
Перекрытие = (max_x1> min_x2) и (max_x2> min_x1) и (max_y1> min_y2) и (max_y2> min_y1)
Вы можете сделать это и для 3D-блоков, на самом деле это работает для любого количества измерений.
источник
В других ответах было сказано достаточно, поэтому я просто добавлю псевдокод в одну строку:
источник