CODEWITHSUNDEEP
algorithmmathgeometrycomputational-geometry
Gaius Augustus
Gaius Augustus

Reputation: 1215

How to calculate the Minimum Translation Vector in a given direction?

The Separating Axis Theorem returns a minimum translation vector in an arbitrary direction. A variation of this problem would be to calculate the minimum translation vector in a given direction. I was wondering how to calculate this with polygons and circles but I'm stuck in the circle-circle case. Does anybody have an idea of how to approach this problem?

A signature of this function would be:

Vector minimum_tranlation_vector_between(Circle a, Circle b, Vector axis);

Thanks in advance!

Upvotes: 4

Views: 1457

Answers (2)

samgak
samgak

Reputation: 24417

Suppose that the center co-ordinates and radius of circle a are given by a.x, a.y and a.r.

Also suppose that we have a vector v and we want to push the circles apart by moving the first circle in the direction of v by an amount d. The circles will be touching when:

((a.x + (v.x * d)) - b.x)2 + ((a.y + (v.y * d)) - b.y)2 = (a.r + b.r)2

This equation just calculates the squared distance between the offset circle centers and sets it equal to the square of the sum of the radii.

We can simplify it a bit by moving both circles by subtracting the second one's center point from both so that the second circle is at the origin, which removes it from the equation:

(a.x + (v.x * d))2 + (a.y + (v.y * d))2 = (a.r + b.r)2

Now we just need to solve for d and multiply it by v to get the result (the separation vector). I cheated and used an online solver, there are the 2 solutions (formatted as code because the formatter keeps trying to turn the multiplies into italics):

d = -(sqrt((v.y²+v.x²)*e-a.x²*v.y²+2*a.x*v.x*a.y*v.y-v.x²*a.y²)+a.y*v.y+a.x*v.x)/(v.y²+v.x²)
d = (sqrt((v.y²+v.x²)*e-a.x²*v.y²+2*a.x*v.x*a.y*v.y-v.x²*a.y²)-a.y*v.y-a.x*v.x)/(v.y²+v.x²)

Here's some proof of concept code in Java:

double calculateSeparationDistance(double circle1x, double circle1y, double radius1, double circle2x, double circle2y, double radius2, double vectorx, double vectory)
{
    double a = circle1x-circle2x;
    double b = vectorx;
    double c = circle1y-circle2y;
    double d = vectory;
    double e = (radius1 + radius2) * (radius1 + radius2);

    // 2 possible solutions:
    double distance = -(Math.sqrt(((d*d)+(b*b))*e-(a*a)*(d*d)+2*a*b*c*d-(b*b)*(c*c))+c*d+a*b)/((d*d)+(b*b));
    // double distance = (Math.sqrt(((d*d)+(b*b))*e-(a*a)*(d*d)+2*a*b*c*d-(b*b)*(c*c))-c*d-a*b)/((d*d)+(b*b));

    // add (distance * vectorx, distance * vectory) to first circle, or subtract from second circle to separate them 
    return distance;
}

The two solutions correspond to pushing the first circle out of the second one in either direction. You can chose whichever solution has the smallest absolute value, or choose the one with the positive sign.

Failure case: when the circles are not intersecting and the vector does not put them on a collision course then there are no solutions and the equation gives the square root of a negative value, so either do an intersection test beforehand or check the sign of the value before passing it to sqrt().

Upvotes: 3

Lutz Lehmann
Lutz Lehmann

Reputation: 25992

Copying the naming scheme from samgak, but reducing everything to the standard situation for quadratic equation gives the procedure

double calculateSeparationDistance(double circle1x, double circle1y, double radius1, double circle2x, double circle2y, double radius2, double vectorx, double vectory)
{
    double dx = circle1x-circle2x;
    double vx = vectorx;
    double dy = circle1y-circle2y;
    double vy = vectory;
    double R2 = (radius1 + radius2) * (radius1 + radius2);

    // the equation is 
    // (dx+vx*d)²+(dy+vy*d)² = R2
    // expanding and reordering by degree
    // (vx²+vy²)*d²+2*(vx*dx+vy*dy)*d+(dx²+dy²-R2) = 0

    double a = vx*vx;
    double b = 2*(vx*dx+vy*dy);
    double c = dx*dx+dy*dy-R2

    // Note that we want the smaller (in absolute value) solution, 
    // and that the selection by the solution formula depends on
    // the sign of b. Setting (b,d):=(-b,-d) still results in an
    // equation with a solution.

    double sign = 1;
    if ( b<0 ) { b=-b; sign = -1; } 

    // Real solutions do not exist if the discriminant is negative
    // here that means that abs(dx*vx+dx*vy) is too small, 
    // geometrically that the circles never touch if moving in
    // direction v.

    if( b*b < 4*a*c ) return 0; // or 1e308 or throw exception

    // apply stable standard solution formula for the smaller solution:
    double d = -(2*c)/(b + Math.sqrt(b*b-4*a*c));

    return sign*d;
}

Upvotes: 3

Related Questions