эффективный алгоритм нахождения ближайшей точки в графе, не имеющем известного уравнения
Я задаю эти вопросы из любопытства, так как моя быстрая и грязная реализация, кажется, достаточно хороша. Однако мне любопытно, какой была бы лучшая реализация.
У меня есть график реальных данных. На графике нет повторяющихся значений X, и значение X увеличивается с постоянной скоростью, но данные Y основаны на реальных выходных данных. Я хочу найти ближайшую точку на графике из произвольной заданной точки P программно. Я пытаюсь найти ... эффективный (то есть быстрый) алгоритм для этого. Мне не нужна точная ближайшая точка, я могу довольствоваться точкой, которая является "почти" ближайшей точкой.
Очевидное ленивое решение состоит в том, чтобы увеличить каждую отдельную точку на графике, вычислить расстояние, а затем найти минимум расстояния. Однако теоретически это может быть медленно для больших графиков; слишком медленно для того, что я хочу.Поскольку мне нужна только приближенная ближайшая точка, я предполагаю, что идеальное быстрое уравнение будет необходимо создать линию наилучшего соответствия и использовать ее для вычисления того, где должна быть точка в реальном времени; но это звучит как потенциальная математическая головная боль, которую я не собираюсь брать на себя.
Мое решение-это хак, который работает только потому, что я предполагаю, что моя точка P не произвольна, а именно я предполагаю, что P обычно будет близко к моей линии графика, и когда это произойдет, я могу вычеркнуть удаленные значения X из рассмотрения. Я вычисляю, насколько близко точка на линии, которая разделяет X координата с P is и используйте расстояние между этой точкой и P для вычисления наибольшего / наименьшего значения X, которое может быть ближе точек.
Я не могу не чувствовать, что должен быть более быстрый алгоритм, чем мое решение (что полезно только потому, что я предполагаю, что в 99% случаев моя точка P уже будет точкой, близкой к линии). Я попытался поискать в гугле лучшие алгоритмы, но нашел так много алгоритмов, которые не совсем подходили, что было трудно найти то, что я искал среди всех нагромождение неподходящих алгоритмов. Итак, есть ли у кого-нибудь здесь предложенный алгоритм, который был бы более эффективным? Имейте в виду, что мне не нужен полный алгоритм, поскольку то, что у меня есть, работает для моих нужд, мне просто интересно, какое правильное решение было бы.
3 ответа:
Если вы можете использовать структуру данных, некоторые общие структуры данных для пространственного поиска (включая ближайший сосед) являются...
- quad-tree (и octree etc).
- kd-дерево
- БСП дерево (только для статического набора очков).
- r-дерево
R-дерево поставляется в нескольких вариантах. Он очень тесно связан с деревом B+, но с (в зависимости от варианта) различными порядками элементов (точек) в листовых узлах.
Дерево Гильберта R использует строгий порядок точек, основанный на кривой Гильберта. Кривая Гильберта (или, скорее, ее обобщение) очень хорошо упорядочивает многомерные данные так, что соседние точки в пространстве обычно находятся рядом в линейном порядке.
В принципе, порядок Гильберта может быть применен путем сортировки простого массива точек. Естественная кластеризация в этом случае означала бы, что поиск обычно должен был бы искать только несколько довольно коротких промежутков в массиве - с усложнением, заключающимся в том, что вам нужно выяснить, какие это пролеты.
Раньше у меня была ссылка на хорошую работу по вычислению порядка кривой Гильберта, но я ее потерял. Упорядочение, основанное на серых кодах, было бы проще, но не столь эффективно при кластеризации. На самом деле, существует глубокая связь между серыми кодами и кривыми Гильберта - та бумага, которую я потерял, довольно часто использует функции, связанные с серым кодом.
EDIT - я нашел эту ссылку - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490
Если вы храните точки [x,y] в квадрицепсе , Вы сможете быстро найти ближайший (что-то вроде O(log n)). Я думаю, что это лучшее, что вы можете сделать, не делая предположений о том, где будет точка. Вместо того, чтобы повторять алгоритм здесь, взгляните на эту ссылку .
Ваше решение довольно хорошо, исследуя, как точки меняются в y не могли бы вы вычислить границу для количества точек вдоль оси x, которые вам нужно исследовать вместо использования произвольное решение.