Допустим, у меня есть несколько точек на двумерном холсте. Предположительно, есть способ избежать поиска по всем координатам ближайшего к определенному набору координат (например, щелчок мышью). Здесь?Эффективный способ нахождения ближайшей точки?
Спасибо.
Лучший алгоритм зависит от количества очков, которые вы ожидаете сравнить, как часто эти точки перемещаются и просматриваются, насколько важны скорость повторной индексации и поиска и какой язык вы используете. Как отметил @Sylvanus, могут быть вызовы языка или библиотеки, которые могут помочь. По всей видимости, самый простой способ - quad tree, хотя он будет максимально эффективен. @Shiva Kumar дает отличный полный набор возможностей (хотя есть еще много способов.) Вы должны выполнить поиск в Google, чтобы узнать, как проблема была решена для языка и среды, для которой вы программируете.
Обычно это может быть достигнуто, например, путем индексации точек с помощью B-дерева. Но я не знаю, какие функции, которые использует ваш холст, возможно, он имеет встроенную функцию для чего-то подобного. Это холст HTML5? –
Вы проверили http://stackoverflow.com/questions/1901139/closest-point-to-a-given-point –