Алгоритм покрытия произвольной фигуры прямоугольниками

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
shady
Постоялец
Постоялец
 
Сообщения: 461
Зарегистрирован: 09.11.2005 (Ср) 11:03

Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение shady » 27.02.2011 (Вс) 13:04

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

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение Debugger » 27.02.2011 (Вс) 14:31

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

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение Proxy » 27.02.2011 (Вс) 15:24

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

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4272
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение iGrok » 27.02.2011 (Вс) 15:32

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

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение Proxy » 27.02.2011 (Вс) 15:37

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

shady
Постоялец
Постоялец
 
Сообщения: 461
Зарегистрирован: 09.11.2005 (Ср) 11:03

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение shady » 27.02.2011 (Вс) 16:06

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

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

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

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

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение Proxy » 27.02.2011 (Вс) 16:15

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

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

shady
Постоялец
Постоялец
 
Сообщения: 461
Зарегистрирован: 09.11.2005 (Ср) 11:03

Re: Алгоритм покрытия произвольной фигуры прямоугольниками

Сообщение shady » 27.02.2011 (Вс) 17:36

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


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6

    TopList