Апроксимирующие эллипс, прямоугольник, треугольник

[Andr]

Дана плоская фигура, заданная маской (по сути массив, в котором значение 0 соответствует фону, 1-объекту). Необходимо решить следующие задачи:
1. Подобрать для объекта аппроксимирующий эллипс (определить оси и угол меду горизонтальной осью и главной осью эллипса)
2. Подобрать для объекта аппроксимирующий прямоугольник (определить стороны прямоугольника и угол)
3. Подобрать для объекта аппроксимирующий треугольник

Поискав в сети и на этом форуме, я пришел к выводу, что задачи [1] и [2] лучше решать через вторые моменты (равенство вторых моментов объекта и аппроксимирующих фигур). Но пока я так и не понял как это сделать. Может кто пояснит как это сделать или даст ссылку на теорию, где можно доступно почитать (имеется ввиду не пояснение, что такое моменты второго порядка, а как перейти от моментов к параметрам аппроксимирующих фигур).

Как решить задачу [3] пока даже предположений нет.

Заранее спасибо за ответы.
P.S.: ветки форума эту и эту видел. Но там только ссылка на готовую реализацию, а мне бы понять суть этих алгоритмов.

[prografix]

> как перейти от моментов к параметрам аппроксимирующих фигур

Для таких фигур, как эллипс и прямоугольник существуют формулы, как вычислить по ним моменты 2-го порядка. Здесь надо решить обратную задачу: по моментам найти параметры фигур.

[Andr]

Для таких фигур, как эллипс и прямоугольник существуют формулы, как вычислить по ним моменты 2-го порядка.

Если можно, дайте ссылку, где можно посмотреть эти формулы.

[prografix]

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

[Andr]

Например, здесь. Есть и другие статьи ( ищите по запросу "моменты инерции" ).

Спасибо за ссылку. Пойду разбираться.

Что касается исходной задачи, то её можно решать по-другому - искать минимальную фигуру содержащую данные точки. Тогда и треугольник найдётся.

Здесь не все так просто.
Во-первых, "минимальная ограничивающая фигура" != "аппроксимирующая фигура" (ограничивающая фигура почти всегда больше аппроксимирующей).
Во-вторых, алгоритмы, которые мне встречались, чаще всего предполагают, что ориентация ограничивающей фигуры известна (например, ее оси параллельны осям координат). В моем же случае это совсем не так. Т.е. на изображении может быть правильный квадрат, повернутый на 45 градусов, или правильный треугольник.

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

[prografix]

По поводу треугольника можно сделать так: 1) по точкам построить выпуклый многоугольник 2) найти минимальный охватывающий треугольник ( есть такой алгоритм и статья на английском ) 3) найти максимальный вписанный треугольник ( перебором вершин ) 4) взять средний из этих двух треугольников.

Во-вторых, алгоритмы, которые мне встречались, чаще всего предполагают, что ориентация ограничивающей фигуры известна (например, ее оси параллельны осям координат).

Мне известны алгоритмы которые строят подобные фигуры для любой ориентации.

[Andr]

Мне известны алгоритмы которые строят подобные фигуры для любой ориентации.

А можно ссылку, где про эти алгоритмы почитать можно.

[mserg]

Насколько я понимаю, прямоугольник и эллипс определяются 5-ю независимыми параметрами, а треугольник – 6-ю.
1. Требование совпадения центра масс изображения и аппроксимирующей фигуры дают 2 уравнения
2. Требование совпадения моментов инерции дает 3 уравнения: припоминается, что существуют такие взаимно перпендикулярные оси, относительно одной из которых момент инерции максимален, а относительно второй минимален. Итого три параметра: угол поворота и два значения моментов. Для прямоугольника и эллипса этого достаточно, т.к. п1 и п2 дают 5 уравнений.
3. Для треугольника остается еще одна степень свободы. Шестое уравнение может быть построено из требования: площадь изображения треугольника и площадь аппроксимирующей фигуры должны быть равны.

Можно предложить и другое понимание аппроксимации.
1. Площади аппроксимирующей фигуры и площади изображения равны.
2. Внутренность аппроксимирующей фигуры должна содержать максимум изображения фигуры.
Математически это задача глобальной оптимизации с одним ограничением и одним критерием – подходит «для чего угодно». Переменные здесь – это параметры, определяющие фигуру на плоскости.

[Andr]

Для эллипса и прямоугольника так и решаю, через моменты инерции (спасибо еще раз prografix, почитал по его ссылкт, посмотрел его код).

А вот для треугольника:
1. Если решать через моменты и площадь, то не так все просто. Для произвольного треугольника и моменты инерции непонятно как вывести, да и если и выведешь, чувствую потом эту систему не так просто будет решить.
2. Если решать через равенство площади и максимум совпадения - идея интересная. Но получается функция для оптимизации с 6 переменными. Аналитическое решение - не представляю как сделать. Перебором всех переменных - слишком трудремкая операция.

[mserg]

Чтобы еще упростить задачу, можно воспользоваться только одним критерием: в охваченной аппроксимирующем треугольнике области, нужно просуммировать точки фигуры минус точки фона. Эту суммо-разность нужно максимизировать. Это можно сделать, например, генетическим алгоритмом – не нужно пытаться решать задачи оптимизации перебором.

Но, скорее всего, в условиях пропущено, что треугольник равнобедренный. Тогда проблем нет – есть прямые формулы расчета, как и для прямоугольника и эллипса.