Алгоритм для обнаружения пересечения двух прямоугольников?
Я ищу алгоритм, чтобы определить, пересекаются ли два прямоугольника (один под произвольным углом, другой только с вертикальными / горизонтальными линиями).
Тестирование, если угол одного находится в другом, ПОЧТИ работает. Сбой, если прямоугольники образуют крестообразную форму.
Кажется хорошей идеей избегать использования наклонов линий, что потребовало бы особых случаев для вертикальных линий.
18 ответов
Стандартный метод состоит в том, чтобы сделать тест разделительной оси (выполните поиск Google по этому вопросу).
Короче:
- Два объекта не пересекаются, если вы можете найти линию, которая разделяет два объекта. например, объекты / все точки объекта находятся на разных сторонах линии.
Самое интересное, что достаточно просто проверить все ребра двух прямоугольников. Если прямоугольники не перекрываются, то одна из кромок будет разделительной осью.
В 2D вы можете сделать это без использования уклонов. Ребро просто определяется как разница между двумя вершинами, например
edge = v(n) - v(n-1)
Вы можете получить перпендикуляр к этому, повернув его на 90°. В 2D это просто как:
rotated.x = -unrotated.y
rotated.y = unrotated.x
Таким образом, нет тригонометрии или склонов. Нормализация вектора на единицу длины также не требуется.
Если вы хотите проверить, находится ли точка на той или иной стороне линии, вы можете просто использовать точечный продукт. знак скажет вам, на какой стороне вы находитесь:
// rotated: your rotated edge
// v(n-1) any point from the edge.
// testpoint: the point you want to find out which side it's on.
side = sign (rotated.x * (testpoint.x - v(n-1).x) +
rotated.y * (testpoint.y - v(n-1).y);
Теперь проверьте все точки прямоугольника A относительно краев прямоугольника B и наоборот. Если вы найдете разделяющую кромку, объекты не пересекаются (при условии, что все остальные точки в B находятся на другой стороне проверяемой кромки - см. Рисунок ниже). Если вы не найдете разделительной кромки, либо прямоугольники пересекаются, либо один прямоугольник содержится в другом.
Тест работает с любыми выпуклыми многоугольниками, кстати..
Поправка: для идентификации разделяющего ребра недостаточно проверить все точки одного прямоугольника на каждом ребре другого. Кром-кандидат E (ниже) будет обозначен как разделительный край, так как все точки в A находятся в одной и той же полуплоскости E. Однако это не разделительный край, потому что вершины Vb1 и Vb2 из B также в этой полуплоскости. Это было бы только разделительным краем, если бы это было не так http://www.iassess.com/collision.png
В основном посмотрите на следующую картину:
Если два блока сталкиваются, линии A и B будут перекрываться.
Обратите внимание, что это должно быть сделано как по оси X, так и по оси Y, и оба должны перекрываться для столкновения прямоугольников.
На gamasutra.com есть хорошая статья, которая отвечает на вопрос (картинка из статьи). Я сделал подобный алгоритм 5 лет назад, и я должен найти свой фрагмент кода, чтобы опубликовать его здесь позже
Поправка: Теорема о разделяющей оси утверждает, что две выпуклые формы не перекрываются, если существует разделяющая ось (то есть та, где проекции, как показано , не перекрываются). Так что "Разделительная ось существует" => "Нет перекрытия". Это не двусмысленность, поэтому вы не можете заключить обратное.
В Какао вы могли легко определить, пересекает ли выбранный объект прямоугольник прямоугольник вашего повернутого кадра NSView. Вам даже не нужно вычислять полигоны, нормали такие. Просто добавьте эти методы в ваш подкласс NSView. Например, пользователь выбирает область в суперпредставлении NSView, затем вы вызываете метод DoesThisRectSelectMe, передавая прямоугольник selectedArea. API convertRect: сделает эту работу. Тот же трюк работает, когда вы нажимаете на NSView, чтобы выбрать его. В этом случае просто переопределите метод hitTest, как показано ниже. API convertPoint: сделает эту работу;-)
- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
NSRect localArea = [self convertRect:selectedArea fromView:self.superview];
return NSIntersectsRect(localArea, self.bounds);
}
- (NSView *)hitTest:(NSPoint)aPoint
{
NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
Ответ m_pGladiator правильный, и я предпочитаю его.Тест с разделительной осью - это самый простой и стандартный метод определения перекрытия прямоугольников. Линия, для которой проекционные интервалы не перекрываются, мы называем разделяющей осью. Решение Нильса Пипенбринка слишком общее. Он использует точечное произведение, чтобы проверить, находится ли одна фигура полностью на одной стороне края другой. Такое решение фактически могло бы привести к n-ребрам выпуклых многоугольников. Тем не менее, он не выбран для двух прямоугольников.
критическая точка ответа m_pGladiator заключается в том, что мы должны проверить проекцию двух прямоугольников на обе оси (x и y). Если две проекции перекрываются, то можно сказать, что эти два прямоугольника перекрываются. Так что комментарии выше к ответу m_pGladiator неверны.
для простой ситуации, если два прямоугольника не повернуты, мы представляем прямоугольник со структурой:
struct Rect {
x, // the center in x axis
y, // the center in y axis
width,
height
}
мы называем прямоугольник A, B с помощью rectA, rectB.
if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2)
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
then
// A and B collide
end if
если любой из двух прямоугольников повернут, может потребоваться некоторое усилие, чтобы определить их проекцию на оси x и y. Определите struct RotatedRect следующим образом:
struct RotatedRect : Rect {
double angle; // the rotating angle oriented to its center
}
разница в том, что теперь ширина 'немного отличается:
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)
if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2)
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
then
// A and B collide
end if
Может ссылаться на GDC(Конференция по разработке игр 2007) PPT http://www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
Общепринятый ответ об испытании разделяющей оси был очень освещая, но я все еще чувствовал, что это было не тривиально применять. Я поделюсь псевдокодом, который, как я думал, сначала "оптимизируется" с помощью теста ограничивающего круга (см. Этот другой ответ), на случай, если это может помочь другим людям. Я рассмотрел два прямоугольника A и B одинакового размера (но общую ситуацию рассмотреть несложно).
1 Тест ограничивающего круга:
function isRectangleACollidingWithRectangleB:
if d > 2 * R:
return False
...
Вычислительно намного быстрее, чем тест разделяющей оси. Вам нужно только рассмотреть тест разделяющей оси в ситуации, когда обе окружности сталкиваются.
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 (как показано на изображении), это означает мы обнаружили, что разделяющая ось и прямоугольники не пересекаются.
В псевдокоде:
function isRectangleACollidingWithRectangleB:
...
#Consider first rectangle A:
Si-1 = Vertex_A[4] - Vertex_A[1]
for i in Vertex_A:
Si+1 = Vertex_A[i+1] - Vertex_A[i]
Ni = [- Si+1.y, Si+1.x ]
sgn_i = sign( dot_product(Si-1, Ni) ) #sgn_i is the sign of rectangle A with respect the separating axis
for j in Vertex_B:
sij = Vertex_B[j] - Vertex_A[i]
sgn_j = sign( dot_product(sij, Ni) ) #sgnj is the sign of vertex j of square B with respect the separating axis
if sgn_i * sgn_j > 0: #i.e., we have the same sign
break #Vertex i does not define separating axis
else:
if j == 4: #we have reached the last vertex so vertex i defines the separating axis
return False
Si-1 = - Si+1
#Repeat for rectangle B
...
#If we do not find any separating axis
return True
Вы можете найти код на Python здесь.
Примечание: в этом другом ответе они также предлагают для оптимизации попробовать перед проверкой разделяющей оси, находятся ли вершины одного прямоугольника внутри другого в качестве достаточного условия для столкновения. Однако в своих испытаниях я обнаружил, что этот промежуточный шаг на самом деле менее эффективен.
Одно из решений состоит в том, чтобы использовать то, что называется полигоном No Fit. Этот многоугольник рассчитывается на основе двух многоугольников (концептуально путем скольжения одного вокруг другого), и он определяет область, для которой многоугольники перекрываются, учитывая их относительное смещение. Получив этот NFP, вы просто должны выполнить тест на включение с точкой, заданной относительным смещением двух полигонов. Этот тест на включение является быстрым и легким, но вы должны сначала создать NFP.
Поищите в сети "Не подходит многоугольник" и посмотрите, сможете ли вы найти алгоритм для выпуклых многоугольников (он становится намного сложнее, если у вас есть вогнутые многоугольники). Если вы не можете ничего найти, напишите мне на Говард точка J точка может Gmail точка ком
Проверьте, не пересекаются ли какие-либо линии из одного прямоугольника с какой-либо из линий другого. Наивное пересечение отрезка линии легко закодировать.
Если вам нужна большая скорость, существуют усовершенствованные алгоритмы пересечения отрезков (sweep-line). Смотрите http://en.wikipedia.org/wiki/Line_segment_intersection
Вот что я думаю позаботится обо всех возможных случаях. Сделайте следующие тесты.
- Убедитесь, что любая из вершин прямоугольника 1 находится внутри прямоугольника 2 и наоборот. Каждый раз, когда вы находите вершину, которая находится внутри другого прямоугольника, вы можете сделать вывод, что они пересекаются, и остановить поиск. Это позаботится о том, чтобы один прямоугольник полностью находился внутри другого.
- Если приведенный выше тест не дает результатов, найдите точки пересечения каждой линии одного прямоугольника с каждой линией другого прямоугольника. Как только точка пересечения найдена, проверьте, находится ли она внутри воображаемого прямоугольника, созданного соответствующими 4 точками. Когда когда-нибудь найдется такая точка, сделайте вывод, что они пересекаются и остановите поиск
Если вышеупомянутые 2 теста возвращают false, то эти 2 прямоугольника не перекрываются.
Либо я что-то упускаю, зачем делать это так сложно?
если (x1,y1) и (X1,Y1) являются углами прямоугольников, то для поиска пересечения выполните:
xIntersect = false;
yIntersect = false;
if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
if (xIntersect && yIntersect) {alert("Intersect");}
У меня есть более простой метод, если у нас есть 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-блоков, на самом деле это работает для любого количества измерений.
Вот что я бы сделал для 3D- версии этой проблемы:
Смоделируйте 2 прямоугольника как плоскости, описываемые уравнениями P1 и P2, затем напишите P1=P2 и выведите из этого линию уравнения пересечения, которая не будет существовать, если плоскости параллельны (нет пересечений) или находятся в одной плоскости, в этом случае вы получите 0=0. В этом случае вам нужно будет использовать алгоритм пересечения 2D-прямоугольника.
Тогда я бы увидел, проходит ли эта линия, которая находится в плоскости обоих прямоугольников, через оба прямоугольника. Если это так, то у вас есть пересечение 2-х прямоугольников, в противном случае вы не можете (или не должны, я мог пропустить угловой случай в моей голове).
Чтобы определить, проходит ли линия через прямоугольник в той же плоскости, я бы нашел 2 точки пересечения линии и стороны прямоугольника (моделируя их с помощью линейных уравнений), а затем убедившись, что точки пересечения находятся в спектр.
Это математические описания, к сожалению, у меня нет кода, чтобы сделать выше.
Это обычный метод, переходите строка за строкой и проверяйте, пересекаются ли линии. Это код в MATLAB.
C1 = [0, 0]; % Centre of rectangle 1 (x,y)
C2 = [1, 1]; % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];
R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;
plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')
%% lines of Rectangles
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
line1 = reshape(L1(i,:),2,2) ;
for j = 1:4
line2 = reshape(L2(j,:),2,2) ;
point = InterX(line1,line2) ;
if ~isempty(point)
count = count+1 ;
P(:,count) = point ;
end
end
end
%%
if ~isempty(P)
fprintf('Given rectangles intersect at %d points:\n',size(P,2))
plot(P(1,:),P(2,:),'*k')
end
Функцию InterX можно загрузить по адресу: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function
Вот реализация принятого ответа в Matlab:
function olap_flag = ol(A,B,sub)
%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order
if nargin == 2
olap_flag = ol(A,B,1) && ol(B,A,1);
return;
end
urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);
olap_flag = ~any(max(sdiff)<0);
Я реализовал это так:
bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
float Axmin = boundsA.origin.x;
float Axmax = Axmin + boundsA.size.width;
float Aymin = boundsA.origin.y;
float Aymax = Aymin + boundsA.size.height;
float Bxmin = boundsB.origin.x;
float Bxmax = Bxmin + boundsB.size.width;
float Bymin = boundsB.origin.y;
float Bymax = Bymin + boundsB.size.height;
// find location of B corners in A space
float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);
float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);
float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);
float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);
if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
return false;
if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
return false;
if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
return false;
if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
return false;
float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);
// find location of A corners in B space
float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;
float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;
float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;
float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;
if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
return false;
if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
return false;
if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
return false;
if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
return false;
return true;
}
Матрица mB - это любая матрица аффинного преобразования, которая преобразует точки в пространстве B в точки в пространстве A. Это включает в себя простое вращение и перемещение, вращение с масштабированием и полные аффинные деформации, но не перспективные деформации.
Это может быть не так оптимально, как это возможно. Скорость не была большой проблемой. Однако, похоже, у меня все в порядке.
Хорошо, метод грубой силы состоит в том, чтобы пройти края горизонтального прямоугольника и проверить каждую точку вдоль края, чтобы видеть, падает ли она на или в другом прямоугольнике.
Математический ответ состоит в том, чтобы сформировать уравнения, описывающие каждое ребро обоих прямоугольников. Теперь вы можете просто найти, пересекаются ли какие-либо из четырех линий из прямоугольника A с любой из линий прямоугольника B, который должен быть простым (быстрым) решателем линейных уравнений.
-Адам
Вы могли найти пересечение каждой стороны прямоугольного прямоугольника с каждой стороной выровненного по оси. Сделайте это, найдя уравнение бесконечной линии, на которой лежит каждая сторона (т.е. v1 + t(v2-v1) и v'1 + t'(v'2-v'1) в основном), найдя точку, в которой линии встречаются путем решения для t, когда эти два уравнения равны (если они параллельны, вы можете проверить это), а затем проверяете, лежит ли эта точка на отрезке между двумя вершинами, т.е. верно ли, что 0 <= t <= 1 и 0 <= t' <= 1.
Однако это не относится к случаю, когда один прямоугольник полностью покрывает другой. Вы можете это проверить, проверив, все ли четыре точки одного прямоугольника лежат внутри другого прямоугольника.
В других ответах было сказано достаточно, поэтому я просто добавлю псевдокод в одну строку:
!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
Убедитесь, что центр масс всех вершин обоих прямоугольников находится внутри одного из прямоугольников.
Если вы используете Java, все реализации интерфейса Shape имеют метод пересечений, который принимает прямоугольник.
Другой способ сделать тест, который немного быстрее, чем тест с разделительной осью, состоит в том, чтобы использовать алгоритм чисел намотки (только для квадрантов - не суммирование углов, которое ужасно медленно) в каждой вершине любого прямоугольника (произвольно выбранный). Если какая-либо из вершин имеет ненулевое число обмоток, два прямоугольника перекрываются.
Этот алгоритм несколько длиннее, чем тест с разделительной осью, но он быстрее, потому что он требует только теста полуплоскости, если ребра пересекают два квадранта (в отличие от до 32 тестов с использованием метода разделительной оси)
Алгоритм имеет дополнительное преимущество, заключающееся в том, что его можно использовать для проверки перекрытия любого многоугольника (выпуклого или вогнутого). Насколько я знаю, алгоритм работает только в 2D пространстве.