Аппроксимация контура

← →
Анонимщик © (2004-10-15 17:30) [0]

Мне нужно аппроксимировать набор точек, описывающих замкнутый контур, похожий на эллипс (x^2/a^2 + y^2/b^2=1), эллипсом, и найти соответствующие лучшие в каком-то смысле (метода наименьших квадратов, например) a и b. Собственно алгоритм меня не интересует, есть ли библиотеки, позволяющие такое делать?

← →
begin...end © (2004-10-15 17:47) [1]

Я встречал только про аппроксимацию полиномами. А для эллипса - не знаю, возможно, и есть. Но тут нужно решить два уравнения, это довольно просто.

← →
MBo © (2004-10-15 17:53) [2]

Оси эллипса параллельны осям координат?

← →
MBo © (2004-10-15 18:13) [3]

Если нет, то теоретически, насколько мне кажется, можно посчитать моменты распределения плотности точек первого и второго порядка, что даст "центр" эллипса (2 параметра) и еще три параметра, однозначно характеризующие эллипс (для описания эллипса общего вида необходимо 5 величин)

← →
TUser © (2004-10-15 18:50) [4]

А если да (что следует из формулы) - тогда функция F(a,b), которая дает сумму квадратов отклонений для всех этих точек, имеет единственный минимум, который можно найти оптимизацией. Параметров-то всего два.

← →
Ega23 © (2004-10-15 18:55) [5]

для описания эллипса общего вида необходимо 5 величин)

А разве трёх недостаточно?

← →
Sapersky (2004-10-15 19:17) [6]

можно посчитать моменты распределения плотности точек первого и второго порядка

А можно хотя бы ссылкой намекнуть, как это?

Вообще, если по скорости не критично, то можно делать многомерную оптимизацию (или как она правильно называется), генетическим алгоритмом, например.
Брать 2 точки (фокусы эллипса), считать сумму расстояний от них до каждой точки контура - для эллипса она должна быть равна. Т.е. чем равнее, тем эллипсоиднее :), точнее, зависит от того, какой эллипс нужен - если "наиболее приближённый", то брать среднее от всех расстояний и считать сумму разностей его и всех точек; если вписанный - минимальное расстояние и ещё учитывать площадь.

← →
Ega23 © (2004-10-15 19:21) [7]

Sapersky (15.10.04 19:17) [6]

Ну вот вроде именно так и нужно. По крайней мере, я бы именно так и делал.

← →
Cobalt © (2004-10-15 23:23) [8]

Гы :)
У меня сегодня по Вычислительной Математике проходили тему Интерполяция и аппроксимация ):

>можно посчитать моменты распределения плотности точек первого и второго порядка
>А можно хотя бы ссылкой намекнуть, как это?
Книги по численным методам, в частности, Numerical Recipes (есть в инете).
Насколько я помню, в Math есть процедура расчета нескольких первых моментов (отдельно по координатам X и Y).
Реально ли это поможет в данном случае - не знаю, не пробовал.

>Реально ли это поможет в данном случае
Увы, поможет лишь при равномерном (или по крайней мере) известном распределении точек по углу, длине дуги, или другому параметру.

Я же сказал: библиотека нужна, поскольку у меня не только эллипсы, но и овалы, треугольники и т.п. Еще не знаю, что может понадобиться, а общие подходы мне известны, другое дело, что хорошие алгоритмы стоят большого затраченного времени.

Аппроксимация контура Найти похожие ветки