Быстрый алгоритм нахождения х ближайших точек к заданной точке на плоскости

Question

Я хотел бы найти быстрый алгоритм, чтобы найти x ближайших точек к данной точке на плоскости.

На самом деле мы имеем дело с не слишком многими точками (между 1000 и 100 000), но мне нужны x ближайших точек для каждой из этих точек. (где х обычно будет между 5 и 20.)

Мне нужно написать это на C #.

Немного больше контекста о сценарии использования: эти точки являются координатами на карте. (Я знаю, это означает, что мы не совсем говорим о плоскости, но я надеюсь избежать решения проблем проекции.) В конечных точках, которые имеют много других точек, близких к ним, должны отображаться красным цветом, точки, которые не слишком много точки рядом с ними должны отображаться зеленым цветом. Между этими двумя крайностями точки находятся на градиенте цвета.

Answer 1

Вам нужна структура данных, подходящая для организации точек на плоскости.KD-дерево часто используется в таких ситуациях.См. kd tree в Википедии.

Здесь я нашел общее описание Геометрических алгоритмов

---

ОБНОВЛЕНИЕ

Я перенес Java-реализацию KD-дерева на C #.Пожалуйста, смотрите Пользователь: Ojd / KD-Tree в RoboWiki.Вы можете загрузить код там или загрузить CySoft.Collections.zip прямо с моей домашней страницы (только загрузка, без документов).

Answer 2

Для данной точки (не для всех) и поскольку количество точек не является экстремальным, вы можете рассчитать расстояние от каждой точки:

var points = new List<Point>();
Point source = ...
....
var closestPoints = points.Where(point => point != source).
                           OrderBy(point => NotReallyDistanceButShouldDo(source, point)).
                           Take(20);

private double NotReallyDistanceButShouldDo(Point source, Point target)
{
   return Math.Pow(target.X - source.X, 2) + Math.Pow(target.Y - source.Y, 2);
}

(я использовал х = 20)

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

Answer 3

Чтобы сделать это более эффективным.скажем, расстояние к.Возьмите все точки с координатами x между xk и x + k.аналогично возьмите, yk и y + k.Итак, вы удалили все лишние координаты.Теперь сделайте расстояние на (x-x1) ^ 2 + (y-y1) ^ 2.Создайте минимальную кучу из k элементов и добавьте их в кучу, если новая точка

Answer 4

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

Если результаты должны быть точными на 100%, вы можете использовать стандартную функцию расстояния:

d = SQRT ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)