Naming this algorithm: Comparing and interpolating points?

Question

Hello, my question might be a little strange. I've "developed" an algorithm and don't know if there's a similar algorithm already out there.

The situation: I've got a track defined by track points (2D). The track points represent turns for instance. Between the track points there are only straight lines. Now I'm given a set of coordinates in this 2D space. I calculate the distance from the first track point to the new coordinates and the distance for the interval for the first two track points. If the distance to the measured coordinates is shorter than the distance from the first to the second track point, I'm assuming that this point lies in between this interval. I then do a linear interpolation on that. If it's bigger, I'll check with the next interval.

So it's basically taking interval distances and trying to fit them in there. I'm trying to track an object moving approximately along this track.

Does this sound familiar to somebody? Can somebody come up with a suggestion for a similiar existing algorithm?

EDIT: From what I've stated so far, I want to clarify that a position is not multiply associated to track points. Consider the fine ASCII drawing Jonathan made:

The X position is found to be within Segment 1 and 2 (S12). Now the next position is Y, which is not to be considered close enough to be on S12. I'll move on to S23, and check if it's in.

If it's in, I won't be checking S12 for any other value, because I found one in the next segment already. The algorithm "doesn't look back".

But if it doesn't find the right segment from there on, because it happenend to be to far away from the first segment, but still further away from any other segment anyhow, I will drop the value and the next position will be looked for back in S12, again.

The loop still remains a problem. Consider I get Y for S23 and then skip two or three positions (as they are too far off), I might be losing track. I could determine one position in S34 where it would be already in S56.

Maybe I can come up with some average speed to vage tell in what segment it should be.

It seems the bigger the segments are, the bigger the chance to make a right decision.

Answer 1

The first part of this algorithm reminds me of moving through a discretised space. An example of representing such a space is the Z-order space-filling curve. I've used this technique to represent a quadtree, the data structure for an adaptive mesh refinement code I once worked on, and used an algorithm very like the one you describe to traverse the grid and determine distances between particles.

The similarity may not be immediately obvious. Since you are only concerned about interval locations, you are effectively treating all points on the interval as equivalent in this step. This is the same as choosing a space which only has discretised points - you're effectively 'snapping' your points to a grid.

Answer 2

What concerns me about the algorithm you've described is that it is 'greedy' and could choose the 'wrong' track segment (or, at least, a track segment that is not the closest to the point).

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

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

How are we supposed to interpret your description?

[C]alculate the distance from the first track point to the new coordinates and the distance for the interval for the first two track points. If the distance to the measured coordinates is shorter than the distance from the first to the second track point, [assume] that this point lies in between this interval; [...] [i]f it's bigger, [...] check with the next interval.

I think the first sentence means:

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

The tricky part is the interpretation of the conditional sentence.

My impression is that if either D1X or D2X is less than D12, then X will be assumed to be on (or closest too) the track segment TP1 to TP2 (call it segment S12).

Looking at the position of X in the diagram, it is moderately clear that both D1X and D2X are smaller than D12, so my interpretation of your algorithm would interpret X as being associated with S12, yet X is clearly closer to S23 or S56 than it is to S12 (but those are discarded without even being considered).

Have I misunderstood something about your algorithm?

Thinking about it a bit: what I've interpreted your algorithm to mean is that if the point X lies within either the circle of radius D12 centred at TP1 or the circle of radius D12 centred at TP2, then you associate X with S12. However, if we also consider point Y, the algorithm I suggest you are using would also associate it with S12.

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