4

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.

4

2 回答 2

6

你所描述的算法让我担心的是它是“贪婪的”并且可能选择“错误”的轨道段（或者，至少，一个不是最接近点的轨道段）。

是时候将 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 位于以 TP1 为中心的半径 D12 的圆内或以 TP2 为中心的半径 D12 的圆内，那么您将 X 与 S12 相关联。但是，如果我们还考虑 Y 点，我建议您使用的算法也会将其与 S12 相关联。

如果算法被细化为MAX(D1Y, D2Y) < D12，则它不认为 Y 与 S12 相关。然而，X 可能仍被认为与 S12 相关，而不是与 S23 或 S56 有关。

于 2009-08-23T11:35:02.510 回答
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.

于 2009-08-23T10:25:57.283 回答