Алгоритм обнаружения пересечения двух прямоугольников?
https://stackoverflow.com/questions/115426
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я ищу алгоритм для определения пересечения двух прямоугольников (один под произвольным углом, другой только с вертикальными/горизонтальными линиями).
Проверка того, находится ли угол одного в другом, ПОЧТИ работает.Это не удастся, если прямоугольники образуют крестообразную форму.
Кажется хорошей идеей избегать использования наклонов линий, что потребует особых случаев для вертикальных линий.
Решение
Стандартным методом будет сделать испытание разделяющей оси (поищите по этому поводу в 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 лет назад, и мне нужно найти фрагмент кода, чтобы опубликовать его здесь позже.
Поправка:Теорема о разделяющей оси утверждает, что две выпуклые формы не перекрываются, если существует разделяющая ось (т.е.тот, где проекции, как показано не перекрывать).Итак, «Разделяющая ось существует» => «Нет перекрытия».Это не двойное импликация, поэтому вы не можете сделать обратный вывод.
Ответ 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.Определите структуру RotatedRect следующим образом:
struct RotatedRect : Rect {
double angle; // the rotating angle oriented to its center
}
разница в том, что ширина теперь немного другая:ширинаA' для rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)ширинаB' для 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
Можно сослаться на PPT GDC (Конференция по разработке игр 2007 г.). www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
В Cocoa вы можете легко определить, пересекает ли прямоугольник selectedArea прямоугольник вашего повернутого кадра 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;
}
Проверьте, не пересекаются ли какие-либо линии одного прямоугольника с линиями другого.Наивное пересечение сегментов линии легко запрограммировать.
Если вам нужно больше скорости, есть усовершенствованные алгоритмы пересечения отрезков линии (sweep-line).Видеть http://en.wikipedia.org/wiki/Line_segment_intersection
Одним из решений является использование так называемого «неподходящего многоугольника».Этот многоугольник рассчитывается на основе двух многоугольников (концептуально путем скольжения одного вокруг другого) и определяет область, в которой полигоны перекрываются с учетом их относительного смещения.Если у вас есть этот NFP, вам просто нужно выполнить тест включения с точкой, заданной относительным смещением двух полигонов.Этот тест на включение выполняется быстро и легко, но сначала вам необходимо создать NFP.
Поищите в Интернете «Неподходящий многоугольник» и посмотрите, сможете ли вы найти алгоритм для выпуклых многоугольников (он становится НАМНОГО сложнее, если у вас есть вогнутые многоугольники).Если вы ничего не можете найти, напишите мне по адресу Howard Dot J Dot May Gmail Dot Com.
Вот что, я думаю, позаботится обо всех возможных случаях.Выполните следующие тесты.
- Убедитесь, что любая из вершин прямоугольника 1 находится внутри прямоугольника 2 и наоборот.Каждый раз, когда вы находите вершину, находящуюся внутри другого прямоугольника, вы можете сделать вывод, что они пересекаются, и остановить поиск.Это позаботится о том, чтобы один прямоугольник полностью находился внутри другого.
- Если приведенный выше тест не дал результатов, найдите точки пересечения каждой линии одного прямоугольника с каждой линией другого прямоугольника.Как только точка пересечения найдена, проверьте, находится ли она между воображаемым прямоугольником, созданным соответствующими четырьмя точками.Когда такая точка будет найдена, сделайте вывод, что они пересекаются, и прекратите поиск.
Если два вышеуказанных теста возвращают значение false, то эти два прямоугольника не перекрываются.
Если вы используете Java, все реализации интерфейса Shape имеют пересекает метод, который принимает прямоугольник.
Что ж, метод грубой силы состоит в том, чтобы пройтись по краям горизонтального прямоугольника и проверить каждую точку вдоль края, чтобы увидеть, попадает ли она на другой прямоугольник или в него.
Математический ответ — составить уравнения, описывающие каждый край обоих прямоугольников.Теперь вы можете просто определить, пересекает ли какая-либо из четырех линий прямоугольника A какую-либо из линий прямоугольника B, что должно быть простым (быстрым) решателем линейных уравнений.
-Адам
Вы можете найти пересечение каждой стороны углового прямоугольника с каждой стороной прямоугольника, выровненного по оси.Сделайте это, найдя уравнение бесконечной прямой, на которой лежит каждая сторона (т.е.v1 + t(v2-v1) и v'1 + t'(v'2-v'1) в основном), нахождение точки, в которой пересекаются линии, путем решения для t, когда эти два уравнения равны (если они параллельно, вы можете проверить это), а затем проверить, лежит ли эта точка на отрезке между двумя вершинами, т.е.Верно ли, что 0 <= t <= 1 и 0 <= t' <= 1.
Однако это не распространяется на случай, когда один прямоугольник полностью перекрывает другой.Это можно проверить, проверив, лежат ли все четыре точки одного прямоугольника внутри другого прямоугольника.
Это то, что я бы сделал, потому что 3D версия этой проблемы:
Смоделируйте два прямоугольника как плоскости, описываемые уравнениями P1 и P2, затем запишите P1=P2 и выведите из него уравнение линии пересечения, которого не будет, если плоскости параллельны (нет пересечения) или находятся в одной плоскости. в этом случае вы получите 0=0.В этом случае вам нужно будет использовать алгоритм пересечения 2D-прямоугольника.
Затем я хотел посмотреть, проходит ли эта линия, находящаяся в плоскости обоих прямоугольников, через оба прямоугольника.Если да, то у вас есть пересечение двух прямоугольников, в противном случае — нет (или не должно быть, возможно, я упустил в голове угловой случай).
Чтобы определить, проходит ли линия через прямоугольник в той же плоскости, я должен найти две точки пересечения линии и сторон прямоугольника (моделируя их с помощью уравнений линии), а затем убедиться, что точки пересечения совпадают с диапазон.
Это математические описания, к сожалению, у меня нет кода, позволяющего сделать вышеизложенное.
Другой способ выполнить тест, который немного быстрее, чем тест на разделяющую ось, — использовать алгоритм чисел витков (только для квадрантов — нет угловое суммирование, которое происходит ужасно медленно) на каждой вершине любого прямоугольника (выбранного произвольно).Если какая-либо из вершин имеет ненулевое число витков, два прямоугольника перекрываются.
Этот алгоритм несколько более трудоемкий, чем тест разделяющей оси, но он быстрее, поскольку он требует проверки полуплоскости только в том случае, если ребра пересекают два квадранта (в отличие от 32 тестов с использованием метода разделяющей оси).
Алгоритм имеет еще одно преимущество: его можно использовать для проверки перекрытия любой многоугольник (выпуклый или вогнутый).Насколько я знаю, алгоритм работает только в 2D-пространстве.
Либо я что-то упускаю, зачем все так усложнять?
если (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");}
Я реализовал это так:
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.Сюда входят простое вращение и перемещение, вращение плюс масштабирование и полные аффинные деформации, но не перспективные деформации.
Возможно, это не совсем оптимально.Скорость не вызывала большого беспокойства.Однако мне кажется, что это работает нормально.
Вот реализация принятого ответа в 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);
Это обычный метод: проходите по строкам и проверяйте, пересекаются ли линии.Это код в 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
У меня есть более простой метод, если у нас есть 2 прямоугольника:
R1 = (мин_x1, макс_x1, мин_y1, макс_y1)
R2 = (мин_x2, макс_x2, мин_y2, макс_y2)
Они перекрываются тогда и только тогда, когда:
Перекрытие = (max_x1 > min_x2) и (max_x2 > min_x1) и (max_y1 > min_y2) и (max_y2 > min_y1)
Вы можете сделать это и для 3D-боксов, на самом деле это работает для любого количества измерений.
В других ответах было сказано достаточно, поэтому я просто добавлю однострочный псевдокод:
!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
