Нахождение ближайших координат XY - PullRequest
0 голосов
/ 22 марта 2011

У меня есть точка на 2d изображении, например красная точка на данном рисунке и набор из n точек синяя точка (x1, y1) ... (xn, yn), и я хочу найти ближайшую точку к(x0, y0) лучше, чем пробовать все точки.Хотелось бы иметь лучшее из возможных решений.Буду признателен, если вы разделяете какой-либо подобный класс, если у вас есть.

enter image description here

Ответы [ 2 ]

1 голос
/ 22 марта 2011

Есть много подходов к этому, наиболее распространенным, вероятно, является использование какой-либо формы разделения пространства для ускорения поиска, так что это не O (n). Подробнее см. Поиск ближайшего соседа в Википедии.

0 голосов
/ 22 марта 2011

Большинство решений, которые мы могли бы предложить, зависели бы от немного большего знания, я собираюсь выйти из себя и сказать, что, если вы уже не знаете, что у вас мало времени. То есть Есть десятки тысяч синих точек, или вы должны выполнить тысячи таких расчетов за короткое время. « Линейный поиск » послужит вам достаточно хорошо.

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

Большинство других методов используют более сложные структуры данных для сортировки точек по их геометрическому расположению. Но это намного сложнее реализовать.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...