Прямоугольник, наилучшим образом приближающий выпуклый четырехугольник

[WW_]

Пусть на плоскости задан выпуклый четырехугольник набором координат своих вершин: (предположим, что вершины перечислены в порядке обхода по часовой стрелке).
Стоит две задачи:
1) Найти прямоугольник наилучшим образом приближающий заданный прямоугольник. Под "наилучшим образом" понимается то, что площадь отсекаемых (добавленных) фигур минимальна.
2) Найти MBR (minimum bounding rectangle) - описанный прямоугольник минимальной площади (для заданного выпуклого четырехугольника).

Вторую задачу решить даже важнее.

2) Найти MBR (minimum bounding rectangle) - описанный прямоугольник минимальной площади (для заданного выпуклого четырехугольника).

http://en.wikipedia.org/wiki/Minimum...box_algorithms

[WW_]

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

Ну, там задача всего с пятью параметрами - угол и ординаты/абсциссы сторон. И целевой функционал непрерывен по ним. По-моему, тут проще всего будет забабахать любой метод численной (не-градиентной) оптимизации, см. http://cs.gmu.edu/~sean/book/metaheuristics/
Генетику там, или дифференциальную эволюцию попробуй.

не-градиентной

хотя нет, вру. Градиент везде есть, это всего лишь второй производной иногда нет. Так что все у вас хорошо с задачей в численном плане.

[prografix]

А критерий первой задачи изменить можно?
Например, я для аппроксимации многоугольника прямоугольником использую такой подход - центры масс и моменты инерции двух фигур должны совпадать.

[WW_]

А критерий первой задачи изменить можно?
Например, я для аппроксимации многоугольника прямоугольником использую такой подход - центры масс и моменты инерции двух фигур должны совпадать.

Спасибо, это интересно. Можно поподробнее, пожалуйста.
Совпадение центров масс даст сразу точку пересечения диагоналей (центр прямоугольника). Остается еще 3 параметра (например, поворот, высота и ширина). Как получить их из совпадения моментов инерции?
Приравнять осевые моменты инерции и центральные моменты инерции?

Вообще, очень интересно, попробую обязательно. Еще раз спасибо.

[prografix]

Детали этого алгоритма объяснить непросто, но у меня уже есть программа на С++ (ссылка), которая это делает.

[prografix]

Хочу добавить, что при использовании моментов 2-го порядка для некоторых фигур ( например, для правильных многоугольников ) максимальный и минимальный моменты равны друг другу, и в этом случае направления осей инерции не определены. Известно только, что аппроксимирующий прямоугольник - это квадрат, а также его размеры и положение центра. Осталось найти его поворот. Это можно сделать путём нахождения максимума площади пересечения квадрата и исходной фигуры. Эту одномерную оптимизацию можно сделать при помощи метода золотого сечения.