Started by Aug 30 2006 01:30 PM

,
9 replies to this topic

Posted 30 August 2006 - 01:30 PM

Suppose I have a path that is simply made up of a series of points. I don't have a strong math background, but I would like to calculate the radius of curvature of each vertex of the path. Anyone have an idea on how I can do this?
Thanks.

Posted 30 August 2006 - 02:12 PM

The first thing to do is decide what kind of curve you want to fit through the points. That's a whole separate topic. But, a very quick, and very approximate way to compute some radii of curvature is to assume that at each vertex the curve approaches being a circle that happens to pass through the adjacent points. So, then the problem becomes a matter of computing the radius of a circle that passes through the point of interest and the adjacent point on either side. Its a pretty big assumption---highly unlikely---that the curve you are really interested in does behave in this manner (e.g., it is unlikely that the center-of-curvature actually happens to correspond to a circle that passes through both the point-of-interest and also the two adjacent points), but that is an easy way to get started with something.

The next possibility, is to actually use proper formulas to compute the radius of curvature. The following page shows the formulas, for the problem in 2D:

Radius of Curvature

If you have a spline or curve that has an analytic formulation, then you can possibly compute those derivatives analytically. Or, you can do it numerically. There is the issue of finding an appropriate projection plane, if you have a 3D curve...since the curvature then would be a function of some projection.

The next possibility, is to actually use proper formulas to compute the radius of curvature. The following page shows the formulas, for the problem in 2D:

Radius of Curvature

If you have a spline or curve that has an analytic formulation, then you can possibly compute those derivatives analytically. Or, you can do it numerically. There is the issue of finding an appropriate projection plane, if you have a 3D curve...since the curvature then would be a function of some projection.

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 30 August 2006 - 02:52 PM

To provide a bit more information, I'm experimenting with vehicles driving, and am looking for a way to estimate a speed that a vehicle can go around a corner without losing control. The information that I've seen related to this are based around a radius of curvature. If I have the friction coefficient of the vehicle I can get the lateral force that would push it into a slide. I'm not sure how to put that information to use in adjusting the vehicle speed so that it takes turns safely. My googling turned up some stuff that uses the radius of curvature so that's what I'm looking into now. I figured I could adjust the speed based on this radius. Is there a way to calculate this radius at a corner if I have 2 vectors that meet, sort of an L shape, essentially each vector is a tangent of the circle. Any other ideas are welcome as well.

Posted 31 August 2006 - 02:35 AM

Well, to find the radius of curvature, you probably need to know width of the road (i.e. area where said car is allowed to drive, which is part of entire road).

There's simple illustration

If radius of such circle is what you need, i can derive the formula. It's quite simple, circle is tangent to outside of road and pass through the inner point.

If road is curved and car is supposed to stay on same line, then you can get radius of curvature from shape of that line. If line is polygonal somewhere, you can do it as grhodes suggested, or you can find curvature of your spline analytically.

There's simple illustration

If radius of such circle is what you need, i can derive the formula. It's quite simple, circle is tangent to outside of road and pass through the inner point.

If road is curved and car is supposed to stay on same line, then you can get radius of curvature from shape of that line. If line is polygonal somewhere, you can do it as grhodes suggested, or you can find curvature of your spline analytically.

Posted 31 August 2006 - 04:03 AM

The illustration looks about what I need. I have the path width defined as well. Once I get the radius I will need to work backwords with the centrifugal force equation to solve for the speed the object can go through the turn, since I should know the force that the vehicle loses it. I think it will give me a decent enough value that the vehicle should slow down to. Just not sure how to get this radius. Appreciate the help.

Posted 31 August 2006 - 04:16 AM

As a sidenote, remember that most roads are inclined to counteract the centripetal forces acting on the vehicle. This effectively reduces the "curvature" of the road.

Posted 31 August 2006 - 04:25 AM

Yea, this is for a game where that probably won't be the case, and I just need it as a good estimate of speed for the turns. Consider this more a case of offroad driving than street driving. And even streets are only inclined to reduce force at some expected speed. Pretend there are no speed limits, and the car wants to drive a course as fast as possible.

Posted 31 August 2006 - 07:48 AM

Let v1 is direction vector before turn, v2 is direction vector after turn (both normalized 2D vectors) , w is track width (note: it's assumed that track is like in my drawing(note that it may be incorrect if there's several such turns close to eachother), road sides is straight lines that just break), r is circle radius for largest turn that fits on road.

The formula is simply

r = w/(1-0.5*Length(v1 + v2))

[beware of infinite radius at zero angle]

That was not so simple to derive tho... Derivations:

let perp(a) = [a_{y}, -a_{x}] (perpendicular aka orthogonal line). For coordinates, let outer corner of that turn be origin.

n is normalized angular bisector direction:

n = (perp(v1) + perp(v2)) / |perp(v1) + perp(v2)|

The inner corner c must be at the bisector line, i.e.

c = d*n

and be on the distance w from side of the road

c . perp(v1) = w ; same for v2

d*n . perp(v1) = w

d = w / (n . perp(v1))

symmetry: the circle center o must be at bisector line; circle must intersect bisector in c , thus

o = n*(d + r)

the circle center must also be at distance r from either line

o . perp(v1) = r ; same for v2

(d + r) * n . perp(v1) = r

d * n . perp(v1) + r * n . perp(v1) = r

d * n . perp(v1) = r * (1 - n.perp(v1))

r = (d * n . perp(v1) ) / (1 - n . perp(v1))

replacing d by it's formula, simplifying:

r = w/(1-DotProd(n,perp(v1)))

note that dotproduct is cosine of half angle, simplifying even more:

r = w/(1-0.5*|v1+v2|)

little test app:

The formula is simply

r = w/(1-0.5*Length(v1 + v2))

[beware of infinite radius at zero angle]

That was not so simple to derive tho... Derivations:

let perp(a) = [a

n is normalized angular bisector direction:

n = (perp(v1) + perp(v2)) / |perp(v1) + perp(v2)|

The inner corner c must be at the bisector line, i.e.

c = d*n

and be on the distance w from side of the road

c . perp(v1) = w ; same for v2

d*n . perp(v1) = w

d = w / (n . perp(v1))

symmetry: the circle center o must be at bisector line; circle must intersect bisector in c , thus

o = n*(d + r)

the circle center must also be at distance r from either line

o . perp(v1) = r ; same for v2

(d + r) * n . perp(v1) = r

d * n . perp(v1) + r * n . perp(v1) = r

d * n . perp(v1) = r * (1 - n.perp(v1))

r = (d * n . perp(v1) ) / (1 - n . perp(v1))

replacing d by it's formula, simplifying:

r = w/(1-DotProd(n,perp(v1)))

note that dotproduct is cosine of half angle, simplifying even more:

r = w/(1-0.5*|v1+v2|)

little test app:

int main()

{

Vec2d v1(1.2,0.2);

Vec2d v2(0.75,1);

Normalize(v1);

Normalize(v2);

double w(2.3456789);

double r = w/(1-0.5*Length(v1+v2));// radius of largest turn circle

cout<<"r="<<r<<endl;

// test: find circle center , find it's distance to outer side of road and to c. Must be equal to r

Vec2d n=Normalized(perp(v1)+perp(v2));

double d=w/DotProd(n , perp(v1));

Vec2d c=d*n;

cout<<DotProd(c,perp(v1))-w<<endl;// must be very small

cout<<DotProd(c,perp(v2))-w<<endl;// must be very small

Vec2d o = n * (d + r);

cout<<"r (distance to v1 line) ="<<DotProd(o,perp(v1))<<endl;

cout<<"r (distance to v2 line) ="<<DotProd(o,perp(v2))<<endl;

cout<<"r (distance to c) ="<<Length(o-c)<<endl;

return 0;

}

Posted 31 August 2006 - 01:03 PM

I have been working on a small tool to try to fit a path to a racetrack.

I found an article about it, that included some bits about radius of curvature

http://www.gamedev.net/community/forums/topic.asp?topic_id=391612

^ You may be able to use that formula to help you in some way.

Unfortunately I still havnt gotten my particular contraption to converge on a solution. Hope you have better luck.

I found an article about it, that included some bits about radius of curvature

http://www.gamedev.net/community/forums/topic.asp?topic_id=391612

^ You may be able to use that formula to help you in some way.

Unfortunately I still havnt gotten my particular contraption to converge on a solution. Hope you have better luck.