Задача такая. Даны координаты вершин многоугольника. Нужно покрыть этот многоугольник квадратами с фиксированной длинной стороны так, чтобы число квадратов было минимальным. Все перечесения диагоналей квадратов должны при этом принадлежать области ограниченной многоуголькиком. Решать задачу нужно на С++, но на данный момент нужен сам алгоритм.

Решить эту задачу математически не могу, так же как и в общем случае    Упрощенную задачу, когда все углы многоугольника равны 90 градусов тоже смог ршить только через Ж    Для этого:

1) Строю точечный рисунок - фон. Это большой квадрат одного цвета (скажем зеленого). 

2) В нем рисую данный многоугольник и закрашиваю его другрм цветом (синим).

3) Описываю данный многоугольник другим большим квадратом (ничего не рисуя) и выбираю один из 
его углов совпадающих с какой-либо вершиной многоугольника. Эта исходная точка.

ДАЛЬШЕ ИДЕТ ЦИКЛ: Х-овая координата исходной точки изменятеся от ее начального положения до плюч/минус сторона квадрата. То же во вложеном цикле делаю с У-ковой координатой, таким образом перебираются покрытия. Получается разумеется перебор не всех покрытий, которых бесконечное число, а перебор их конечного подмножества.

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

5) В полученой сетке все квадраты, пересечение диагоналей которых не принадлежит многоугольнику, а одна из вершин принадлежит (определяю это по цвету пикселя с координатами вершин и пересечения диагоналей) , смещаю так, чтобы пересечение диагоналей стало принадлежать многоугольнику (имело синий цвет, а не зеленый). ИМЕННО НЕОБХОДИМОСТЬЮ ВЫБОРА НАПРАВЛЕНИЯ СМЕЩЕНИЯ ОБУСЛОВЛЕНО УПРОЩЕНИЕ ЗАДАЧИ до случая многоугольника с углами в 90 градусов.

КОНЕЦЦИКЛА


6) Из всех покрытий полученных в цикле выбираю то, которое содержит наименьшее число квадартов.


Если кто нибудь встречал алгоритм проще или универасльнее - поделитесь пожалуйтса информацией. Конечно желательно чтобы в последующем была возможность превратить его словесное описание в програмную реализацию.  Заранее спасибо за ответы   

Это центр, что ли?

Да, центр.

Здравствуйте, WaldemarL,

Испольуете ли вы какую-нибудь вспомогательную литературу по Вашему вопросу? = Вот, поприставал к поисковикам, нашёл и загрузил для Вас статью, по-моему неплохую :

A Linear Time Approximation Algorithm for Minimum Rectangular Covering (Приближённый Линейный по Времени Алгоритм Минимального Покрытия [Полигона] Прямоугольниками). Там в абстракте такая же постановка задачи.

А то, наверно, с нуля изобретать будет слишком долго...

Это сообщение отредактировал(а) marcusmae - 21.11.2007, 01:25

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