Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

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

Анонимщик (2004-10-18 11:24:00) [1]
Я же сказал: библиотека нужна, поскольку у меня не только эллипсы, но и овалы, треугольники и т.п. Еще не знаю, что может понадобиться, а общие подходы мне известны, другое дело, что хорошие алгоритмы стоят большого затраченного времени.

MBo (2004-10-16 17:39:00) [2]
>Реально ли это поможет в данном случае
Увы, поможет лишь при равномерном (или по крайней мере) известном распределении точек по углу, длине дуги, или другому параметру.

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

Cobalt (2004-10-15 23:23:00) [4]
Гы :)
У меня сегодня по Вычислительной Математике проходили тему Интерполяция и аппроксимация ):

Ega23 (2004-10-15 19:21:00) [5]
Sapersky (15.10.04 19:17) [6]

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

Sapersky (2004-10-15 19:17:00) [6]
можно посчитать моменты распределения плотности точек первого и второго порядка

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

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

Ega23 (2004-10-15 18:55:00) [7]
для описания эллипса общего вида необходимо 5 величин)

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

TUser (2004-10-15 18:50:00) [8]
А если да (что следует из формулы) - тогда функция F(a,b), которая дает сумму квадратов отклонений для всех этих точек, имеет единственный минимум, который можно найти оптимизацией. Параметров-то всего два.

MBo (2004-10-15 18:13:00) [9]
Если нет, то теоретически, насколько мне кажется, можно посчитать моменты распределения плотности точек первого и второго порядка, что даст "центр" эллипса (2 параметра) и еще три параметра, однозначно характеризующие эллипс (для описания эллипса общего вида необходимо 5 величин)

MBo (2004-10-15 17:53:00) [10]
Оси эллипса параллельны осям координат?

begin...end (2004-10-15 17:47:00) [11]
Я встречал только про аппроксимацию полиномами. А для эллипса - не знаю, возможно, и есть. Но тут нужно решить два уравнения, это довольно просто.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »