Инвертирование набора прямоугольников на 2D-плоскости

Question

У меня прямоугольная плоскость целочисленного размера.Внутри этой плоскости у меня есть набор непересекающихся прямоугольников (целочисленного размера и с целочисленными координатами).

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

Мое текущее, наивное решение использует булеву матрицу (размер плоскости) и работает поустановка точки i, j в 0, если она содержится внутри под прямоугольника, и 1 в противном случае.Затем я перебираю каждый элемент матрицы и, если это 1 (свободная) попытка «вырастить» прямоугольник наружу от точки.Уникальность не имеет значения (подходит любой подходящий набор прямоугольников).

Существуют ли алгоритмы, которые могут более эффективно решить такую ​​проблему?(Т. Е. Не прибегая к булевой матрице.

Answer 1

Да, это довольно просто. Я уже отвечал на почти такой же вопрос по SO, но пока не смог его найти.

В любом случае, по сути, вы можете сделать это:

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

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

Answer 2

Хорошо! Первая реализация! (java), на основе @ Paul's ответа:

List<Rectangle> slice(Rectangle r, Rectangle mask)
{
        List<Rectangle> rects = new ArrayList();

        mask = mask.intersection(r);

        if(!mask.isEmpty())
        {
                rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y));
                rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height)));
                rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height));
                rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height));

                for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();)
                        if(iter.next().isEmpty())
                                iter.remove();
        }
        else rects.add(r);

        return rects;
}

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects)
{
        List<Rectangle> outputs = new ArrayList();
        outputs.add(base);

        for(Rectangle r : rects)
        {
                List<Rectangle> newOutputs = new ArrayList();

                for(Rectangle output : outputs)
                {
                        newOutputs.addAll(slice(output, r));
                }

                outputs = newOutputs;
        }
        return outputs;
}

Возможно рабочий пример здесь

Answer 3

Вы должны взглянуть на алгоритмы заполнения пространства.Эти алгоритмы стараются заполнить данное пространство геометрическими фигурами.Не должно быть трудно изменить такой алгоритм в соответствии с вашими потребностями.

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

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

Вот сайт с множеством алгоритмов, которые могут быть полезны.

Answer 4

Это относительно просто, потому что ваши прямоугольники не пересекаются. Целью является набор непересекающихся прямоугольников, которые полностью покрывают плоскость, некоторые помечены как оригинальные, а некоторые помечены как «обратные».

Думайте с точки зрения сканирования сверху вниз (или слева направо или как угодно). У вас есть текущая позиция "линии прилива". Определите, какая позиция следующей горизонтальной линии, с которой вы столкнетесь, находится не на линии прилива. Это даст вам высоту вашей следующей линии прилива.

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

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

Вы можете сделать то же самое, даже если ваши исходные прямоугольники могут пересекаться, но это немного сложнее.

Подробности оставлены в качестве упражнения для читателя; -)

Answer 5

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