Задача компоновки

← →
Newss (2008-12-18 23:18) [0]

Здравствуйте!
Помогите, пожалуйста, с решением задачи компоновки, может есть какой-нибудь алгоритм который можно применить. Суть в том, что задаются плоские фигуры (4-угольники), между ними можно проводить линии связи (по желанию пользователя). Нужно размещенные на поле фигуры разместить так, чтобы они в совокупности занимали как можно меньшую площадь, и при этом линии связи, которые между ними существуют, не пересекались между собой.

← →
charoey_mag (2008-12-19 07:07) [1]

Задача называется "оптимальный раскрой", я правильно понял? В свое время искал но открытых алгоритмов не нашел, в следствии не тривиальности задачи, так как детали ее постановки меняют алгоритм целиком. Так что либо использовать сущетвующие ПО либо писать с нуля.

← →
Дуб © (2008-12-19 07:45) [2]

> Newss (18.12.08 23:18)

Берем четыре точки(маленькие четырехугольники). Все их попарно соединяем. Теперь попробуй удовлетворить своим условиям - чтобы линии не пересекались.

← →
Fynjy84 (2008-12-19 08:34) [3]

> Задача называется "оптимальный раскрой", я правильно понял?

на оптимальный раскрой вроде не похоже

> Берем четыре точки(маленькие четырехугольники). Все их попарно
> соединяем. Теперь попробуй удовлетворить своим условиям
> - чтобы линии не пересекались.

линии и прямые это не одно и то же ... так что без проблем

А по сути вопроса мне сказать нечего ))))

← →
Дуб © (2008-12-19 08:37) [4]

> линии и прямые это не одно и то же ... так что без проблем

А, ты и про кривые линии, не отрезки? В это случае - да. А если 5?

← →
Правильный$Вася (2008-12-19 10:52) [5]

> размещенные на поле фигуры разместить так, чтобы они в совокупности
> занимали как можно меньшую площадь, и при этом линии связи,
> которые между ними существуют, не пересекались

линии имеют площадь или это математич. понятие?

← →
KilkennyCat © (2008-12-19 11:02) [6]

раскрой + разводка печатных плат получается

← →
Правильный$Вася (2008-12-19 11:18) [7]

> разводка печатных плат получается

причем однослойных, если пересечения недопустимы

← →
Newss (2008-12-19 13:34) [8]

А если без линий связи, просто организовать оптимальное размещение фигур на заданной площади? Это как-то можно сделать?

> Это как-то можно сделать?
>

Ну, как-то это же делают ? :))
Значит можно.
Рецепт очень прост - исследуем доступные источники по нужной теме, изучаем/учимся, пробуем реализовать,а вот с обсуждением проблем - на форум.

← →
Правильный$Вася (2008-12-19 15:34) [10]

> оптимальное размещение фигур на заданной площади

этот класс задач так и называется "задачи плотной упаковки"

> этот класс задач так и называется "задачи плотной упаковки"

Это частное определение.

Задача компоновки Найти похожие ветки