I have a long list of Vector3s, a few hundred of them. They represent the path an object has taken through space, by simply recording its position each frame (it never stops moving, so duplication shouldn’t be an issue)
I want to do some stuff with this list now, but first i’d like to trim it down a bit. Since the points are being recorded so often, you can often just draw a straight line through several of them before any real change in direction occurs, and hence most of the points are completely worthless data
I’d like some advice on how to trim or process this. I’m thinking i could measure the angle of several points, and as long as the total angular change from the first one is below some threshold, i could just discard the intervening ones, until at some point a sharp enough turn is made in the path
I’ve not really fully formed this idea yet, i could do with some input, math help, and code snippets to make the problem more manageable
I would (no maths genius here) do as you say and measure the angle between each point and the next and compare it with a threshold. The only difference is I would consider accumulating the angles and comparing that with the threshold instead, thus any long shallow curves would not be lost.
As I say, I’m not really a maths guy so there’s probably an algorithm already for it
Well, depends. Have you taken into account whether or not you need a known time interval between the points? If so, you’d have to put that data in there if you take out other data.
Simplest ‘compression’ would probably be like this; take the direction between point 0 and 1, and then delete all points following where their direction (1->2, 2->3 etc) is close to the 0->1 direction. And repeat that forever.
I’d do this on the fly, only adding points as we need. Rather than compressing an existing list.
Less memory used up, and no need for compressing all that data all at once.
Something along these lines.
public class PositionTracker : MonoBehaviour
{
public float SignificantChangeInDirectionAngle = 5f; //if the change in direction is more than 5 degrees
private List<Vector3> _nodes = new List<Vector3>();
private Vector3 _totalDelta;
void Start()
{
this.InsertPosition(this.transform.position);
}
void Update()
{
this.InsertPosition(this.transform.position);
}
private void InsertPosition(Vector3 pos)
{
if (_nodes.Count == 0)
{
//first point is special case, just add it
_nodes.Add(pos);
_totalDelta = Vector3.zero;
}
else
{
int i = _nodes.Count - 1;
var prevPos = _nodes[i] + _totalDelta;
var localDelta = pos - prevPos;
_totalDelta += localDelta;
if (Mathf.Abs(localDelta.sqrMagnitude) < 0.0001f)
{
//there's so little change in distance that we barely moved
return;
}
var a = Vector3.Angle(localDelta, _totalDelta);
if (a > this.SignificantChangeInDirectionAngle)
{
//significant change in direction
_nodes.Add(pos);
_totalDelta = Vector3.zero;
}
}
}
}
Basically, every frame we get the total change in position (totalDelta), and the change in position since the previous update (localDelta).
If change since last update is really tiny, it’s as if we stood still, so don’t do anything.
Otherwise, test if the heading of the small change since last update is somewhat in the direction of the general direction we’ve been taking this entire time. If it’s sufficiently different, add a new node.
TotalDelta would be the general direction you’re heading since the last turn.
Take a look at this picture:
So the red dots are the positions each update. They vary a little due to physics, gravity, float error, etc. So they result in a sort of zig zag shape. Keep in mind, these changes are really small, so a point to point change that only pushes down 0.01 units, on a horizontal change that is 0.01 in length, will appear like a 45 degree turn… despite the fact that visually it just looks like you’re standing still.
The purple lines are vectors pointing in the direction from one position to the immediately following position. They vary wildly, with angles between them that are large.
Where as the grey vectors, which is the actual resulting change in position from the last recorded ‘turn point’ (when we set totalDelta to zero), represents more of the general direction of the flow of positions. This vector always points from the last turn position to the current red dot we’re on this frame (this is what the sum of all small changes will result in).
It’s when this “general” direction has a wild change to it that we consider ourselves turning. Otherwise, a point to point change in direction may accidentally result in a wild enough angle that it appears like a turn, when really, it’s not.
