Как найти min площадь между фигурами?
Необходим следующий алгоритм: на плоскость раскладываются различные фируры, нужно чтобы они разложились таким образом что бы площадь между ними была наименьшей. Это используется в легкой промышленности, т.е. раскладываются лекала, и нужно разложить их так, что бы выпады ткани были минимальными.
Подскажите, кто знает, как реализовать этот алгоритм, или может есть по этому поводу какая нибудь литература, или ссылки в инете.
Подскажите, кто знает, как реализовать этот алгоритм, или может есть по этому поводу какая нибудь литература, или ссылки в инете.
Имел дело с подобной задачей - самоскладывающимя тетрисом. Нужно было уложить разные фигуры в прямоугольник.
Делал перебором с ограничениями.
Делал перебором с ограничениями.
2Mike немного не то. тут замкнутые произвольные кривые.
2AlenaR категорично утверждать не буду. но ща специально поинтересовался, тетя поведала такое. вроде какой то московский институт не далее чем год назад проводил работу по этому поводу. Они пришли к выводу, что задача не алгоритмическая, как они утверждают, опытный закройщик справляется с этой задачей эффективней, чем существующие программы. есть такой факт, что издание burda при составлении выкроек юзает какой-то собтсвеннфй комплекс. существует "неофициальная статистика" (может есть и официальная..) что в основном народ берет заранее на 20-30% меньше ткани, ибо по тем же самым журнальным выкройкам (лекалам, да?) они используют площадь эффективнее (всмысле на эти самые 20-30%)..
А воообще хотелось бы и самому послушать мнения народа по этой теме...
2AlenaR категорично утверждать не буду. но ща специально поинтересовался, тетя поведала такое. вроде какой то московский институт не далее чем год назад проводил работу по этому поводу. Они пришли к выводу, что задача не алгоритмическая, как они утверждают, опытный закройщик справляется с этой задачей эффективней, чем существующие программы. есть такой факт, что издание burda при составлении выкроек юзает какой-то собтсвеннфй комплекс. существует "неофициальная статистика" (может есть и официальная..) что в основном народ берет заранее на 20-30% меньше ткани, ибо по тем же самым журнальным выкройкам (лекалам, да?) они используют площадь эффективнее (всмысле на эти самые 20-30%)..
А воообще хотелось бы и самому послушать мнения народа по этой теме...
Уж не знаю, как там у закройщиков в московском институте:cool: , но в принципе эта задача вполне алгоритмическая. Если не ошибаюсь, это называется теория размещения блоков. Что-то связанное с топологией. Попробуйте поискать по этим ключевым словам.
Это ж чистая дискретная математика.
Вот смежная задача:
Формулировка задачи одномерного размещения блоков: требуется упорядочить вершины неориентированного графа G = (V, E) с весами на ребрах c (u, v), пронумеровав их числами 1 … n так, чтобы минимизировать ∑i, j = 1…n |i − j|c(vi, vj); n = |V|.
Вершины графа обычно называют "блоками", а веса интерпретируют как количество "проводов" между блоками. Тогда суть задачи становится понятна: требуется расположить элементы на прямой так, чтобы длина проводов, требуемая для их соединения была минимальной.
Эта, а также аналогичная двумерная задача, находят приложение при соединении логических плат и создании интегральных микросхем.
Для нахождения локально-оптимальных решений задачи размещения блоков можно использовать такие локальные преобразования:
Произвести взаимную перестановку смежных блоков vi и vi+1, если результирующий порядок имеет меньшую стоимость. Пусть
L(j) = ∑k=1…j−1 c (vk, vj);
R(j) = ∑k= j+1…nc(vk, vj).
Улучшение можно выполнить, если
L(i) − R(i) + R(i+1) − L(i+1) + 2c(vi, vi+1) < 0
Взять блок vi и вставить его между некоторыми блоками vi и vi+1 при некоторых значениях i и j.
Выполнить взаимную перестановку двух блоков vi и vj.
Это ж чистая дискретная математика.
Вот смежная задача:
Формулировка задачи одномерного размещения блоков: требуется упорядочить вершины неориентированного графа G = (V, E) с весами на ребрах c (u, v), пронумеровав их числами 1 … n так, чтобы минимизировать ∑i, j = 1…n |i − j|c(vi, vj); n = |V|.
Вершины графа обычно называют "блоками", а веса интерпретируют как количество "проводов" между блоками. Тогда суть задачи становится понятна: требуется расположить элементы на прямой так, чтобы длина проводов, требуемая для их соединения была минимальной.
Эта, а также аналогичная двумерная задача, находят приложение при соединении логических плат и создании интегральных микросхем.
Для нахождения локально-оптимальных решений задачи размещения блоков можно использовать такие локальные преобразования:
Произвести взаимную перестановку смежных блоков vi и vi+1, если результирующий порядок имеет меньшую стоимость. Пусть
L(j) = ∑k=1…j−1 c (vk, vj);
R(j) = ∑k= j+1…nc(vk, vj).
Улучшение можно выполнить, если
L(i) − R(i) + R(i+1) − L(i+1) + 2c(vi, vi+1) < 0
Взять блок vi и вставить его между некоторыми блоками vi и vi+1 при некоторых значениях i и j.
Выполнить взаимную перестановку двух блоков vi и vj.