уменьшение перекрытия в случайных прямоугольниках

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

Начните с целого прямоугольника

--------
|      |
|      |
|      |
|      |
|      |
--------

Разделите в случайной точке и сохраните два прямоугольника.

--------
|      |
|------|
|      |
|      |
|      |
--------

Разделение случайного прямоугольника в случайной точке

--------
|      |
|------|
| |    |
| |    |
| |    |
--------

повторите. . .

--------
|      |
|------|
| |    |
| |----|
| |    |
--------

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

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

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

1. Самое простое решение

Создайте набор всех квадратов (области 1), которые покрыты прямоугольниками входного набора. Квадрат - это прямоугольник ... вот и вы!

2. Минималистское решение?

Хорошо, это было опрометчиво, однако я не думаю, что вам стоит беспокоиться о входном наборе. На самом деле ваша проблема в другом:

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

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

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

Две опции ползут в верхней части моего списка:

MDHT - https://www.projects.openhealthtools.org/sf/projects/mdht/

оплетка - http://braid.sourceforge.net

MDHT имеет много дополнительных компонентов, помимо того, что НЕОБХОДИМО для производства или потребления и использования сообщений CDA/CCD. Оплетка предположительно доказана, приняв участие в нескольких IHE Connectathons.

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

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

Хотя ограничение System.Enum запрещено C #, в .NET и C # можно использовать типы или методы с такими ограничениями. Смотрите библиотеку Jon Skeet Unconstrained Melody , которая включает код, который делает именно то, что вы хотите.

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

Числите ваши начальные прямоугольники от 1 до N. Начиная с прямоугольника 1 цикл до тех пор, пока вы не найдете пересекающийся прямоугольник. Создание новых прямоугольников. Удалите два пересекающихся прямоугольника и добавьте 3 или более вновь созданных прямоугольников в набор и начните заново.

Результатом будет целый набор неперекрывающихся прямоугольников. Создает ли это наименьшее количество прямоугольников? Возможно, нет, но вы не указали, что минимизация количества прямоугольников была важна. Занимает ли это время o (n ^ 2)? Наверное.

Сначала создайте набор всех "атомарных" прямоугольников в композиции, то есть областей, образованных пересечениями прямоугольников и не подразделяющихся на части. Каждый реальный прямоугольник покрывает один или несколько атомных прямоугольников. Затем запустите комбинаторный алгоритм оптимизации, например. SETCOVER, чтобы вычислить минимальное количество прямоугольников, которое вам нужно, чтобы покрыть их все.

Вот иллюстрация подхода. У вас есть три прямоугольника (A, B, C). Они создают 5 атомных областей (1-5):

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

Прямоугольники покрывают атомные области в соответствии с этой таблицей:

 A  {1,2,4}
 B  {2,3,4,5}
 C  {4,5}

Задача SETCOVER теперь состоит в том, чтобы выбрать минимальное подмножество прямоугольников {A, B, C} так, чтобы все атомные области покрываются, когда вы объединяете атомные области, покрытые прямоугольниками. Минимальное решение (очевидно)

 A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}

Обратите внимание, что здесь области не прямоугольные, например область 3 имеет сложную форму.Вы можете избавиться от этой проблемы, используя следующий подход: возьмите все различные X-координаты угловых точек исходных прямоугольников и рассмотрите их как X-координаты сетки и проделайте то же самое с Y-координатами; тогда каждый прямоугольник покрывает набор квадратов сетки, которые никогда не делятся на части, то есть:

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

 |    |  | |   | |

Что дает вам следующую сетку 5x5:

 AAA      A = rectangle A only
 A**BB    B = rectangle B only
 A*#CB    * = A and B
  BCCB    C = rectangles C and B
  BBBB    # = All

Из этого вы можете легко выделить 5 областей; на самом деле они уже были отмечены :) (A, B, C, *, #)