Алгоритм размещения случайных многоугольников в заданном прямоугольнике

У меня есть набор из 20 (пример) 2D-полигонов, начиная от треугольников, 4-сторонних неправильных, 5-сторонних до 6-сторонних полигонов. Некоторые из них почти идеальные прямоугольники, некоторые совершенно неправильной формы. Все они будут иметь от 3 до 6 сторон, максимум.

У меня также есть прямоугольник, скажем, 16 на 9, так как это типичное соотношение сторон для экранов.

Моя цель — найти способ сложить многоугольники внутри прямоугольника, затрачивая минимум места.

Я могу вращать их, масштабировать вверх или вниз, перемещать в любое место внутри прямоугольника. Единственное правило состоит в том, чтобы делать это, сохраняя их визуально приятными (не делайте их слишком большими или слишком маленькими, не поворачивайте их более чем на +- 45 градусов, если это возможно).

Как и просили, вот пример изображения:

введите здесь описание изображения

Слева мы видим приемлемый результат, а справа вход.

Я думал научить ИИ выполнять эту работу, но есть ли какой-нибудь алгоритм, который может помочь с этим?
Имейте в виду, что как только я поместил несколько полигонов в прямоугольник, я процедурно продолжу добавлять к нему новые по запросу. .


javascript algorithm geometry bin-packing polygons
person Kristian    schedule 04.05.2017    source источник
comment
Не учите ИИ выполнять эту работу, найдите алгоритм, который считывает набор 2D-уловок, и сделает работу за вас. Я могу помочь вам выбрать правильный или реализовать его, но вам нужно больше объяснить мне свою проблему.   -  person Oussama Ben Ghorbel    schedule 05.05.2017
comment
Усама, я думал, что объяснил, но в любом случае:   -  person Kristian    schedule 05.05.2017
comment
У меня есть холст (на основе SVG), который действует как прямоугольник. В этом прямоугольнике я хочу заполнить различные треугольники и многоугольники с числом сторон до 6. Я могу вращать, масштабировать и перемещать любой из них. Я не хочу, чтобы они перекрывались, и я не хочу, чтобы они оставляли пробелы. Если многоугольник находится в левом или правом углу, я могу сделать так, чтобы он выходил за пределы прямоугольника (немного), чтобы все было максимально заполнено.   -  person Kristian    schedule 05.05.2017
comment
Для такого рода вопросов вам, вероятно, следует добавить одно или несколько изображений, чтобы объяснить, каков желаемый результат.   -  person m69 ''snarky and unwelcoming''    schedule 05.05.2017
comment
Спасибо за помощь/хотя бы попытку. Я добавил изображение, описывающее приемлемое решение проблемы (скорее всего, не самое лучшее). На изображении вы видите несколько примеров того, с чем БУДЕТ столкнуться программа, и если она сможет их сортировать хотя бы так же плохо, как я в фотошопе, я буду повиноваться богам ИИ во веки веков. Обратите внимание, что полигоны были повернуты (+/-45º), масштабированы (не слишком большие и не слишком маленькие) и явно перемещены.   -  person Kristian    schedule 05.05.2017
comment
гугл bin-packing   -  person Spektre    schedule 05.05.2017

Ответы (1)


arrow_upward
0
arrow_downward

Если вы хотите, чтобы ИИ решал эту проблему, вам нужно установить функцию полезности, которую нужно оптимизировать.

Его можно определить с точки зрения:

  • Непрерывная используемая площадь (например, насколько хорошо детали подходят друг к другу)

  • Площадь деталей внутри

  • Площадь деталей снаружи

person arboreal84    schedule 05.05.2017