Пусть задано дискретное множество точек на плоскости и надо найти прямую наиболее близкую к ним. В качестве критерия близости будем рассматривать некоторую норму вектора расстояний от точек до прямой. В этом случае нужно найти прямую, которая минимизирует выбранную норму.

Для 1-нормы это будет минимум суммы расстояний от точек до прямой ( абсолютный момент 1-го порядка ). Следующие функции находят такую прямую ( вторая функция учитывает массу каждой точки ):

Def<Line2d> getLine1 ( CArrRef<Vector2d> point );

Def<Line2d> getLine1 ( CArrRef<Vector2d> point, CArrRef<double> mass );

Def<Line2d> getLine2 ( CArrRef<Vector2d> point );

Def<Line2d> getLine2 ( CArrRef<Vector2d> point, CArrRef<double> mass );

Временная сложность этих функций равна O ( n ).

Для бесконечной нормы это будет минимакс расстояний от точек до прямой:

Def<Line2d> getLineU ( CArrRef<Vector2d> point );

Робастный метод аппроксимации предназначен для данных с выбросами. Этот алгоритм также заполняет массив весов (mass) значениями от 0 до 1.

Def<Line2d> getLineR ( CArrRef<Vector2d> point, ArrRef<double> mass );

Примеры использования этих функций можно посмотреть в приложении DEMO.

Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Описание класса Line2d находится здесь.

Исходники находятся в файле approx2d.cpp