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

Для 1-нормы это будет минимум суммы расстояний от точки до прямых. В этом случае решением может быть точка, отрезок или многоугольник. В любом случае одна из точек пересечения каких-то прямых будет принадлежать множеству решений. Функция getNearPoint1 находит такую точку в среднем за время O ( n * log n ):

Def<Vector2d> getNearPoint1 ( CArrRef<Line2d> line, nat & ix1, nat & ix2 );
Def<Vector2d> getNearPoint1 ( CArrRef<Line2d> line );

Для 2-нормы это будет минимум суммы квадратов расстояний от точки до прямых, то есть эта задача является задачей наименьших квадратов, и она может быть решена одним из соответствующих методов. В данном случае выбран метод ortholin. Если нужно задать прямым разный вес, то для этого надо умножить компоненты класса Line2d на соответствующий вес или воспользоваться вариантом функции, где вес передаётся в качестве параметра. Для этой нормы решение всегда единственное. Функция getNearPoint2 находит такую точку за время O ( n ):

Def<Vector2d> getNearPoint2 ( CArrRef<Line2d> line );
Def<Vector2d> getNearPoint2 ( CArrRef<Line2d> line, CArrRef<double> mass );

Для бесконечной нормы это будет минимакс расстояний от точки до прямых, и эту задачу можно свести к задаче линейного программирования. Функция getNearPointU находит такую точку. Экспериментально определено, что на случайных прямых этот алгоритм имеет временную сложность O ( n ):

Def<Vector2d> getNearPointU ( CArrRef<Line2d> line );

Следующие функции минимизируют p-норму для значений p = 4/3, 6/5, 8/7, 10/9:

Def<Vector2d> getNearPoint4_3 ( CArrRef<Line2d> line );
Def<Vector2d> getNearPoint6_5 ( CArrRef<Line2d> line );
Def<Vector2d> getNearPoint8_7 ( CArrRef<Line2d> line );
Def<Vector2d> getNearPoint10_9( CArrRef<Line2d> line );

Def<Vector2d> getNearPointR ( CArrRef<Line2d> line, ArrRef<double> mass );

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

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

Исходники находятся в approx2d.cpp