Re: Размещение фигур

From

Andrew Vlasov ()

To

Pavel Murtishev

Date

2002-11-05T17:24:22Z

Area

RU.ALGORITHMS

From: "Andrew Vlasov" <vlas@dicomp.ru>


что-то типа?
http://kusnetsov.sapa.sib.ru/raskroy/description.asp
Программа раскроя позволяет производить построение карты оптимизированного
раскроя промышленных материалов, например, ДСП (при изготовлении мебели),
стекла или любых других листовых или рулонных материалов
или http://cuttinghome.com/


Мне думается что, можно использовать физическую модель, укрупненно:
1) раскидать подальше, чтобы не пересекались
2) имитировать силу притяжения по любому закону(например тяготения)
3) маленькими шажками двигать пока не упрутся(здесь нужно продумать алгоритм
отката или восстановления)
4) одновременно трясти генератором случайных чисей по X,Y на размер <
размера шага, и одновременно случайно вращать(правильно подобрав величину
возмущения) для более полной оптимизации
3-4 - повторять пока все формы не выйдут на ограничения

--
С уважением, Андрей.
Best regards, Andrew.
Respectfully yours, Andrew.

"Pavel Murtishev" <Pavel.Murtishev@f1378.n5030.z2.fidonet.org>
сообщил/сообщила в новостях следующее:
news:1036499509@f1378.n5030.z2.FidoNet.ftn...
> Здравствуй, All.
>
> Есть несколько замкнутых кривых произвольной формы, для конкретики возьмем
три
> эллипса с разными осями. Есть прямоугольник известных размеров. Необходимо
> разместить фигуры (эллипсы) на прямоугольнике таким образом, чтобы площадь
> прямоугольника, охватывающего все фигуры была нимимальна.
>
>            a                          a
>       ------------              --------------
>       |oo        | b            |o      o    |b
>       |o         |              |  o         |
>       ------------              --------------
>
>           Верно                    Не верно
>
> a, b - известны
>
> В каком направлении думать? :]
>
> До свидания.
>

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)