Математика / Алгоритм / JS: Как определить, пересекаются ли 2+ прямоугольника, учитывая TopLeft (x0, y0) и Bottom-Right (x1, y1) каждого прямоугольника

Question

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

Дано 2 (или более, но в основном для 2) прямоугольника с 2 известными точками для каждого: Верхний левый (x1, y1) и Bottom -право (x2, y2) (я могу найти длину по этой информации, если это необходимо для решения проблемы).

TL(x1, y1)
   +-----------------+
   |                 |
   |                 |       TL(x3, y3)
   |                 |            +---------------------------+
   +-----------------+            |                           |
               BR(x2, y2)         +---------------------------+
                                                         BR(x4, y4)

В любом случае можно ли определить, имеют ли они пересечение в области, я имею в виду, лежит ли какая-либо часть этого прямоугольника на какой-либо части другого?

Я искал и нашел небольшую помощь, но это не решает проблему:

Существует 4 условия, при которых два прямоугольника не пересекаются:

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

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

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

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

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

Любая помощь высоко ценится, пожалуйста, покажите мне, как это сделать, или алгоритм, или код (только JS и PHP).

Большое спасибо!

* * Тысяча сорок-девять [х]

Answer 1

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

• Сортированный список S x-координат левого и правого краев прямоугольников.
• дерево интервалов T интервалов, заданныхy-координаты (внизу / вверху) прямоугольников.

Алгоритм перебирает отсортированный список S из x-координат:

1. Если текущийx-координата - это левый край прямоугольника R, тогда y-координаты [y1, y2] для R сравниваются с деревом интервалов T. Если обнаружено перекрытие, алгоритм останавливается и выдает сообщение OVERLAP.Если в дереве T не было перекрытия, то интервал [y1, y2] вставляется в дерево.

2. Если текущая координата x является правым краем прямоугольника Rзатем его интервал y [y1, y2] удаляется из дерева интервалов T.

3. Если отсортированный список S полностью обработан, то перекрытия не было.Алгоритм останавливается и выдает сообщение NO-OVERLAP.

Сложность по времени для N прямоугольников равна O (N * log (N)), поскольку для каждой 2 * N x-координат выполняется поиск вдерево интервалов для N интервалов.Сложность пространства составляет O (N) для вспомогательных структур данных S и T.

Answer 2

Это мои два цента по проблеме. Дайте мне знать, если это можно улучшить. Примеры, которые я сам делаю, похоже, верны с этим кодом, однако, если вы можете дать мне пример координат, которые приводят к сбою, я все же хотел бы поработать над этой проблемой:)

 <?php

//declare the points for your rectangles
//'UL' means upper left points, and 'LR' means the lower right points
$rectangle_array = array(
    $R1 = array("UL" => array("x" => 10, "y" => 20), "LR" => array("x" => 22, "y" => 5)),
    $R2 = array("UL" => array("x" => 32, "y" => 44), "LR" => array("x" => 65, "y" => 20)),
    $R3 = array("UL" => array("x" => 20, "y" => 16), "LR" => array("x" => 25, "y" => 10))
);


if (rectIntersect($rectangle_array)) {
    echo "THEY INTERSECT";
} else {
    echo "NO INTERSECTION";
}

function rectIntersect($rectangles) {
    $num_rectangles = count($rectangles);
    for ($i = 0; $i < $num_rectangles; $i++) {
        //for each rectangle, compare points to every following rectangle
        $R1 = $rectangles[$i];
        for ($k = $i; $k < ($num_rectangles - $i); $k++) {
            $R2 = $rectangles[$k + 1];
            if ($R1['LR']['x'] > $R2['UL']['x'] && $R1['UL']['x'] < $R2['LR']['x']) {
                //rectangles cross on x-axis
                if (($R1['LR']['y'] < $R2['UL']['y'] && $R1['UR']['y'] < $R2['LR']['y']) ||
                        ($R1['UL']['y'] > $R2['LR']['y'] && $R1['LR']['y'] < $R2['UL']['y'])) {
                    //rectangles intersect
                    return true;
                }
            }
        }
    }
    return false;
}

?>