Страницы: 1
RSS
min площадь прямоугольника внутри которого многоугольник
 
Здравствуйте. Не могу найти алгоритм. Точнее могу но сомневаюсь в правильности его.

Исходные данные:
фигура на плоскости -выпуклый многоугольник .(Если невыпуклый, то он легко преобразовывается в выпуклый нехитрым алгоритмом.). Данные в виде последовательных координат. (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уществует ли такая фигура при которой контейнер может не использовать коллинеарность с данной фигурой.
Если нет, то алгоритм верен.
Изменено: Sla_0412 - 19.06.2017 18:05:12
Страницы: 1
Наверх