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

Question

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

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

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

Answer 1

Либо я что-то упускаю, зачем делать это так сложно?

если (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");}

Answer 2

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

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

-Adam

Answer 3

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

Этот алгоритм несколько длиннее, чем тест с разделительной осью, но он быстрее, потому что он требует только теста полуплоскости, если ребра пересекают два квадранта (в отличие от до 32 тестов с использованием метода разделительной оси)

Алгоритм имеет дополнительное преимущество, заключающееся в том, что его можно использовать для проверки перекрытия любого многоугольника (выпуклого или вогнутого). Насколько я знаю, алгоритм работает только в 2D-пространстве.

Answer 4

Вот что я хотел бы сделать для 3D версии этой проблемы:

Смоделируйте 2 прямоугольника как плоскости, описываемые уравнениями P1 и P2, затем напишите P1 = P2 и выведите из этой линии уравнение пересечения, которое не будет существовать, если плоскости параллельны (без пересечения) или находятся в той же плоскости, в этом случае вы получите 0 = 0. В этом случае вам нужно будет использовать алгоритм пересечения прямоугольников 2D.

Тогда я бы посмотрел, проходит ли эта линия, находящаяся в плоскости обоих прямоугольников, через оба прямоугольника. Если это так, то у вас есть пересечение 2-х прямоугольников, иначе вы этого не сделаете (или не должны, я мог пропустить угловой случай в моей голове).

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

Это математические описания, к сожалению, у меня нет кода для выполнения вышесказанного.

Answer 5

Вы можете найти пересечение каждой стороны углового прямоугольника с каждой стороной выровненного по оси. Сделайте это, найдя уравнение бесконечной прямой, на которой лежит каждая сторона (т.е. v1 + t (v2-v1) и v'1 + t '(v'2-v'1) в основном), найдя точку, в которой линии встречаются путем решения для t, когда эти два уравнения равны (если они параллельны, вы можете проверить это), а затем проверяете, лежит ли эта точка на отрезке между двумя вершинами, то есть верно ли, что 0 <= t <= 1 и 0 <= t '<= 1. </p>

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

Answer 6

У меня есть более простой метод, если у нас есть 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-блоков, на самом деле это работает для любого количества измерений.

Answer 7

В других ответах было сказано достаточно, поэтому я просто добавлю псевдокод в одну строку:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);

Answer 8

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