Дана строка и дается множество точек. Я должен найти точку на линии, для которой сумма расстояний от заданных точек минимальна. Я не мог найти алгоритм для реализации в c. Пожалуйста, помогите, спасибо заранее.Как найти оптимальную точку местоположения на линии?
Без ограничения общности линия является осью X (иначе вращайте всю геометрию). Затем вы хотите, чтобы свести к минимуму
Sum √[(X - Xk)² + Yk²]
, которые вы можете сделать, отменив первой производной
Sum (X - Xk)/√[(X - Xk)² + Yk²] = 0
К сожалению, это нелинейное уравнение, которое требует численных методов.
В качестве исходного приближения можно использовать минимизант суммы квадратов расстояний,
Sum [(X - Xk)² + Yk²]
пути решения
Sum (X - Xk) = 0
, который просто дает точку (X*, 0) где является средними по оси абсцисс ,
Пока ни одна из заданных точек не находится на линии, использование Newton-Raphson на этом, похоже, хорошо работает. Однако, если некоторые точки находятся на линии, то цель не дифференцируема (в этих точках), и все не так приятно. – dmuir
Это классическая проблема минимизации *. Вы должны узнать об этом. –
Начните с поиска прямоугольника, который охватывает все точки. Это дает приблизительный диапазон поиска для X и Y. – user3386109
@ user3386109 Этот прямоугольник не обязательно будет содержать какую-либо часть строки. –