Заблокирован
1

Поиск оптимального раскроя

16.01.2017, 03:58. Показов 725. Ответов 3
Метки нет (Все метки)

Здравствуйте, помогите пожалуйста с алгоритмом:

Есть список точек на плоскости, представляющих замкнутый контур. Необходимо найти такой прямоугольник, площадь или ширина которого будет наименьшей.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.01.2017, 03:58
Ответы с готовыми решениями:

Поиск оптимального набора
Здравствуйте. Возникла следующая задача: имеется несколько объектов с различными параметрами,...

Задача оптимального раскроя: распил досок
Всем привет! Никак не могу разобраться с задачей. Требуются комплекты досок, каждый из которых...

Поиск оптимального
Всем добрых суток! ПК собирать буду лишь к новому году в лучшем случае, но прицел на первые три...

Поиск оптимального решения
Помогите с алгоритмом. Есть матрица смежности - С и матрица веса time, время цикла - sum Условие...

3
2054 / 1529 / 167
Регистрация: 14.12.2014
Сообщений: 13,326
16.01.2017, 15:41 2
Цитата Сообщение от gomer_lamer Посмотреть сообщение
Есть список точек на плоскости, представляющих замкнутый контур.
Первое - надо определить выпуклый контур или нет. Если не выпуклый то построить вокруг него выпуклый.
Второе - прямоугольник минимальной площади описанный вокруг выпуклого контура всегда лежит на наиболее длинной стороне. Теорема не помню кого но она в задачах раскроя чуть ли не единственная. Соответственно находим наиболее удаленную от прямой на которой лежит самая длинная сторона точку. Параллельная наиболее длинной стороне прямая проходящая через эту точку и есть вторая сторона прямоугольника.
Третье - находим уравнение прямой перпендикулярной наиболее длинной стороне и проходящей через найденную точку. Подставляем в это уравнение все точки контура, находим точки с минимальной и максимальной невязкой. это и есть точки через которые проходят оставшиеся две стороны, перпендикулярные наиболее длинной.

Добавлено через 10 часов 47 минут
Цитата Сообщение от gomer_lamer Посмотреть сообщение
или ширина которого будет наименьшей
Ширина будет наименьшей у наименьшего по площади прямоугольника. На этом кстати и основано доказательство теоремы о том что минимальный по площади прямоугольник лежит на наибольшей стороне. Там доказывается через тот факт что высота проведенная к самой длинной стороне минимальная.
1
Заблокирован
16.01.2017, 20:26  [ТС] 3
Спасибо за помощь, а что такое невязка?
0
2054 / 1529 / 167
Регистрация: 14.12.2014
Сообщений: 13,326
16.01.2017, 20:37 4
Цитата Сообщение от gomer_lamer Посмотреть сообщение
а что такое невязка?
Разность возникающая при подстановке значений в уравнение. т.е. если в уравнение прямой ax+bx+c=0 в правую часть подставить конкретные значения x и y То получится какое то число. Оно и называтся в данном случае невязкой т.к правая часть равна 0. т.е. невязка это разница правой и левой частями уравнения после подстановки значения переменных. В уравнении прямой невязка по модулю равна расстоянию от точки до прямой а по знаку положению слева или справа от прямой. Соответственно находя точки с макс и мин невязкой получаем точки которые лежат на наиболее удаленных друг от друга прямых параллельных исходной.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.01.2017, 20:37

Поиск оптимального оборудования
Доброго времени, товарищи! =) Помоги пожалуйста советом,идеями, аль чем-нибудь ещё. Собственно...

Поиск оптимального маршрута
Не нашел на форуме подходящей темы и решил создать свою...если уже было--поделитесь ссылочкой ...

Поиск оптимального пути
В БД хранится информация об узлах телекоммуникационной сети и кабелях. Нужно реализовать...

Поиск оптимального софта
Доброго времени суток. Необходим: -Бесплатный -Простой -Занимающий мало места -Не влекущий...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.