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

Question

[Александр risok]

Есть вот задача 2д упаковки контейнера (плоскости) определенными фигурами и есть алгоритмы для ее решения. А если задачу усложнить и теперь нужно не только расставить фигуры лучшим образом, но и соединить все эти фигуры между собой "дорогой" шириной 1 клетку.

Comments

[Александр risok]

Answer 1

[Сергей Соколов]

По периметру каждой фигуры должна идти дорога? Может, её сразу учесть и «растолстить» каждую фигуру на пол-клетки? А далее решать как и раньше )

Comments

[Александр risok]

Нет. Соединить все фигуры, то есть касались бы хоть одной клеткой.

[Сергей Соколов]

Александр Ржаницын, нужна ли "дорога", если фигуры имеют общую грань? Т.е. стоят вплотную.

[Александр risok]

Все фигуры должны касаться дороги

[Сергей Соколов]

Александр Ржаницын, иллюстрация не помешала бы..

Answer 2

[profesor08]

Расставил фигуры, определил в каждой центр, провел линию от одной до другой, и так по всем.

Comments

[Сергей Соколов]

Триангуляция Делоне тут пригодится?

[Александр risok]

Линия "дорога" занимает место, и это плоскость, нельзя поверх фигур проводить.

[profesor08]

Александр Ржаницын, значит вообрази их грани как граф, это и будет тебе сеть дорог. Выбери любую ветвь и у фигур, через которые она проходит, откусывай по куску.

Если сложно все это представить, то сделай дорогу, она разделит твою плоскость на отдельные плоскости, их и заполняй фигурами.

Answer 3

[Александр Зачиналов]

Ваша логика напомнила мне алгоритмы расстановок кораблей в игре "Морской бой". Есть в сети гайды, можно их изучить и адаптировать для себя. Например: cleanjs.ru/articles/igra-morskoj-boj-na-chistom-ja...