Итак, расстановка...
Для расстановки будем использовать генетические алгоритмы. Звучит страшно, но на деле это самое простое.
Какие нужны будут функции.
1. Самая сложная функция расстановки. По заданным параметрам нужно оптимально расставить объекты в заданном пространстве. Функция сложная т.к. фактически совпадает с поставленной задачей. Поэтому мы поступим хитрее, а именно: заменим сложную функцию простой и добавим элемент интеллекта в виде генетического отбора.
Итак простая функция расстановки получает на вход по порядку все контуры для которых заданы:
- Поворот.
- Положение относительно оси X
- И, соответственно, порядок в котором они приходят.
Функция должна определить минимальное значение координаты Y.
Т.е. все выглядит так, как будто мы бросаем по очереди контуры сверху в стакан и они падают на самый низ. Но, т.к. функция простая, то она не учитывает гравитацию, отскоки и всякие повороты. Т.е. просто опускает контур как можно ниже. Т.к. функция должна работать быстро, то мы заменим кривые Безье на их выпуклые оболочки, чтобы уменьшить количество вычислений. (На рисунке пример работы функции, только поменян верх и низ, но это не важно
)
2. Теперь нам нужна интеллектуальная функция которая будет формировать последовательности в которых мы будем разбрасывать контуры, их повороты и смещение по оси Х. Для этого мы будем использовать генетические алгоритмы. Они работают так:
1. Сначала создаем 100 случайных последовательностей. Это наша начальная популяция.
2. Передаем наши последовательности функции расстановки. И вычисляем характеристическую функцию (За этим страшным названием кроется простой критерий "хорошести" расстановки, например площадь готовой расстановки).
3. Затем из нашей популяции выбираем 10-20 лучших экземпляров. И скрещиваем их, т.е. меняем берем кусочек от одной последовательности и вставляем в другую. Элементы последовательностей и есть те самые "гены". Таким образом делаем 40 потомков, к ним добавляем 30 "мутантов" потомки со случайно измененными генами и 20 случайных "особей".
4. Повторяем все с шага 2.
