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

Question

Мой вопрос может быть немного странным. Я «разработал» алгоритм и не знаю, есть ли подобный алгоритм уже там.

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

• Вычислить расстояние от точки ТР1 (трек 1) в ТР2 - назовем это 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-order. Я использовал эту технику для представления quadtree, структуры данных для кода adaptive mesh refinement, который я когда-то работал, и использовал алгоритм, очень похожий на тот, который вы описываете, чтобы пересечь сетку и определить расстояния между частицами.

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