Называя этот алгоритм: сравнивая и интерполируя точки?

Question

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

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

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

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

РЕДАКТИРОВАТЬ: Из того, что я уже сказал, я хочу уточнить, что позиция не многократно связана с точками отслеживания. Рассмотрим прекрасный рисунок 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] если оно больше, [...] проверьте следующий интервал.

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

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

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