Присвоение имени этому алгоритму:Сравнение и интерполяция точек?

Question

мой вопрос может показаться немного странным.Я "разработал" алгоритм и не знаю, существует ли уже подобный алгоритм.

Ситуация:У меня есть трек, определенный точками трека (2D).Точки трека представляют собой повороты, например.Между точками трека есть только прямые линии.Теперь мне дан набор координат в этом двумерном пространстве.Я вычисляю расстояние от первой точки трека до новых координат и расстояние для интервала для первых двух точек трека.Если расстояние до измеренных координат короче, чем расстояние от первой до второй точки трека, я предполагаю, что эта точка находится между этим интервалом.Затем я выполняю линейную интерполяцию по этому поводу.Если он больше, я проверю со следующим интервалом.

Таким образом, это в основном взятие интервальных расстояний и попытка подогнать их под себя.Я пытаюсь отследить объект, движущийся примерно по этой дорожке.

Кому-нибудь это кажется знакомым?Может ли кто-нибудь предложить аналогичный существующий алгоритм?

Редактировать: Из того, что я изложил до сих пор, я хочу уточнить, что позиция не многократно связана с точками отслеживания.Рассмотрим прекрасный рисунок в формате ASCII, сделанный Джонатаном:

Обнаружено, что положение X находится в пределах сегментов 1 и 2 (S12).Теперь следующая позиция - Y, которую нельзя считать достаточно близкой, чтобы находиться на S12.Я перейду к S23 и проверю, на месте ли он.

Если оно включено, я не буду проверять S12 на наличие какого-либо другого значения, потому что я уже нашел его в следующем сегменте.Алгоритм "не оглядывается назад".

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

Цикл по-прежнему остается проблемой.Предположим, я получаю Y для S23, а затем пропускаю две или три позиции (поскольку они слишком далеки), возможно, я сбиваюсь с пути.Я мог бы определить одну позицию в S34, где она уже была бы в S56.

Может быть, я смогу придумать какую-нибудь среднюю скорость, чтобы vage подсказал, в каком сегменте она должна быть.

Похоже, чем больше сегменты, тем больше шансов принять правильное решение.

Answer 1

Что меня беспокоит в описанном вами алгоритме, так это то, что он "жадный" и может выбрать "неправильный" сегмент трека (или, по крайней мере, сегмент трека, который не является самым близким к точке).

Время довести ASCII-графику до предела.Рассмотрим следующий путь (цифры представляют последовательность в списке точек трека) и координату X (и, позже, Y).

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

Как мы должны интерпретировать ваше описание?

[C] укажите расстояние от первой точки трека до новых координат и расстояние для интервала для первых двух точек трека.Если расстояние до измеренных координат короче расстояния от первой до второй точки трека, [предположим], что эта точка находится между этим интервалом;[...] [i] если он больше, [...] проверьте со следующим интервалом.

Я думаю, что первое предложение означает:

• Вычислите расстояние от TP1 (точки трека 1) до TP2 - назовите его D12.
• Вычислите расстояние от TP1 до X (назовем его D1X) и от TP2 до X (назовем его D2X).

Самая сложная часть - это интерпретация условного предложения.

У меня сложилось впечатление, что если либо D1X, либо D2X меньше, чем D12, то предполагается, что X находится на отрезке трека TP1 -TP2 (назовем его сегментом S12) (или ближе всего к нему).

Глядя на положение X на диаграмме, становится относительно ясно, что и D1X, и D2X меньше, чем D12, поэтому моя интерпретация вашего алгоритма будет интерпретировать X как связанный с S12, однако X явно ближе к S23 или S56, чем к S12 (но они отбрасываются, даже не рассматриваясь).

Я что-то неправильно понял в вашем алгоритме?

Немного подумав об этом:я интерпретировал ваш алгоритм так, что если точка X лежит либо в пределах окружности радиуса D12 с центром в точке TP1, либо в пределах окружности радиуса D12 с центром в точке TP2, то вы связываете X с S12.Однако, если мы также рассмотрим точку Y, алгоритм, который я предлагаю вам использовать, также свяжет ее с S12.

Если алгоритм доработан, чтобы сказать MAX(D1Y, D2Y) < D12, то он не рассматривает Y как относящийся к S12.Однако X, вероятно, все еще считается связанным с S12, а не с S23 или S56.

Answer 2

Первая часть этого алгоритма напоминает мне перемещение по дискретизированному пространству.Примером представления такого пространства является Z-порядок кривая заполнения пространства.Я использовал эту технику, чтобы представить квадродерево, структура данных для адаптивное уточнение сетки код, над которым я когда-то работал, и использовал алгоритм, очень похожий на тот, который вы описываете, для перемещения по сетке и определения расстояний между частицами.

Сходство может быть не сразу очевидным.Поскольку вас интересуют только местоположения интервалов, на этом шаге вы эффективно рассматриваете все точки на интервале как эквивалентные.Это то же самое, что выбрать пространство, в котором есть только дискретизированные точки - вы эффективно "привязываете" свои точки к сетке.