Пусть в пространстве дано множество из n точек pi = ( xi, yi, zi ) и нужно аппроксимировать его сферой. Рассмотрим несколько подходов к решению этой задачи. В первом подходе координаты центра o = ( x, y, z ) и радиус r будем искать, как аргументы при которых функция
принимает минимальное значение. Сведём эту задачу к задаче наименьших квадратов. Для этого продифференцируем (1) по r и приравняем производную нулю. Отсюда получим выражение r 2 через x, y и z:
Подставим это выражение в (1) и приведём подобные члены. Получится задача наименьших квадратов:
где
Следующая программа решает эту задачу: Def<Sphere3d> getSpherePnt22 ( CArrRef<Vector3d> p ); Основное преимущество рассмотренной задачи - это простота решения, но более интересной для практики является минимизация другой функции отклонений:
Отсюда получается следующий итерационный алгоритм: 1) Получаем начальное приближение для o и r при помощи функции getSpherePnt22. 2) Вычисляем значения cxi, cyi и czi. 3) Решая задачу (5) получаем новые значения для o и r. Будем повторять шаги 2 и 3 пока алгоритм не сойдётся. В результате получаем программу: Def<Sphere3d> getSpherePnt2 ( CArrRef<Vector3d> p ); Описание класса Vector3d находится здесь.
Исходники находятся в файле approx3d.cpp Наверх |