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

Question

У меня есть N прямоугольников со сторонами, параллельными осям X и Y.Есть еще один прямоугольник, модель .Мне нужно создать алгоритм, который бы мог определить, полностью ли модель покрыта N прямоугольниками.Я думаю, что сначала мне нужно отсортировать прямоугольники по их левой стороне (это можно сделать за O (n log n) время), а затем использовать вертикальную прямую линию.

Синий прямоугольник - это модель .

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

Это одна из задач по подготовке к тесту.Я знаю, что лучший алгоритм может сделать это за O (n log n) времени.

Answer 1

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

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

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

Answer 2

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

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

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

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

Алгоритм

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

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

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

Предлагаю смешать их так:

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

Другим аспектом реализации является Tail рекурсии. Как и 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, это наш стержень.

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

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

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

Answer 3

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

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

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

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

Этот заказанный набор будет содержать строки top и bottom каждого из red с, если они находятся между 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 прямоугольник и указывает на его наличие или отсутствие. Они упорядочены по индексу.
• Каждый промежуточный узел будет иметь для значения самый правый интервал, охватываемый его дочерними элементами

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

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]

Корень может не указывать точный набор охватываемых интервалов: только самый правый охватываемый интервал. Тем не менее, нам достаточно сказать, полностью ли покрыто 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), в зависимости от используемого алгоритма сортировки.

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 7

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

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

1. Площадь ваших N прямоугольников
2. Площадь ваших N прямоугольников и модель

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

Answer 8

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

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

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

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

Answer 9

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

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

Answer 10

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

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

1. Создать список всех уникальных X-координат левого и правого краев (в одном списке)
2. Когда вы строите этот список, для каждой координаты также связываете с ней список прямоугольников и указывает в этом списке, является ли X-координата, с которой связан список, левой или правой кромкой прямоугольника
3. Сортировка списка координат по возрастанию слева направо
4. Создать новый список прямоугольников, изначально пустой
5. Пробежаться по списку координат и обработать для него связанный список прямоугольников
6. Все прямоугольники в связанном списке, которые обозначены как имеющие координату в качестве левого края, должны быть добавлены в список, который вы создали в 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=[] и начинаете обработку координат и связанных прямоугольников:

Х = 1

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

* * Х тысяча шестьдесят-восемь = 2

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

* 1 072 * Х = 3

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

* * Х тысяча семьдесят шесть = 4

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

Х = 5 и Х = 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. Top = A, Bottom = (нет)
2. Top = C, Bottom = (нет)
3. Верх = B, Низ = (нет)
4. Верх = (нет), Низ = C
5. Верх = (нет), Низ = A
6. Верх = (нет), Низ = 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]

* * 1 134 Y = 6

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

Конечный результат:

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

• (3, 1) - (4, 2) - A
• (3, 2) - (4, 3) - А, С
• (3, 3) - (4, 4) - А, В, С
• (3, 4) - (4, 5) - А, В
• (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 - это, в основном, диапазон от одного значения к другому, поэтому в дополнение к приведенному выше алгоритму требуется немного построения и обслуживания данных.