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

← →
zSerg (2004-01-30 14:29) [0]

Кто-нибудь знает алгоритм построения минимального описанного прямоугольника вокруг заданного многоугольника

← →
MBo (2004-01-30 14:33) [1]

Описанный прямоугольник - должен быть параллелен осям координат или нет?

← →
zSerg (2004-01-30 14:36) [2]

Нет

← →
MBo (2004-01-30 14:52) [3]

Тогда поиск в инете по Convex Hull c ограничением по форме оболочки.

← →
zSerg (2004-01-30 15:02) [4]

Нефига не понял

← →
MBo (2004-01-30 15:39) [5]

Ну тогда и поиск не поможет ;) ;(

Одна из сторон искомого прямоугольника (если минимизация по площади) включает сторону приведенного к выпуклому заданного многоугольника. Поэтому надо перебрать все стороны, находя самую удаленную от прямой точку - так задается высот пр-ка и имеющие самые левые и правые (относительно этой прямой) координаты вершины - так находится ширина.
Алгоритм O(n^2), но, думаю, подойдет.

Построение минимального прямоугольниа Найти похожие ветки