# Working out the next point on a curved path/line given previous positions

## Recommended Posts

Hi Everyone, My maths are really failing me and im stuck on this one, im tracking a point and i want to estimate the next position of that point. Currently i store 10 previous postions, and from at least the last 2 and current position i want to work out the velocity of the point so that i can work out the next postion. Currently im simply going:
Vector2D diff = CurrentUpdatePoint->CurrentPos() - CurrentUpdatePoint->LastPos();
float mag = diff.length();
diff.normalise();
CurrentUpdatePoint->Velocity() = (diff*mag)/timePassed;


and this gives a linear result but its not accurate enough and i reckon i need to work out the curved path the point is going on and work out the next position. But my maths isnt up to scratch on this problem..please help! ive made a small diagram to illustrate the problem: I assume i need to do something where i work out the changing angle in directions and then apply this, but again im not really sure how to go about this! -Thanks for any help, Chris

##### Share on other sites
GregMichael    135
Google "catmull rom spline" that might help...or not..it will at least give you a spline path that will pass through all of the control points which seems to be what you're after.

##### Share on other sites
Sorry perhaps i was misinterpretated but after googling camull rom spline it seems:

"To calculate a point on the curve, two points on either side of the desired point are required"

It seems it would be good for interpolating between two known points but im trying to estimate the next point.

Although looking at that equation makes me wonder if what im asking is really posible?

currently im trying a solution where i work out the directions of the previous points, work out the angle between them, then add this to the direction that ive worked out for the next point and this seems to look like its getting somewere, even though its curving in the oposite direction =P

Thanks for the equation though i think i will find it usefull for fixing another problem =]

##### Share on other sites
GregMichael    135
What I was getting at is if you know at least 4 points (and you say you are storing the last 10 points)...then using a catmull rom spline will let you calculate the position of point 5.

So if you know points, 1, 2, 3 and 4...then you can calculate point 5

Then you know points 2, 3, 4 and 5 so can calculate point 6 etc.

##### Share on other sites
Ok, is this possible by putting in a future time? so whereas interpolation would be 0-1, by putting say 2 it would estimate the next position?

on this site it shows this method:

Output_point = P0 * (-0,5*t*t*t + t*t - 0,5*t) +P1 * (1,5*t*t*t + 2,5*t*t + 1,0) +P2 * (-1,5*t*t*t + 2,0*t*t + 0,5*t) +P3 * (0,5*t*t*t - 0,5*t*t);

and im now asuming that a value of t = 2 would give me an estimated value of the next point?

Sorry my applied maths skills is very bad so this stuff goes right over my head and i tend to not see past its currently applied use. Thanks for you help! Chris

##### Share on other sites
This is my progress so far using the Catmull-Rom splines formula, so far its really not working =[!

My implementation of working out the point on the spline based on Java implementation
        Vector2D TrackingPoint2D::WorkOutPointOnSpline(float time, Vector2D Pos1,Vector2D Pos2, Vector2D Pos3,Vector2D Pos4)	{				float time3 = time * time * time;		float time2 = time * time;		//f..variables		float f1 = -0.5 * time3 + time2 - 0.5 * time;		float f2 = 1.5 * time3 - 2.5 * time2 + 1.0;		float f3 = -1.5 * time3 + 2.0 * time2 + 0.5 * time;		float f4 = 0.5 * time3 - 0.5 * time2;		//x & y		float x = Pos1.x * f1 + Pos2.x * f2 + Pos3.x * f3 + Pos4.x * f4;		float y = Pos1.y * f1 + Pos2.y * f2 + Pos3.y * f3 + Pos4.y * f4;		return Vector2D(x,y);	}

How Im applying it:
	void TrackingPoint2D::WorkOutNextPointC(float dt)	{				if(mLastposistions.size() < MAX_POSITION_STORAGE)return;			Vector2D Pos[4];			Pos[0] = mLastposistions[2]; 			Pos[1] = mLastposistions[1];			Pos[2] = mLastposistions[0];			Pos[3] = mNextPos;			//time variables						for(int i = 0; i < mEstimatedNextPos.size(); ++i)			{				float time = 2.0 + (i*0.1f);				mEstimatedNextPos[i] = WorkOutPointOnSpline(time, Pos[0],Pos[1],Pos[2],Pos[3]);			}			mCurrentposistion = WorkOutPointOnSpline(LerpProgress(),Pos[1],Pos[2],Pos[3],mEstimatedNextPos[0]);						}

What im actually doing to get my data
void Tracker2D::UpdateData( float dt, RMWiimote* mote )	{					//way a		for(int i = 0; i < MAX_IR_POINTS; ++i)				{									TrackingPoint2D* CurrentUpdatePoint = FindMostSimilarPointA(Vector2D(mote->IR.Dot[i].X,mote->IR.Dot[i].Y));//this cycles through all my tracking points and finds which point is closest (will be replaced with closest to estimated pos when ready) to the wii point												if(CurrentUpdatePoint)						{							CurrentUpdatePoint->NextPos() = Vector2D(mote->IR.Dot[i].X,mote->IR.Dot[i].Y); 							CurrentUpdatePoint->Visible() = mote->IR.Dot[i].bVisible;										}						}				for(int i = 0; i <  mTrackingPoints.size(); ++i)		{			TrackingPoint2D* CurrentUpdatePoint = GetPoint(i);			CurrentUpdatePoint->LerpProgress()+=mLerpSpeed;                        //now trying cubic spline for this instead			//CurrentUpdatePoint->CurrentPos().x = XF::MathHelper::Lerp(CurrentUpdatePoint->LastPos().x,CurrentUpdatePoint->NextPos().x ,CurrentUpdatePoint->LerpProgress());			//CurrentUpdatePoint->CurrentPos().y = XF::MathHelper::Lerp(CurrentUpdatePoint->LastPos().y, CurrentUpdatePoint->NextPos().y,CurrentUpdatePoint->LerpProgress());			CurrentUpdatePoint->CurrentPos() = CurrentUpdatePoint->NextPos();			if(CurrentUpdatePoint->LerpProgress() = 1.0f)			{				CurrentUpdatePoint->LerpProgress() = 0.0f;				CurrentUpdatePoint->AddPreviousPos(CurrentUpdatePoint->CurrentPos());							CurrentUpdatePoint->AlreadyFollowing() = false;							}			CurrentUpdatePoint->WorkOutNextPointC(dt);		}	}//----------Add Previous Point------void TrackingPoint2D::AddPreviousPos( Vector2D pos )	{		this->mLastposistions.push_front(pos);		if(mLastposistions.size() > MAX_POSITION_STORAGE)		{			this->mLastposistions.pop_back();		}			}

And this is the result it currently gives me:

##### Share on other sites
alvaro    21246
Extrapolating is always tricky, but I would think using cubic splines should give you better results than what you are seeing, so I am sure there is some problem in the implementation. In order to debug your spline implementation, try plotting interpolated values first. Those should look really good if you did the Math right.