Конференция VBStreets

Доброго времени.
Ищется алгоритм который поможет решить вот такую задачу.
Имеется фигура произвольной формы. Фигуру необходимо покрыть прямоугольниками фиксированной ширины.
Начинать покрытие следует в указанном порядке (либо справа налево, либо слева направо).
Во всех примерах покрытие произведено справа налево.
Желательно учесть, как в последнем примере, возможность исключить определенную область.
Если кто-нибудь знает подобный алгоритм, буду весьма признателен.

На второй картинке как-то очень странно покрыта фигура. Недопокрыта, четвертый прямоугольник выползает (а если покрытие справа налево, то не должен), лишний прямоугольник (7-8 можно заменить одним).
Есть какие-то критерии "хорошести" покрытия? Нужно минимизировать лишнюю покрытую площадь?
Могут ли прямоугольники пересекаться?

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

Вообще, из всех понятна только третья (на первой и понимать нечего). Вторая и четвёртая - окончательно сбивают с толку.

Напоминает разбиение географической карты не фрагменты для удобного хранения.

Debugger писал(а):На второй картинке как-то очень странно покрыта фигура. Недопокрыта, четвертый прямоугольник выползает (а если покрытие справа налево, то не должен), лишний прямоугольник (7-8 можно заменить одним).
Есть какие-то критерии "хорошести" покрытия? Нужно минимизировать лишнюю покрытую площадь?

Да, верно. На второй картинке фигура недопокрыта.
Про четвертый прямоугольник, который выползает. Справедливое замечание, я этот момент забыл описать.
В случаях, когда фигура имеет такую сложную форму, как эта, допустимо, для покрытия "выступов" переключаться в укладку слева на право. Для упрощения, предлагаю, про такие варианты временно забыть. Представим, что все фигуры будут выпуклыми. Такие как на рисунке 3 и 4.
Про 7 и 8 прямоугольник -- это я нарисовал специально, но тоже не прокомментировал. Возможно, что фигура будет покрыта прямоугольниками, в 2 слоя и более.
Критериев "хорошести" покрытия нет. Все что остается -- лишнее и не используется.

Debugger писал(а):Могут ли прямоугольники пересекаться?

Нет. Они только соприкасаются.

Proxy писал(а):Вообще первая моя мысль была разбить изображение на "полосы" (с учётом самой правой или самой левой точки изображения), в каждой полосе найти верхнюю и нижнюю непустую точку, затем ещё найти "выколотые" области и таким образом получить координаты вершин прямоугольников, но нет: 4 картинка как-то совсем мне не понятна.

Не совсем понял, что значит "найти верхнюю и нижнюю непустую точку"
На четвертой фигуре, показана "брешь" в фигуре, которую при заполнении нужно не учитывать. Т.е. если бы бреши не было, то 3 и 4 прямоугольник, были бы одним целым.

shady писал(а):Не совсем понял, что значит "найти верхнюю и нижнюю непустую точку"

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

Еще одно дополнение. Стороны прямоугольников, всегда, параллельны осям координат.