Прямоугольники

Ответ 1

Здесь алгоритм деления и покорения. СРЕДНЯЯ сложность случая очень хорошая, и я бы сказал, что это что-то вроде O(n log MaxCoords). Худший случай может быть квадратичным, хотя, как мне кажется, такой тест будет довольно сложно создать. Чтобы сделать его еще сложнее, сделайте порядок рекурсивных вызовов функций случайным. Возможно, то, что предложил @Larry, может получить это до O(n log n) в среднем.

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

В принципе, используйте рекурсивную функцию, работающую на синем прямоугольнике. Сначала проверьте, полностью ли покрыт синий прямоугольник одним из других прямоугольников. Если да, мы закончили. Если нет, разделите его на 4 квадранта и рекурсивно вызовите функцию на этих квадрантах. Все 4 рекурсивных вызова должны возвращать true. Я включаю код С#, который рисует прямоугольники. Вы можете изменить его и работать с большими значениями, но в этом случае удалите процедуры рисования, так как они будут выполняться навсегда. Я тестировал его с миллионом прямоугольников и квадратом со стороны одного миллиарда, созданным таким образом, чтобы он не был покрыт, а предоставленный ответ (false) занял около секунды на четырехъядерном процессоре.

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

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }

Ответ 2

Здесь общий алгоритм

• есть ли прямоугольник, охватывающий всю модель?
  если да, то вы закончили.
• если нет прямоугольников, частично покрывающих модель?
  если да
• является объединением всех пересечений прямоугольника и модели, равной модели
  если 2. или 3. нет, тогда ответ будет отрицательным, иначе это да

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

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

Если вы используете, например kd-trees, я считаю, что на это можно ответить в O (log n) time, но важной переменной в этом алгоритме является также количество найденных прямоугольников k. В итоге вы получите что-то вроде O (k + log n), и вам понадобится сделать часть объединения, чтобы проверить, покрывается ли модель.

Я предполагаю, что объединение может быть вычислено в O (k log k), поэтому, если k мало, тогда вы смотрите на O (log n), и если k сопоставимо с n, то это должно быть O (k log к).

См. также этот вопрос.

EDIT: В ответ на сложность пересечений и союзов.

Более подробно мы имеем два сценария в зависимости от того, является ли k < n или k, сопоставимых с n

a) в случае k < n и предполагая полиномиальную сложность для пересечения/объединения (поэтому здесь я отказываюсь от предположения O (k log k)):

• log n to найти диапазон в индексированном дереве kd (из прямоугольников),
• k шагов для извлечения всех прямоугольников в этой ветке,
• f (k) некоторое многочленное время для вычисления пересечений и объединения

Общее значение O (k + log n + f (k)), которое прямо равно O (log n), поскольку большая O зависит только от самого быстрорастущего члена.

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

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

Но я считаю, что дерево kd также может помочь найти пересечение сегментов (которые необходимы для построения объединения), поэтому даже эта часть алгоритма может не понадобиться k ^ 2 раза. На этом этапе я бы исследовал эффективные алгоритмы вычисления площади союзов.

Ответ 3

Вы на правильном пути со строкой развертки. Концептуально мы хотим обнаружить, когда пересечение модели с линией развертки не покрывается другими прямоугольниками. Шаблон высокого уровня состоит в том, чтобы разбивать каждый прямоугольник на "левый край" и "правый край", сортировать события по координате x (ставить левые перед правами, если прямоугольники закрыты, а права перед левыми, если они открыты), а затем обрабатывать каждое событие в O (log n) времени. Это в основном домашнее задание, поэтому я больше не буду говорить.

Ответ 4

Существует тривиальный подход O(N^2), аналогичный подходу "растра", который воспитывается. Так как все прямоугольники параллельны оси, то может быть не более 2N различной размерности x и y. Отсортируйте все x и y и переназначить: x_i -> i. Итак, теперь у вас есть матрица 2N x 2N, где вы можете легко использовать наивный алгоритм O(N^2).

Ответ 5

Я думал об этом, и я думаю, что наконец понял, что @algorithmist означает строка развертки. Однако само наличие операций sorting означает, что у меня есть:

• O(n log n) в в среднем
• O(n**2) в худшем случае

Линия развертки

Прежде всего, нам нужна некоторая сортировка, потому что наш sweep line будет состоять из хождения упорядоченного набора.

Этот упорядоченный набор будет содержать строки top и bottom каждого из red s, если они находятся между top и bottom от blue. Это делит наше пространство на (не более) n*2 горизонтальные полосы.

Теперь нам нужно убедиться, что в каждом strip все blue покрывается, и эта операция не может быть сложнее O(log n), это можно сделать, если бы у нас (для каждой полосы) список охватываемых интервалов. Это "событие" @algorithmist говорит о

Чтобы обработать это событие, мы будем использовать описанное ниже двоичное дерево, которое обрабатывает добавление или удаление прямоугольника в точности O(log n) и дает самый правый интервал, покрываемый деревом, который мы используем, чтобы определить, существует ли полоса blue покрывается или нет.

Двоичное дерево

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

def __lt__(lhs, rhs):
  return (lhs.left <  rhs.left)
      or (lhs.left == rhs.left and lhs.right < rhs.right)

Затем я создам выделенное двоичное дерево.

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

Обработка ошибки "Кодовый блок не может следовать списку":

class Node:
  def __init__(self):
    self.interval = []
    self.left  = None
    self.right = None

Теперь у нас есть две возможности, скажем, дети покрывают [a,b] и [c,d]:

• if c <= b, то node удерживайте [a,d]
• else он содержит [c,d]

Почему это работает? Возьмем пример, используя 4 листа:

        _ [1,9] _
       /         \
   [1,7]         [6,9] <-- Special node merge
   /   \         /   \
  /     \       /     \
[1,3] [2,7]   [3,5] [6,9]

Специальный node игнорировать [3,5], потому что это не самый правый интервал. Причиной является то, что прямоугольники упорядочены:

• Никакой прямоугольник справа от [6,9] не будет охватывать отсутствующий интервал [5,6], поскольку они начинаются после 6
• Прямоугольники слева от [3,5] начинаются до 3, поэтому, если они покрывают недостающие [5,6], они будут покрывать [3,5] в любом случае

Корень может не указывать точный набор охватываемых интервалов: только самый правый интервал. Однако для нас совершенно достаточно сказать, полностью ли покрыто blue!

В этом дереве доступно 2 операции:

• Отметка прямоугольника как присутствующего
• Отметить прямоугольник как отсутствующий

Каждый из них похож:

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

Рекурсивный бит принимает O(log n). Это классическое свойство сбалансированных двоичных деревьев. И как только это будет сделано, мы имеем самый правый интервал, охватываемый корнем, который достаточно, чтобы определить, полностью ли покрыт сегмент blue или нет.

Сложность

Сложность алгоритма проста:

• У нас есть O(n) события
• Каждое событие обрабатывается в O(log n)

Что дает O(n log n) для основной части.

Однако мы не должны забывать, что у нас также есть 2 sort операции:

• для классификации событий (для линии развертки)
• другой для классификации прямоугольников (для двоичного дерева)

Каждый должен принимать O(n log n) в среднем, но в худшем случае может выродиться в O(n**2), в зависимости от используемого алгоритма сортировки.

Ответ 6

Хорошо, теперь кажется, что я даже не могу спать по ночам, потому что я думаю об этой проблеме... но также кажется, что я наконец получил решение O (n log n), в средний (но с уменьшенными возможностями наличия патологического ввода по сравнению с @lVlad).

Мы все знаем технику Divide and Conquer. Чтобы обеспечить использование O(n log n), мы обычно фокусируемся на 2 пунктах:

• разделение и слияние должны быть O(n)
• существует C > 1 такое, что на каждом шаге размер подзадач уменьшается на коэффициент C (постоянный по всей задаче)

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

Алгоритм

• Clipping: мы рассматриваем только часть red, которая пересекается с blue, они вставляются в HashSet для удаления дубликатов → O(n)
• Выбор поворота: подробнее об этом позже → O(n)
• Разделение: как только у нас есть свод, мы подразделим пространство в зонах 3 ^d один из которых является стержнем, причем d - размерность (d = 1 для сегментов, 2 для прямоугольников, 3 для кубов и т.д.)
• Repartition: мы помещаем red в разделы, применяя технику Clipping, отмечаем, что данный red может в конечном итоге дать несколько кусков в разных разделах
• Рекурсия: мы рекурсивно применяем (от шага 2) к каждому разделу, начиная с наименее населенного и останавливаясь, как только один не покрывается.

Выбор Pivot - это краеугольный камень алгоритма, если раздел плохо адаптирован, мы не можем достичь требуемой сложности. Кроме того, это должно быть выполнено в O(n). Пока у меня есть 2 предложения:

• Maximum Area: используйте прямоугольник с наибольшей площадью, потому что это означает, что после этого разделы будут иметь наименьшую площадь, однако он может быть легко превзошел
• Median of 3: на основе qsort, возьмите 3 элемента, выберите медиану (ту, где центр ближе к барицентру трех центров).

Я предлагаю их смешать:

• Возьмите 3 элемента с наибольшей площадью, выберите медианную, используйте ее при повороте.
• Если после перераспределения получается, что один из разделов заполнен более чем N/C (настраивается) элементами, выбирайте 3 элемента наугад, выбирайте медианную и делайте передел (здесь не проверяйте)

Другим аспектом реализации является Хвост рекурсии. Подобно qsort, вероятно, что алгоритм неэффективен при малых n. Вместо того, чтобы идти до 1, я предлагаю использовать трюк introsort: если n меньше, чем 12, вместо этого используйте вместо этого следующий алгоритм:

• Для каждой оси проецируйте каждую red на ось (только ребра) и сортируйте их (ala introsort)
• Это определяет растровую зону n ^d проверяйте, что каждая из них покрыта

Агностик измерения

Алгоритм формально определяется применимым в любой заданной размерности с той же асимптотической сложностью, в средней O (n log n). Это дает нам возможность протестировать в измерении 1 для определения патологических входов.

Патологический ввод

Подобно qsort, на котором он моделируется, он разумен для факториальных входов. По факториальным входам я имею в виду:

1.......6...9.11.13

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

При таком вводе даже выбирая медианную из 3 вряд ли даст очень хороший разрез.

EDIT:

Я собираюсь показать идею раздела с небольшой схемой, так как @lVlad отметил, что она была нечеткой.

+----------------+----+---------+
|       1        | 2  |   3     |
+----------------+----+---------+
|       8        | P  |   4     |
+----------------+----+---------+
|       7        | 6  |   5     |
+----------------+----+---------+

Хорошо, поэтому прямоугольник, который мы проверяем на покрытие, теперь разделен на 9 подправок. Мы игнорируем P, это наша точка.

Теперь нам бы очень хотелось, чтобы каждый subrectangle был меньше red, чем n. Стержень выбирается в качестве барицентра центров, поэтому это означает, что наш "случайный" выбор подтвердил, что в каждом направлении точки поворота находится столько центров red.

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

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

Ответ 7

Трудно знать, что вы ищете, но это звучит для меня как R-tree может работать?

Ответ 8

Хорошо, я задал достаточно вопросов, вот что-то вроде ответа...

Если данные представлены как растровые, один алгоритм тривиален:

• Создайте булевский массив, представляющий прямоугольник модели (т.е. синий). Установите все элементы в FALSE (представляя "не покрытый" )
• Для каждого красного прямоугольника (игнорируйте те, которые не могут пересекаться с Синим) установите для всех элементов массива значение ИСТИНА, если они находятся внутри красного прямоугольника.
• Наконец, проверьте, не установлен ли каждый элемент массива TRUE.

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

• Создайте переменную с именем UnCoveredRectangle, которая инициализируется таким же, как синий прямоугольник.

• Опять же, только беспокоитесь о красных прямоугольниках, которые пересекают синий. Для каждого красного прямоугольника вычислите пересечение прямоугольника с помощью UnCoveredRectangle. Пересечение приведет к одной из следующих ситуаций:

  2.1. Пересечение равно UnCoveredRectangle. Задание завершено.

  2.2 Пересечение "кусает" прямоугольный кусок из CoveredRectangle. Оставшийся UnCoveredRectangle будет либо прямоугольником, либо L-образной фигурой, либо U-образной фигурой. Если это прямоугольник, установите UnCoveredRectangle как оставшийся прямоугольник и перейдите к шагу 2. Если UnCoveredRectangle L- или U-образный, разделите его на 2 или 3 прямоугольника и повторите процедуру с шага 2.

• Если у вас закончились красные прямоугольники до того, как область (часть) UnCoveredRectangle отправлена ​​в 0, вы закончили.

OK У меня нет понятия о сложности этого алгоритма, но если количество прямоугольников не велико, я не слишком обеспокоен, хотя, возможно, @den. И я опустил много деталей. И я не могу рисовать красивые диаграммы, такие как @den, поэтому вам нужно будет представить их для себя.

Ответ 9

Здесь можно сделать это без использования растеризации, то есть с использованием только чистых чисел.

Примечание. Это не O (n log n), больше похожее на O (n ^ 2). Это, однако, решение. Является ли это ответом, возможно, нет, если требуется O (n log n).

• Создайте список всех уникальных X-координат левого и правого ребер (в том же списке)
• Когда вы создадите этот список, для каждой координаты также свяжите с ним список прямоугольников и обозначьте в этом списке, является ли X-координата, с которой связан список, - это левый или правый край прямоугольника
• Отсортируйте список координат так, чтобы он поднимался, идя слева направо
• Создайте новый список прямоугольников, изначально пустых
• Выполнить список координат и обработать связанный с ним список прямоугольников
• Все прямоугольники в ассоциированном списке, которые обозначены как имеющие координату в качестве левого края, должны быть добавлены в список, который вы создали в 4.
• Все прямоугольники с координатой в качестве правого края должны быть удалены.
• Порядок добавления и удаления фактически должен выполняться в противоположном порядке, сначала вы хотите удалить прямоугольные прямоугольники, а затем добавить все прямоугольники с левым краем
• Теперь, прежде чем удалять прямоугольники из списка, созданного в 4, вы хотите обработать их. Вы обрабатываете их, рассматривая их как "суб-прямоугольники". Их "новая" координата левого края - это X-координата, обработанная предыдущей итерацией цикла (в 5), а новый правый край - текущая обрабатываемая X-координата.
• Выход алгоритма представляет собой набор координатных пар (две X-координаты слева и справа), каждая пара имеет соответствующий список прямоугольников (вертикальная полоса)

Выход должен быть таким:

• X = 1..2, Rects = A
• X = 2..3, Rects = A, B
• X = 3..4, Rects = A, B, C
• X = 4..5, Rects = A, C
• X = 5..6, Rects = C

Позвольте мне проиллюстрировать этот процесс до сих пор

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+----------+-----+
   |          |
   +----------+

^  ^     ^    ^     ^     ^
1  2     3    4     5     6  <-- X-coordinates

Связанные прямоугольники:

• left: A, right: (none)
• слева: B, справа: (нет)
• слева: C, справа: (нет)
• left: (none), справа: B
• left: (none), справа: A
• left: (none), справа: C

Теперь вы создаете пустой список L=[] и начинаете обработку координат и связанных прямоугольников:

Х = 1

Список пуст, ничего не обработать Ничего не удалить Добавить A: L = [A]

Х = 2

Список содержит прямоугольники, список процессов как прямоугольники с левым краем X = 1 и правый край X = 2 (две координаты, которые мы обработали до сих пор), и используем их исходные верхние и нижние координаты. Ничего не удалить. Добавить B: L = [A, B]

Х = 3

Список содержит прямоугольники, список процессов (как A, так и B) одинаково, рассматривайте их как временно имеющие левую и правую координаты как X = 2 и X = 3, и используйте их исходные верхние и нижние координаты. Ничего не удалить Добавить C: L = [A, B, C]

Х = 4

Обработать три прямоугольника так же, как указано выше, временные левые и правые координаты X = 3 и X = 4 Удалить B: L = [A, C] Ничего добавить

X = 5 и X = 6

Обработать их точно так же.

Это означает, что вы получите "полоски" прямоугольников, как это (я немного потянул их, чтобы яснее проиллюстрировать, что они являются полосами, но они расположены бок о бок непрерывно, как на исходной диаграмме ):

+--+ +-----+ +----+ ------+
|A | |     | |    | |     |
|  | |     | +----+ +-----+ +-----+
|  | |     | |C   | |     | |     |
|  | +-----| +----+ |     | |     |
|  | |B    | |    | |     | |     |
|  | |     | +----+ +-----| +-----+
|  | |     | |    | |     |
+--+ +-----+ +----+ +-----+
     |     | |    |
     +-----+ +----+
^  ^ ^     ^ ^    ^ ^     ^ ^     ^
1  2 2     3 3    4 4     5 5     6

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

Теперь мы делаем трюк. Мы обрабатываем вертикальную полосу точно так же, только в этот раз мы используем координаты Y как разделители. Позвольте обрабатывать полосу между 3 и 4 выше. Помните, что полоса имеет левую и правую координаты 3 и 4.

Полоса выглядит следующим образом:

^     +----+ <-- 1
A     |    |
|   ^ +----+ <-- 2
|   C |    |
| ^ | +----+ <-- 3
| B | |    |
| | V +----+ <-- 4
| |   |    |
V |   +----+ <-- 5
  |   |    |
  V   +----+ <-- 6

Список координат с прямоугольниками:

• Top = A, Bottom = (none)
• Top = C, Bottom = (none)
• Top = B, Bottom = (none)
• Top = (none), Bottom = C
• Top = (none), Bottom = A
• Top = (none), Bottom = B

Новый пустой список L = []

Обработать координаты:

Y = 1

Ничего не обрабатывается (L = []) Добавить A в список, L = [A]

Y = 2

Процесс A с временным расположением верхних и нижних координат Y = 1 и 2 (и помните, что он также имеет временные левые и правые координаты X = 3 и 4 Добавить C, L = [A, C]

Y = 3

Процесс A и C, которые теперь имеют временные координаты (3, 2) - (4, 3) Добавить B, L = [A, B, C]

Y = 4

Процесс A, B и C, все из которых имеют координаты (3, 3) - (4, 4) Удалить C, L = [A, B]

Y = 5

Процесс A и B, координаты (3, 4) - (4, 5) Удалить A, L = [B]

Y = 6

Процесс B, координаты (3, 5) - (4, 6)

Конечный вывод:

пары Y-координат с связанными с ними прямоугольниками (которые также получили новые X-координаты):

• (3, 1) - (4, 2) - A
• (3, 2) - (4, 3) - A, C
• (3, 3) - (4, 4) - A, B, C
• (3, 4) - (4, 5) - A, B
• (3, 5) - (4, 6) - B

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

Ответ может быть выработан следующим образом:

• Прокрутите все прямоугольники в конечном списке выше
• Если B НЕ является частью связанного прямоугольника, игнорируйте этот прямоугольник
• Если есть какой-либо другой из исходных прямоугольников, связанных с координатами, то эта часть B покрывается тем, что /the rectangle (s)
• Если нет других исходных прямоугольников, связанных с координатами, то эта часть B не покрывается.

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

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

+--+-----+----+-----+
|A |A    |A   |A    |
|  |     +----+-----+-----+
|  |     |AC  |AC   |C    |
|  +-----+----+     |     |
|  |AB   |ABC |     |     |
|  |     +----+-----+-----+
|  |     |AB  |A    |
+--+-----+----+-----+
   |B    |B   |
   +-----+----+

Если мы теперь взглянем на исходную диаграмму, я закрасил части, найденные выше алгоритмом, содержит B, но не имеет другого прямоугольника:

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+-----+----+-----+
   |#####|####|
   +-----+----+

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

Я очень надеюсь, что понял себя здесь. У меня есть код, который может помочь вам в реализации каждого прогона по спискам координат, но это 01:21 за полночь здесь, и я ложась спать, но оставляю комментарий, если вы хотите увидеть какой-то фактический код для этого.

Или это было бы отличным упражнением, чтобы реализовать его самостоятельно:)

Здесь ссылка на класс, содержащий данный метод: RangeExtensions.cs.

Метод - это метод Slice, просто выполните поиск на нем страницы. Тип, о котором идет речь, Range, в основном представляет собой диапазон от одного значения к другому, поэтому в дополнение к вышеуказанному алгоритму существует немного структуры данных и обслуживания.

Ответ 10

Здесь, как заставить sweepline работать в O (n lg n). Я сосредоточусь на сложной части того, как работает BST.

Сохраняйте сбалансированный BST, который содержит начало и конец каждого прямоугольника, который пересекает текущий sweepline. Каждый node BST содержит два вспомогательных поля: minOverlap и deltaOverlap. Поле minOverlap обычно сохраняет минимальное количество прямоугольников, перекрывающих любую точку в интервале, охватываемом поддеревом этого node. Однако для некоторых узлов значение немного выключено. Мы сохраняем инвариант, что minOverlap плюс сумма deltaOverlap для каждого node до корня имеет истинное минимальное количество прямоугольников, перекрывающих область в поддереве node.

Когда мы вставляем начало прямоугольника node, мы всегда вставляем его в лист (и, возможно, перебалансировку). По мере прохождения по пути ввода мы "нажимаем" любые ненулевые значения deltaOverlap для дочерних элементов пути доступа к вставленному node, обновляя minOverlap узлов на пути доступа. Затем нам нужно увеличить каждый node до "права" вставленного node в дереве в O (lg n). Это достигается путем увеличения поля minOverlap всех правых предков вставленного node и увеличения deltaOverlap всех правых детей правых предков вставленного node. Аналогичный процесс выполняется для вставки node, который заканчивает прямоугольник, а также удаление точек. Операция перебалансировки может быть выполнена путем изменения только полей узлов, участвующих в вращении. Все, что вам нужно сделать, это проверить корень в каждой точке развертки, чтобы увидеть, является ли minOverlap равным 0.

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

Ответ 11

Знаете ли вы обычный худший вариант O(nlogn) для области объединения прямоугольников?

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

• Область ваших N прямоугольников
• Область ваших N прямоугольников и модели

Если эти области равны, модель полностью покрыта, в противном случае это не так.

Ответ 12

Здесь используется O (n lg n) время выполнения, используя некоторую память.

Используя пример:

Нам интересна только часть подкатегории сцены, которая содержит прямоугольник "model"; в этом примере прямоугольник 'model' равен 1,1 -> 6,6

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) собрать все координаты x, которые находятся в пределах прямоугольника модели (слева и справа), в список, затем отсортировать его и удалить дубликаты

1 3 4 5 6

2) собрать все координаты y, которые находятся в пределах прямоугольника модели (как сверху, так и снизу), в список, затем отсортировать его и удалить дубликаты

1 2 3 4 6

3) создать 2D-массив по количеству зазоров между уникальными координатами x * количеством пробелов между уникальными координатами y. Это может использовать один бит на ячейку, и вы можете рассмотреть использование С++ STL bit_vector() для эффективного представления.

4 * 4

4) покрасьте все прямоугольники в эту сетку, покрасьте ячейку, в которой она встречается:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

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

Координаты сбора и этапы рисования - O (n), а сортировка координат - O (n lg n).

Это адаптировано из одного из моих ответов на: Что такое эффективный алгоритм для поиска области перекрывающихся прямоугольников