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

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

> Newss   (18.12.08 23:18)  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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