Я задаю этот вопрос из любопытства, так как моя быстрая и грязная реализация кажется достаточно хорошей.Тем не менее, мне любопытно, что будет лучшей реализацией.
У меня есть график данных реального мира.В графике нет повторяющихся значений X и значений X с постоянной скоростью, но данные Y основаны на реальных результатах.Я хочу найти ближайшую точку на графике из произвольно заданной точки P программно.Я пытаюсь найти эффективный (то есть быстрый) алгоритм для этого.Мне не нужна точная ближайшая точка, я могу согласиться на точку, которая находится «почти» вблизи ближайшей точки.
Очевидное ленивое решение состоит в том, чтобы увеличивать каждую точку на графике, вычислять расстояние, а затем найдите минимум расстояния.Это, однако, теоретически может быть медленным для больших графов;слишком медленный для того, что я хочу.
Поскольку мне нужна только приблизительная ближайшая точка, я представляю, что идеальное наиболее быстрое уравнение будет включать в себя создание линии наилучшего соответствия и использование этой линии для вычисления того, где точка должна находиться в реальном времени;но это звучит как потенциальная математическая головная боль, которую я не собираюсь принимать.
Мое решение - хак, который работает только потому, что я предполагаю, что моя точка P не произвольна, а именно, я предполагаю, что P обычно будетблизко к моей линии графика, и когда это произойдет, я могу вычеркнуть отдаленные значения X из рассмотрения.Я вычисляю, насколько близка точка на линии, которая разделяет координату X с P, и использую расстояние между этой точкой и P, чтобы вычислить наибольшее / наименьшее возможное значение X, которое может быть ближе к точке.
Я могу 'Это не поможет, но я чувствую, что должен быть более быстрый алгоритм, чем мое решение (что полезно только потому, что я предполагаю, что 99% времени моя точка P будет точкой, близкой к прямой).Я попробовал поискать лучшие алгоритмы, но нашел так много алгоритмов, которые не совсем подходили, и было трудно найти то, что я искал, среди всего множества неуместных алгоритмов.Итак, есть ли у кого-нибудь здесь предложенный алгоритм, который был бы более эффективным?Имейте в виду, мне не нужен полный алгоритм, поскольку то, что у меня есть, работает для моих нужд, мне просто любопытно, каким было бы правильное решение.