Здравствуйте. Не могу найти алгоритм. Точнее могу но сомневаюсь в правильности его.
Исходные данные: фигура на плоскости -выпуклый многоугольник .(Если невыпуклый, то он легко преобразовывается в выпуклый нехитрым алгоритмом.). Данные в виде последовательных координат. (2 массива x(),y()) Нужно найти координаты прямоугольника-контейнера, который имеет минимальную площадь для многоугольника. Сам я думаю что алгоритм следующий: 1.Цикл начнем с первого отрезока x(i) y(i)-x(i+1),y(i+1) 2 Вторым циклом J перебираем точки начиная с 3 x(j),y(j) и формулой точка перпендикуляр к линии находим мах точку (эдакий штангенциркуль) длина будет первой стороной a 3.Вычисляем все точки по левую и по правую сторону перпендикуляра формулой d = (x0 - x1) * (y2 - y1) - (y0 - y1) * (x2 - x1) если D>0 то первая сторона, если D<0 то вторая сторона для D<> 0 находится max значение длины если D=0 то длина =0 складываем max(D>0) с max(D<0)=b вторая сторона 4 stemp=a*b 5 заканчиваем J 6 Если s<stemp то s=stemp 7 заканчиваем i
Картинка не правильно составлена но суть отражает (там где невыпуклость будем считать что вершины ее образующие удалены из цепочки ...дуга и острый угол)
Исходя из темы у меня один вопрос , существует ли решение по поиску min S, при котором ни одна сторона контейнера не образовывает коллинеарность с любой из сторон многоугольника? Тот же вопрос, но по другому: Cуществует ли такая фигура при которой контейнер может не использовать коллинеарность с данной фигурой. Если нет, то алгоритм верен.