Текущий архив: 2004.02.25;
Скачать: CL | DM;
Вниз
Построение минимального прямоугольниа Найти похожие ветки
← →
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), но, думаю, подойдет.
Страницы: 1 вся ветка
Текущий архив: 2004.02.25;
Скачать: CL | DM;
Память: 0.47 MB
Время: 0.022 c
