roboforum.ru

Технический форум по робототехнике.

Подскажите алгоритм аппроксимации окружностью (или сферой)..

Автомат, адаптивный автомат ... разум

Подскажите алгоритм аппроксимации окружностью (или сферой)..

Сообщение Michael_K » 19 дек 2010, 14:31

...для калибровки компаса.
Хочется сделать процедуру "калибровки в поле".
для начала - найти центр окружности (сферы), вокруг которого ложатся точки.
Разброс сравнительно большой.

Что-то не гуглится алгоритм прямого вычисления...
(приближение численными методами не предлагать :))

С эллипсами решил не заморачиваться - думаю, что в пределах разброса отличаться от окружности не будет (картинки в теме про компасы показывал).
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение =DeaD= » 19 дек 2010, 14:38

Точки по окружности равномерно раскиданы?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение Michael_K » 19 дек 2010, 16:02

нет...
было б равномерно, не спрашивал бы - усреднил бы и все :)

Добавлено спустя 3 минуты 52 секунды:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..
Задумка _приблизительно_ такая - датчик физически представляет из себя цилиндр.
Чел кладет его на плоский стол и катает... (ну и возможно потом поворачивает на столе на 90 градусов и еще катает - чтобы типа сферу получить).
Стол не обязательно строго горизонтальный, углы чел не обязан строго соблюдать и т.п.

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

Добавлено спустя 15 минут 33 секунды:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..


Ну вот, например, такие данные:
Изображение

Добавлено спустя 4 минуты 45 секунд:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..
млин, только сейчас доперло, что окружности мало - сфера нужна.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение =DeaD= » 19 дек 2010, 20:36

Это минимум суммы по i от (sqrt((x0-xi)^2+(y0-yi)^2+(z0-zi)^2)-r0)^2

Не очень похоже, что оно аналитически решается.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение Michael_K » 19 дек 2010, 20:55

Спасибо...
пытался решить на бумажке... запутался :) (ну вот такой я мотематег... :()
нашел тут
http://www.prografix.narod.ru/rus_cirap.html
еще не проверял.

для плоской окружности, правда...

и, похоже, что свернуть в один проход его не удастся :(
то есть все точки нужно сначала в память накопить...
Последний раз редактировалось Michael_K 19 дек 2010, 21:01, всего редактировалось 1 раз.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение =DeaD= » 19 дек 2010, 20:59

Ну там минимизируют не квадрат разности, а квадрат разности квадратов, чтобы от корня уйти :)

Добавлено спустя 1 минуту 6 секунд:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..
Это минимум суммы по i от ((x0-xi)^2+(y0-yi)^2+(z0-zi)^2-r0^2)^2
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Подскажите алгоритм аппроксимации окружностью (или сферо

Сообщение skyfoxss » 28 фев 2011, 20:19

Если выводить лень, есть готовые формулы для МНК оценки окружности. На первой странице этой работы выписаны. Для сферы по аналогии выписываются.

Добавлено спустя 31 минуту 38 секунд:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..
О, для сферы нашел.
N точек xi, yi,zii,
Центр сферы находится как решение системы линейных уравнений:
Sphere.gif


12.gif
12.gif (1.1 КиБ) Просмотров: 5435

Система 3 на 3 решается по правилу Крамера либо если есть готовая библиотека с матрицами - через обратную.
далее радиус сферы:
R.gif
R.gif (2.47 КиБ) Просмотров: 5455


Добавлено спустя 14 минут 52 секунды:
Re: Подскажите алгоритм аппроксимации окружностью (или сферой)..
Да, если в данных могут быть слишком удаленные от аппроксимирующей сферы точки (т.е. шум который не вписывается в модель из за больших разбросов) то нужно применять МНК для случайных выборок - RANSAC алгоритм.
Вложения
Ramanauskas-The Investigation of Eye Tracking Accuracy using Synthetic Images (circle aprox).pdf
(211.94 КиБ) Скачиваний: 0
skyfoxss
 
Сообщения: 12
Зарегистрирован: 12 окт 2010, 13:43
Откуда: Москва, Тольятти


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron