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

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

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

0

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

Первое - надо определить выпуклый контур или нет. Если не выпуклый то построить вокруг него выпуклый.
Второе - прямоугольник минимальной площади описанный вокруг выпуклого контура всегда лежит на наиболее длинной стороне. Теорема не помню кого но она в задачах раскроя чуть ли не единственная. Соответственно находим наиболее удаленную от прямой на которой лежит самая длинная сторона точку. Параллельная наиболее длинной стороне прямая проходящая через эту точку и есть вторая сторона прямоугольника.
Третье - находим уравнение прямой перпендикулярной наиболее длинной стороне и проходящей через найденную точку. Подставляем в это уравнение все точки контура, находим точки с минимальной и максимальной невязкой. это и есть точки через которые проходят оставшиеся две стороны, перпендикулярные наиболее длинной.

Добавлено через 10 часов 47 минут

Сообщение от gomer_lamer или ширина которого будет наименьшей

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

1

Спасибо за помощь, а что такое невязка?

0

Сообщение от gomer_lamer а что такое невязка?

Разность возникающая при подстановке значений в уравнение. т.е. если в уравнение прямой ax+bx+c=0 в правую часть подставить конкретные значения x и y То получится какое то число. Оно и называтся в данном случае невязкой т.к правая часть равна 0. т.е. невязка это разница правой и левой частями уравнения после подстановки значения переменных. В уравнении прямой невязка по модулю равна расстоянию от точки до прямой а по знаку положению слева или справа от прямой. Соответственно находя точки с макс и мин невязкой получаем точки которые лежат на наиболее удаленных друг от друга прямых параллельных исходной.

0