как узнать из двух точек, какая из них ближе всего к набору точек?

Question

как узнать из двух точек, какая из них ближе всего к набору точек?

Предположим, у меня есть две точки (x1, y1) и (x2, y2), я хочу знать, какая из нихближе к набору точек p1, p2, p3, p4.

Есть ли какой-нибудь алгоритм для этого ??

Количество входных точек и количество точек в наборе не фиксированы

У нас может быть n входов и n точек в Set.

Answer 1

Все зависит от того, как вы определяете «ближайший к набору точек».

Одним из супербыстрых критериев может быть «наличие минимальной суммы квадратных расстояний до набора точек» (квадратные расстоянияиспользуется, например, в подгонке кривой, так что ничего странного здесь).

Используя этот критерий, вам просто нужно минимизировать Σᵢ((xᵢ-x)²+(yᵢ-y)²), где i - индекс по набору.

Answer 2

Построить kD-дерево по заданным точкам.Это можно сделать за время Ns Log Ns.

Затем для каждой точки входа найдите ближайшего соседа.Это занимает Ni Log Ns время.И наконец, найдите самое короткое расстояние в сравнениях Ni.

Общее время, (Ns + Ni) Log Ns.Это можно сравнить с грубой силой, принимая Ns.Ni.Для малого Ni предпочтительна грубая сила.