Как вписать произвольную фигуру в фигуру, которая состоит из прямоугольников N x M ?

Question

[Антон Марцен]

Здравствуйте!

В какую сторону копать при решении этой задачи?
Немного ее поясню графически:
Задан некий прямоугольный участок размером N x M

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


Прямоугольники необязательно должны быть вплотную друг другу. Можно (и даже лучше), чтобы они наезжали друг на друга.

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

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


Update2:
Фигура, которую нужно вписать задается при помощи множества точек на плоскости. Например, приходит массив [{x1,y1}, {x2,y2},{x3,y3}] и поочередно их соединяя будет получен треугольник.
В простейшем случае точки будут соединены прямыми линиями. Соединение при помощи сплайнов пока не рассматривается.

Answer 1

[Sergey Lerg]

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

Comments

[Антон Марцен]

Т.е. сначала вписываем фигуру в прямоугольник, а потом бьем на сетку и дальше по сценарию?

[Sergey Lerg]

martsen: да.

[Антон Марцен]

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

[Sergey Lerg]

martsen: увеличить разрешение, т.е. уменьшить размер прямоугольников. Вот метод эффективного объединения фигур в прямоугольники
stackoverflow.com/questions/5919298/algorithm-for-...

[Антон Марцен]

Sergey Lerg: отличная ссылка. А ссылки, которые внутри еще более интересные. Спасибо за наводку. Посмотрю, что там есть.

Answer 2

[Виталий Пухов]

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

Comments

[Виталий Пухов]

Вообще для растра задачу можно решить "в лоб", если исключить перекрытия, т.к. они не имеют смысла и ничего не экономят. Можно разместить фигуру и определить размер прямоугольника, после сформировать "сетку" с размером ячейки равной размеру прямоугольника, далее смещая данную сетку по обоим осям последовательно (понадобится X*Y шагов, где X и Y размер прямоугольника) в каждом смещении нужно посчитать количество прямоугольников, которые содержат хотябы 1 часть фигуры, выбрать то смещение сетки, при котором количество листов будет минимальным.
Далее можно провести "оптимизацию" полученной схемы, производя смещения рядов, и вычисляя число листов занятых изображением, выбирая минимальное смещение. После оптимизации рядов оптимизация столбцов будет невозможной из за смещения рядов, то есть тут нужно по идее провести оптимизацию столбцов и посчитать число листов занятых изображением, затем вернуть все обратно к первоначальному смещению и повторить оптимизацию для столбцов, посчитать сколько занято листов и выбрать какая оптимизация была лучше. Алгоритм не гарантирует "алгоритмического" решения, но даст высокое качество результата.

[Виталий Пухов]

Neuroware: Можно провести еще дополнительную оптимизацию, смещая все ячейки с наложением, но тогда нужно будет контролировать что не образовалось частей изображения не перекрытые листом, что проблематично

[Антон Марцен]

Спасибо за развернутый ответ!

К тому же не ясно из задачи чем задается та самая фигура, это векторная фигура или растр, в зависимости от этого и будет алгоритм

Изначально на вход я получаю набор точек на плоскости. Замыкая их получается фигура.
Получается у меня фигура задана в векторном формате (или я ошибаюсь?).

[Антон Марцен]

Neuroware: в целом вы предложили понятный и простой способ найти искомую комбинацию квадратиков, но если сам квадратик будет относительно маленький по сравнению с фигурой, то получится очень много переборов во время оптимизации. Но пока я другого варианта сам не вижу...

[Антон Марцен]

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

[Lynn «Кофеман»]

> если исключить перекрытия, т.к. они не имеют смысла и ничего не экономят
Если фигура невыпуклая, то вариант с перекрытиями может быть оптимальнее.

[Виталий Пухов]

Алексей Тен: Не совсем так, в предложенном мной алгоритме если фигура скажем бублик то в дырке по центру прямоугольник не берется совсем, поэтому для невыпуклых это правило тоже будет работать, хотя с наложением можно уменьшить степень "незаполненности" прямоугольников при желании

[Lynn «Кофеман»]

Neuroware: Вот эту гантелю нельзя покрыть без перекрытий пятью прямоугольниками.

[Виталий Пухов]

Алексей Тен: согласен, не для всех случаев алгоритм будет эффективен, он будет эффективен только если размер прямоугольника много меньше размера фигуры. В подобных случаях он будет менее эффективным. в таком случае нужно "Можно провести еще дополнительную оптимизацию, смещая все ячейки с наложением, но тогда нужно будет контролировать что не образовалось частей изображения не перекрытые листом, что проблематично" придется как то так делать, но это довольно сложно реализовать.