Поиск всех прямоугольников в заданном прямоугольнике, которые не пересекаются с произвольной формой

Question

Мне нужно найти алгоритм, чтобы найти наименьшее число Число перекрывающихся прямоугольников в заданном прямоугольнике R, которые не пересекаются с объединением множества другие прямоугольники, содержащиеся внутри R. Эти внутренние прямоугольники могут перекрываться. Вот ужасный ASCII рисунок примера R:

A-----------------B-------------------------+ 
|           | 
|           | 
|           | 
|           | 
|     +--------+    | 
|     |........|    | 
|     |........|    | 
C    +---D........|    | 
|    |.........+--+    | 
|    |.........|     | 
|    ++........+------+   | 
|    |...............|   | 
G    +---H...........|   | 
|     |...........|   | 
|     |...........|   | 
|     |...........|   | 
|     +-----------+   | 
|           | 
|           | 
|           | 
E-------------I----F------------------------+ 

Прямоугольники здесь будет включать (A, D), (A, I), (G, F). Это похоже на проблему, для которой решение хорошо понято, но для которого мне просто не хватает словарного запаса. Любые ответы, указатели, RTFM приветливо и с благодарностью принимались. Благодаря!

EDIT: В соответствии с приведенным ниже наблюдением Павла, я пытаюсь найти набор прямоугольников, которые покрывают пространство в R, не покрывая какой-либо из многоугольников, состоящих из объединения внутреннего множества. Если это имеет смысл.

Answer 1

Я считаю, что это один из возможных способов решения проблемы.

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

Прежде всего, давайте предположим, что мы имеем структуру данных, пригодную для поиска на перекрестке. Одной из возможных структур данных является Interval Tree, используя точки в одной из координат как интервалы (например, если прямоугольник определяется двумя точками (x0, y0) и (x1, y1), используйте (x0, y1) как интервал. Ссылка также объясняет, как перейти к более высоким измерениям (в вашем случае вам нужно 2).

Я не буду подробно описывать реализацию такой структуры данных, но предположим, что у нас есть один из них: Rectangles, с Следующий по API определен:

• void add(Rectangle r)
• void remove(Rectangle r)
• Rectangle[] getIntersecting(Rectangle r)
• Rectangle[] getAdjacent(Rectangle r)

Хорошо, теперь создать два экземпляра Rectangles под названием black и white. Инициализируйте white со всеми белыми прямоугольниками. Initializie black с прямоугольником R (весь домен).

1. Для каждого прямоугольника rw в white получить массив arr пересекающихся прямоугольников от черного.
2. Для каждого прямоугольника rb в black определите результат rw-rb. Это набор set из 0, 1, 2, 3 или 4 прямоугольников, в зависимости от того, как пересекаются два прямоугольника.
3. удалите rw от white и добавьте в него содержимое set.Это может потребовать объединение прямоугольников из set с прямоугольником уже в white, если такие прямоугольники вместе образуют прямоугольник большего размера (они прилегающую обмен одна стороны)
4. удалить rb из black
5. повтора от 1 до тех пор, пока не останется больше прямоугольников black

Answer 2

Используя основы математики, мы могли бы сказать, что решение вашей проблемы будет разложение прямолинейного многоугольника R \ union(rs), где union(rs) представляет собой многоугольник внутри R. Расчет R \ union(rs) может быть выполнен с использованием Greiner-Hormann-algorithm. Обратите внимание, что этот шаг приведет к многоугольнику с отверстиями и - только если внутренний многоугольник содержит отверстия - несколько других полигонов. Разложение описано here (это только приближение, но пока я не смог найти точный алгоритм).