Перечислите целые точки не общих частей двух прямоугольников.

Question

У меня есть два прямоугольника, которые параллельны оси координат и имеют целочисленные координаты.

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

Прямоугольники могут пересекаться частично, полностью или не пересекаться вообще. Мне нужно перечислить точки первого прямоугольника, которые не находятся внутри второго, и точки второго прямоугольника, которые не находятся внутри первого.

Пример

Кроме того, мне нужно сделать это намного лучше, чем O (h1 * w1 + h2 * w2), лучше всего O (количество очков результата).

Answer 1

Прямоугольники могут пересекаться частично, полностью или не пересекаться вообще.

Давайте исследуем проблему в каждом сценарии:

1. Когда они не пересекаются: Вам нужно перечислить все точки обоих прямоугольников.

2. Когда они полностью пересекаются: В этом сценарии вы можете просто перебрать все точки большего прямоугольника и проверить, находятся ли они внутри пересечения. Но чтобы улучшить его и просто просмотреть результаты, вы можете разделить его на 8 различных разделов:

Теперь вы можете перечислить все точки каждого раздела.

3. Когда они частично пересекаются: Это можно рассматривать как особый случай для предыдущего, где некоторые из этих 8 разделов недействительны:

Вывод: В следующем псевдокоде каждый прямоугольник представлен массивом из 4 элементов, например: [left top right bottom].

procedure isValid(R)
    return R(1)<=R(3) & R(2)<=(R4)
end

procedure enumerateRectangle(R)
    if isValid(R)
        for i = R(1) to R(3)
            for j = R(2) to R(4)
                visit(i, j)
end

procedure enumerateNonIntersection(R, I)
    enumerateRectangle([R(1),       R(2),       I(1)-1,     I(2)-1])    // top-left
    enumerateRectangle([R(1),       I(2),       I(1)-1,     I(4)])      // left
    enumerateRectangle([R(1),       I(4)+1,     I(1)-1,     R(4)])      // bottom-left

    enumerateRectangle([RI(1),      R(2),       I(3),       I(2)-1])    // top
    enumerateRectangle([RI(1),      I(4)+1,     I(3),       R(4)])      // bottom

    enumerateRectangle([I(3)+1,     R(2),       R(3),       I(2)-1])    // top-right
    enumerateRectangle([I(3)+1,     I(2),       R(3),       I(4)])      // right
    enumerateRectangle([I(3)+1,     I(4)+1,     R(3),       R(4)])      // bottom-right
end

procedure enumerateExclusiveOr(R1, R2)
    I = intersectionOf(R1, R2)
    if isValid(I)
        enumerateNonIntersection(R1, I)
        enumerateNonIntersection(R2, I)
    else
        enumerateRectangle(R1)
        enumerateRectangle(R2)
    end
end