привет, народ!
я читала много информации в Сети, ничего не нашла по своему вопросу
помогите пожалуйста с моей задачей

нужно создать генерировать мозаику в области в виде прямоугольника

входные данные:
1) тип фигуры (участвуют только многоугольники), 
2) процентное соотношение фигур (допустим, 50% треугольников, 25% квадратов, 25% шестиугольников)

расположение фигур внутри прямоугольника любое

я даже близко не представляю как это сделать... если есть какие-то идеи, напишите пжл

П.С. реализация должна быть на с++

или может подскажете, какие разделы математики нужно применить для решения задачи?

я тут надумала такой вариант, но он мне совсем не нравится

допустим, известно что что в прямоугольную область всего помещается примерно 50 фигур

тогда определяем количество фигур каждого типа (из приведенного выше в моем посте примера получается треугольников - 25шт, квадратов - 13шт (округл. до целого), шестиугольников - 13 шт)

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

ну и начинается исследование этой матрицы и соединение вершин. Там где рисуется фигура, ставится цифра. Чтобы не запутаться, надо ввести обозначения, н-р, треугольники обозначаются цифрой 1, квадраты - цифрой 2 и т.д.
На выходе алгоритма примерно такая матрица:
2 х 2 х 1 х 0 х 0....
х 0 х 1 х 0 х 0 х....
2 х 2 х 0 х 0 х 0....
.............................
Здесь четыре "2" описывают квадрат, а верхняя правая вершина квадрата + две "1" опишут треугольник.

м-да, какой кошмар...

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

PPS05, спасибо за ответ
я сказала матрица потому что сразу думала о методе реализации...
расскажите подробней про сетку, почему 6 соседей?

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

PPS05, а что значит "регулярная сетка"?

...Пришлось поискать, как дать нормальное определение:


Добавлено через 39 секунд
Что-то я завернул...

PPS05, спасибо
все нормально, вроде поняла