Прямоугольное покрытие

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

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

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

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

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

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

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

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

   2.1 Пересечение равно UnCoveredRectangle. Работа закончена.

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

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

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

Вот общий алгоритм

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: В ответ на сложность пересечений и объединений.

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

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

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

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

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

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

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

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

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

1. Создайте список всех уникальных X-координат левого и правого краев (в том же списке)
2. Когда вы создаете этот список, для каждой координаты также свяжите с ним список прямоугольников и обозначьте в этот список вне зависимости от того, является ли X-координата, с которой связан список, левым или правым краем прямоугольника
3. Отсортируйте список координат по возрастанию слева направо
4. Создайте новый список прямоугольников , изначально пусто
5. Просмотрите список координат и обработайте связанный список прямоугольников для него.
6. Все прямоугольники в связанном списке, которые обозначены как имеющие координату левого края, должны быть добавлены в список, который вы создали in 4.
7. Все прямоугольники с координатой правого края должны быть удалены.
8. Порядок добавления и удаления на самом деле должен выполняться в обратном порядке: сначала вы хотите удалить прямоугольники с правым краем, а затем вы добавляете все прямоугольники с левым краем.
9. Теперь, прежде чем удалять прямоугольники из списка, созданного вами в 4, вы хотите их обработать. Вы обрабатываете их, рассматривая их как «подпрямоугольники». Их «новая» координата левого края - это координата X, которую вы обработали на предыдущей итерации цикла (в 5), а новый правый край - это текущая обрабатываемая координата X
10. . Результатом алгоритма является набор пары координат (две координаты X слева и справа), каждая пара имеет связанный список прямоугольников (вертикальная полоса)

Таким образом, результат должен быть:

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

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

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

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

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

1. слева: A, справа: (нет)
2. слева: B, справа: (нет)
3. слева: C, справа: (нет)
4. слева: (нет), справа: B
5. слева: (нет), справа: A
6. слева: (нет), справа: C

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

X = 1

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

X = 2

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

X = 3

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

X = 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

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

1. Сверху = A, Снизу = (нет)
2. Сверху = C, Снизу = (нет)
3. Сверху = B, Снизу = (нет)
4. Сверху = (нет), Снизу = C
5. Сверху = (нет), Снизу = A
6. Сверху = (нет), Снизу = B

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

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

Y = 1

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

Y = 2

Процесс A с временными верхними и нижними координатами Y = 1 и 2 (и помните, что он также имеет временные левые и правые координаты X = 3 и 4 Add 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 покрывается любой комбинацией другие прямоугольники.

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

1. Перебрать все прямоугольники в последнем списке выше
2. Если B является НЕ частью связанного прямоугольника, игнорируйте этот прямоугольник
3. Если есть какие-либо другие исходные прямоугольники, связанные с координатами, то эта часть B покрывается этим / этими прямоугольниками
4. . Если нет других исходных прямоугольников, связанных с координаты, то эта часть B не покрывается.

В приведенном выше примере мы видим, что 3-й и 4-й прямоугольники в окончательном списке содержат 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, в основном представляет собой диапазон от одного значения до другого, поэтому в дополнение к вышеупомянутому алгоритму есть немного построения и обслуживания данных.

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

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

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

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

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

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

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

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

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

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

Затем я собираюсь создать специальное двоичное дерево.

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

Обработка ошибки «блок кода не может следовать списку»:

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

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

• если c <= b , то выполняется узел [a, d]
• иначе выполняется [c, d]

Почему это работает? Рассмотрим пример с 4 листами:

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

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

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

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

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

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

Все похожи:

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

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

Сложность

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

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

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

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

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

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

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

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

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

В основном, используйте рекурсивную функцию, которая работает с синим прямоугольником. Сначала проверьте, полностью ли синий прямоугольник покрыт одним из других прямоугольников. Если да, то все готово. Если нет, разделите его на 4 квадранта и рекурсивно вызовите функцию для этих квадрантов. Все 4 рекурсивных вызова должны возвращать истину. Я добавляю код C #, который рисует прямоугольники.Вы также можете изменить его для работы с большими значениями, но в этом случае удалите процедуры рисования, так как они будут длиться вечно. Я тестировал его с миллионом прямоугольников и квадратом со стороной один миллиард, созданным таким образом, что он не покрыт, и предоставленный ответ ( 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(); 
    }

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

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

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

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

Алгоритм

1. Отсечение : мы учитываем только ту часть красного , которая пересекается с синим , они вставляются в HashSet для удаления дубликатов -> O (n)
2. Выбор точки поворота : подробнее об этом позже -> O (n)
3. Раздел : как только у нас есть точка поворота, мы делим пространство на 3 ^d зоны, одна из которых является центральной, где d - размер (d = 1 для сегментов, 2 для прямоугольников, 3 для кубов и т. Д.))
4. Переделка : мы помещаем красный в разделы, применяя технику отсечения, обратите внимание, что данный красный может в конечном итоге дать несколько фрагментов в разных разделах
5. Рекурсия : мы применяем рекурсивно (начиная с шага 2) к каждому разделу, начиная с наименее заполненного и останавливаясь, как только один из них не покрывается

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

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

Я предлагаю смешать их следующим образом:

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

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

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

Независимость от размерности

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

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

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

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

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

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

РЕДАКТИРОВАТЬ:

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

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

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

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

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

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

Вот подход времени выполнения O (n lg n) с использованием некоторой памяти.

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

Нас интересует только часть сцены, которая содержит прямоугольник «модель»; в этом примере прямоугольник «модели» имеет вид 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. Это может использовать один бит на ячейку, и вы можете рассмотреть возможность использования, скажем, C ++ 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).

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