Алгоритм «исцеления» нескольких прямоугольников в меньшее количество прямоугольников?

10 голосов | спросил xaxxon 9 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 09 Sep 2016 00:58:32 +0300 2016, 00:58:32

1 ответ


12

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

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

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

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

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

Одним простым способом является объединение горизонтальных прогонов соседних квадратов в длинные тощие прямоугольники. Затем мы можем сравнить с приведенной выше строкой и объединить, если наш запуск начнется & заканчивается совпадением - либо по завершении каждого пробега /строки, либо по мере того, как мы рассматриваем каждую ячейку для добавления к текущему прогону.

 Разложение полиомино в горизонтальные прогоны, затем слияние по вертикали

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

 Пример случая с 3-прямоугольным решением, где найденный выше метод 4

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

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

Еще один метод, который я ищу, - это сделать первый запуск, найденный в верхней строке & продлите его, насколько сможете. Затем сделайте первый прогон в верхнем ряду того, что осталось ... Это получается на инвертированных T-образцах, поэтому оно также не оптимально.

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

ответил DMGregory 9 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 09 Sep 2016 03:20:24 +0300 2016, 03:20:24

Похожие вопросы

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

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132