移动物理对象以使其穿透的最小尺寸 Vec3 = 0

问：

这是一个例子（见图）：-

• 2 个红色矩形是静态对象（即它不能移动）。
• 蓝色球是动态物体。

到目前为止，我设法获得了所有具有穿透力的信息。让我们将其视为我们的输入：-

• 为了解决和球之间的穿透问题，我可以通过 OR 移动球。AVec3(1,0,0)Vec3(0,2,0)
• 为了解决和球之间的穿透问题，我可以通过 移动球。BVec3(0,1,0)

^ 我将其存储为 2D Vec3 数组问题 = {{Vec3{1,0,0}，Vec3{0,2,0}}，{Vec3{0,1,0}}}。

如何找到物理对象（例如示例中的球）的最佳运动（最小尺寸）以尽可能减少穿透力？

此示例中的最佳解决方案是“移动球：size=1.414”。Vec3(1,1,0)

在实际情况下，情况可能更加复杂和丑陋，
例如，A&B（和其他物理对象）都可能试图将球推向几乎相反的方向。（下图）

^ 在某些场景中，2D 阵列问题可能缺少一些细节，但为了简单起见，让我们假设它准确地解释了所有信息。

C++ 代码

这是我的MCVE（coliru）：-

#include<iostream>
#include <utility>
#include <vector>
#include <array>
#include <math.h>

using Vec3=std::array<float, 3>;
float dotProduct(Vec3 vec1,Vec3 vec2){
    return vec1[0]*vec2[0]+vec1[1]*vec2[1]+vec1[2]*vec2[2];
}
float size2(Vec3 vec1){
    return vec1[0]*vec1[0]+vec1[1]*vec1[1]+vec1[2]*vec1[2];
}
Vec3 mulFloat(Vec3 vec1,float m){
    return Vec3{vec1[0]*m,vec1[1]*m,vec1[2]*m};
}
Vec3 normalize(Vec3 vec1){
    return mulFloat(vec1,1/sqrt(size2(vec1)));
}

这是：-main()

int main() {
    std::vector<std::vector<Vec3>> problem;
    std::vector<Vec3> location1;
    location1.push_back(Vec3{0,2,0});
    location1.push_back(Vec3{1,0,0});
    problem.push_back(location1);
    std::vector<Vec3> location2;
    location2.push_back(Vec3{0,1,0});
    problem.push_back(location2);
    //^ INPUT
    //----- insert YOUR ALGORITHM here  ------
    Vec3 solution=Vec3{0,2,0};

    float totalResidual=0;
    for(auto& location : problem){
        float residualRemainMin=1000000;//numerical limit
        for(auto& orgResidual : location){
            Vec3 orgResidualNormalize=normalize(orgResidual);
            float orgResidualSize=sqrt(size2(orgResidual));
            float residualModifyBy=-dotProduct(orgResidualNormalize,solution);//#1
            //"residualModifyBy" is usually negative
            float remainResidual=std::max(0.0f,orgResidualSize+residualModifyBy);
            //^ "max" because it has no advantage to reduce residual to < 0
            residualRemainMin=std::min(residualRemainMin,remainResidual);
            //^ "min" because the "OR" word
        }
        totalResidual+=residualRemainMin;
    }
    std::cout<<"totalResidual="<<totalResidual;
    return 0;
}

代码中注意：残差减少 。
我对这个公式的推导来自这张图片：-(#1)dotProduct(solution,normalize(orgResidual) )

旁注

我觉得对每个组合进行置换太慢了（我不确定如何进行）。
我还认为，一般的迭代方法太慢了，无法收敛。

我只是想要一些指导方针;我不介意只有描述而没有代码的答案。

编辑 （2019年6月29日）

更多测试用例：-

{{(0,3,0)},{(2,2,0)}}            ===> (1,3,0)       
{{(0,1,1),(10,0,0)},{(0,2,3)}}   ===> (0,2,3)  
{{(99,1,0),(99,-1,0),(100,0,0)}} ===> (99,1,0) OR (99,-1,0)    (equally good)