如何计算给定方向的最小平移向量？

Question

分离轴定理returns任意方向上的最小平移向量。这个问题的一个变体是计算给定方向上的最小平移向量。我想知道如何用多边形和圆来计算这个，但我被困在圆圈的情况下。有人知道如何解决这个问题吗？

此函数的签名为：

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

提前致谢！

Answer 1

假设圆a的圆心坐标和半径由a.x、a.y和a.r给出。

还假设我们有一个矢量 v 并且我们想要通过将第一个圆沿 v 的方向移动 d 量来将圆推开。圆圈将在以下时间接触：

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

这个等式只是计算偏移圆心之间的平方距离，并将其设置为等于半径之和的平方。

我们可以稍微简化一下，通过从两个圆中减去第二个圆的中心点来移动两个圆，使第二个圆位于原点，从而将其从等式中删除：

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

现在我们只需要解出d然后乘以v就可以得到结果（分离向量）。我作弊并使用了 online solver，有 2 个解决方案（格式化为代码，因为格式化程序一直试图将乘法转换为斜体）：

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²)

这是 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;
}

这两个解决方案对应于将第一个圆从任一方向推出第二个圆。您可以选择绝对值最小的解，也可以选择正号的解。

失败案例：当圆不相交并且矢量没有将它们放在碰撞路线上时则没有解并且方程给出负值的平方根，所以要么事先进行相交测试要么在将值传递给 sqrt() 之前检查值的符号。

Answer 2

从 samgak 复制命名方案，但将所有内容简化为二次方程的标准情况给出程序

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;
}

如何计算给定方向的最小平移向量？

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

algorithm

math

geometry

computational-geometry