Naming this algorithm: comparing and interpolating points?

Question

my question may be a little strange. I “developed” the algorithm and I don’t know if there is already a similar algorithm there.

Situation: I have a track defined by trace points (2D). For example, track points represent turns. Between the points of the trace there are only straight lines. Now I am given a set of coordinates in this two-dimensional space. I calculate the distance from the first point of the track to the new coordinates and the distance for the interval for the first two points of the track. If the distance to the measured coordinates is less than the distance from the first to the second point of the track, I assume that this point is between this interval. Then I do linear interpolation. If it is larger, I will check at the next interval.

Thus, he basically takes the intervals between distances and tries to fine-tune them. I am trying to track an object moving roughly along this track.

Does this sound familiar to someone? Can someone come up with a suggestion for a similar existing algorithm?

EDIT: From what I have said so far, I want to clarify that the position is not multiplied by tracking points. Consider the subtle ASCII drawing that Jonathan made:

It is believed that position X is in segments 1 and 2 (S12). Now the next position is Y, which should not be considered close enough to be on S12. I will go to S23 and check if you enter.

If it is turned on, I will not check S12 for any other value, because I found it in the next segment. The algorithm does not look back.

But if he does not find the correct segment from there, because he will be far from the first segment, but still move away from any other segment, I will omit the value and the next position will be searched again on S12.

The loop is still a problem. Think that I get Y for S23 and then miss two or three positions (since they are too far), I might lose track. I could define one position on S34, where it would already be on S56.

Maybe I can come up with some average speed to show in which segment it should be.

It seems that the more segments, the more likely to make the right decision.

Answer 1

As for me in relation to the algorithm you described, it is that it is “greedy” and can select the “wrong” segment of the track (or at least the segment of the track that is not the closest to the point).

Time to push ASCII art to limitations. Consider the following path (numbers represent the sequence in the list of track points) and the X coordinate (and, later, Y).

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

How should we interpret your description?

[C] display the distance from the first point of the track to the new coordinates and the distance for the interval for the first two reference points. If the distance to the measured coordinates is less than the distance from the first to the second point of the track, [assume] that this point is between this interval; [...] [i] f more, [...] check with the following interval.

I think the first sentence means:

• Calculate the distance from TP1 (point of track 1) to TP2 - call it D12.
• Calculate the distance from TP1 to X (name it D1X) and from TP2 to X (name it D2X).

The hard part is the interpretation of a conditional sentence.

My impression is that if D1X or D2X is smaller than D12, then it is assumed that X will include (or closest) the segment of track TP1 to TP2 (let's call it segment S12).

Looking at the position of X in the diagram, it will be clear enough that both D1X and D2X are smaller than D12, so my interpretation of your algorithm will interpret X as related to S12, but X is clearly closer to S23 or S56 than S12 (but they are discarded, without even reckoning).

Am I misunderstood something about your algorithm?

Thinking about it a bit: I realized that your algorithm means that if the point X lies either in a circle of radius D12 centered on TP1 or in a circle of radius D12 centered on TP2, then you associate X with S12. However, if we also look at point Y, the algorithm that I suggest you use will also associate it with S12.

If the algorithm is refined to say MAX(D1Y, D2Y) < D12 , then it does not consider Y related to S12. However, X is probably still considered to be associated with S12, and not with S23 or S56.

Answer 2

The first part of this algorithm reminds me of moving through a discretized space. An example of representing such a space is the Z-order pad space. I used this technique to represent quadtree , a data structure for the adaptive grid definition that I once worked on, and used a very similar algorithm to the one you describe to traverse the grid and determine the distance between particles.

The similarity may not be immediately obvious. Since you are only concerned with intervals, you effectively treat all points in the interval as equivalent at this point. This is the same as choosing a space that has only discrete points — you effectively snap your points to the grid.