分离轴定理：计算多边形和线段的 MTV

Question

几个月来，我一直在尝试编写一个函数来 return 将线段与相交的多边形分开所需的最小平移。我正在使用分离轴定理，似乎我能够正确计算大小，但是 returned 的方向有时是错误的。然而，当 returned 翻译不正确时，相反的翻译总是正确的。

下图中，黄线是用于计算的，紫线是黄线+平移，红线是黄线减去平移。如您所见，紫色或红色线在不同位置都是正确的，但我不确定在什么条件下 return 哪条线。

所以我的问题是：在什么情况下实际上需要翻转翻译，以便我的函数总是 return 以正确的方向进行翻译？

const Projection Polygon::Project(const Axis &a) const
{
    float min = a.Dot(GetPoint(0));
    float max = min;

    for (unsigned i = 1; i < GetPointCount(); i++)
    {
        float prj = a.Dot(GetPoint(i));

        if (prj < min)
            min = prj;

        else if (prj > max)
            max = prj;
    }

    return Projection(min, max);
}

const Projection Segment::Project(const Axis &a) const
{
    const float dot0 = a.Dot(GetPoint(0));
    const float dot1 = a.Dot(GetPoint(1));

    return Projection(std::min(dot0, dot1), std::max(dot0, dot1));
}

const float Projection::GetOverlap(const Projection &p) const
{
    // x = min & y = max
    return std::min(y - p.x, p.y - x);
}

const Vector2 Segment::GetTranslation(const Polygon &p) const
{
    float Overlap = std::numeric_limits<float>::infinity();
    Axis smallest;
    Vector2 translation;

    AxesVec axes(p.GetAxes());
    axes.push_back(GetAxis());

    for (auto && axis : axes)
    {
        const Projection pA = p.Project(axis);
        const Projection pB = Project(axis);

        if (pA.IsOverlap(pB))
        {
            const float o = pA.GetOverlap(pB);

            if (o < Overlap)
            {
                Overlap = o;
                smallest = axis;
            }
        }
    }

    translation = smallest * (Overlap + 1);

    return translation;
}

Answer 1

麻烦的是你的GetOverlap函数returns magnitude的重叠，而不是sense（左或右）。

您可以将其更改为：

if(y - p.x < p.y - x)
  return y - p.x;
else
  return x - p.y;

然后在 GetTranslation:

const float o = pA.GetOverlap(pB);

if (abs(o) < abs(Overlap))
{
  ...
}

if (Overlap > 0)
  ++Overlap;
else
  --Overlap;

translation = smallest * Overlap;

分离轴定理：计算多边形和线段的 MTV

Separating Axis thereom: Calculating the MTV for Polygon & Line Segment

c++

algorithm

math

computational-geometry