XNA、C# - 检查 Vector2 路径是否与另一个 Vector2 路径交叉

Question

我有一个 XNA 问题要问那些在这些问题上比我更有经验的人（数学）。

背景：我有一个实现边界类的游戏，它只托管 2 个 Vector2 对象，一个起点和一个终点。当前的实现通过假设边界始终是垂直或水平来粗略地处理碰撞检测，即如果 start.x 和 end.x 是相同的检查，我不会尝试通过 x 等。

理想情况下，我想要实现的是一种接受的方法两个 Vector2 参数。第一个是当前位置，第二个是请求的位置（假设没有异议，我想将其移动到该位置）。该方法还接受一个边界对象。然后该方法应该做的是告诉我在这一步中我是否要跨越边界。这可能是一个布尔值，或者理想情况下代表我实际可以移动多远的东西。

这种空洞的方法可能比我用语言更好地解释。

        /// <summary>
    /// Checks the move.
    /// </summary>
    /// <param name="current">The current.</param>
    /// <param name="requested">The requested.</param>
    /// <param name="boundry">The boundry.</param>
    /// <returns></returns>
    public bool CheckMove(Vector2 current, Vector2 requested, Boundry boundry)
    { 
        //return a bool that indicated if the suggested move will cross the boundry.
        return true;
    }

Answer 1

经过相当多的研究，最重要的是找到了谷歌的正确术语，我有了一个解决方案，我刚刚将其内置到我的测试台中，并且它运行得很好。

我拿了网上找到的一个例子进行了测试，然后修改了一下，以满足这个问题的需要。应该指出的是，自测试以来我已经进行了更改，因为我在这台笔记本电脑上只有一个虚拟机，无法运行 XNA 应用程序，因此虽然我确信它应该可以工作，但可能会出现错误。

我们需要做的就是传入一个表示我们所在位置的向量、一个表示我们想要的位置的向量以及边界（实际上是由起始向量和结束向量组成的线）。该方法将告诉我们两条线（一条是当前位置和请求位置之间的路径，另一条是边界）是否交叉。作为一个额外的好处，如果他们进行交叉和输出参数会告诉我们在哪里。

这是一个非常有用的系统，用于创建强大的碰撞检测。

        /// <summary>
    /// Based on the 2d line intersection method from "comp.graphics.algorithms Frequently Asked Questions"
    /// </summary>
    /// <param name="currentLocation">The current location.</param>
    /// <param name="requestedLocation">The requested location.</param>
    /// <param name="boundary">The boundary.</param>
    /// <param name="collisionVector">The collision vector.</param>
    /// <returns></returns>
    public static bool Intersects(Vector2 currentLocation, Vector2 requestedLocation, Boundary boundary, ref Vector2 collisionVector)
    {
        float q = (currentLocation.Y - boundary.Start.Y) * (boundary.End.X - boundary.Start.X) - (currentLocation.X - boundary.Start.X) * (boundary.End.Y - boundary.Start.Y);
        float d = (requestedLocation.X - currentLocation.X) * (boundary.End.Y - boundary.Start.Y) - (requestedLocation.Y - currentLocation.Y) * (boundary.End.X - boundary.Start.X);

        if (d == 0) 
        {
            return false;
        }

        float r = q / d;

        q = (currentLocation.Y - boundary.Start.Y) * (requestedLocation.X - currentLocation.X) - (currentLocation.X - boundary.Start.X) * (requestedLocation.Y - currentLocation.Y);
        float s = q / d;

        if (r < 0 || r > 1 || s < 0 || s > 1)
        {
            return false;
        }

        collisionVector.X = currentLocation.X + (int)(0.5f + r * (requestedLocation.X - currentLocation.X));
        collisionVector.Y = currentLocation.Y + (int)(0.5f + r * (requestedLocation.Y - currentLocation.Y));
        return true;
    }

Answer 2

我已经提出了一个答案，但这里有另一个答案，相似但不同：

我将使用点线距离的变体，再次取自 Wolfram！ http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html

如果采用等式 14，但去掉分子中的绝对值 ( | | )，您将得到一个有符号距离。我从未听说过有符号距离的概念，所以不要指望这个术语是准确的。好的，如果出发地和目的地的符号距离不同，则意味着出发地和目的地位于线路的两侧：

public bool CheckMove(Vector2 current, Vector2 requested, Boundry boundry)
{
    // Assuming you got 2 points in boundry.
    float signedDistanceCurrent = GetSignedDistance(current, boundry.Vector1, boundry.Vector2);
    float signedDistanceRequested = GetSignedDistance(current, boundry.Vector1, boundry.Vector2);

    return signedDistanceRequested * signedDistanceCurrent < 0;
}

public float GetSignedDistance(Vector2 point0, Vector2 point1, Vector2 point2)
{
    // Equation 14 without the |s.
    return ((point2.X-point1.X)*(point1.Y-point0.Y)-(point2.X-point0.X)*(point2.Y-point1.Y))/((point2.X-point1.X)^2+(point2.Y-point1.Y)^2)^(0.5F);
}

顺便说一句，与上一个答案相比，我更喜欢这个答案，但这取决于你。

编辑：顺便说一句，用这种方法，您还可以知道碰撞何时发生：如果您这样做：

float timeFractionToCollision = -signedDistanceCurrent / (signedDistanceRequested - signedDistanceCurrent);

您将获得碰撞发生的时间段的周期分数。

Answer 3

我想你想要的是找到它们的角度，所以只需做 X/Y 并比较，如果角度相同，它们是平行的..

像这样：

float radians = (float)Math.Atan2(vector.X, vector.Y);

Answer 4

我认为你想要做的是 2D 射线盒相交（与轴对齐的盒）。您可以找到许多在线算法，包括这个：http:// www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm

Answer 5

对于您所有的数学需求，我建议您首先尝试 MathWorld.Wolfram.Com。这是一篇关于线与线相交的文章： http://mathworld.wolfram.com/Line-LineIntersection .html

您感兴趣的部分是上面的部分，包括第四个方程。

使用它，您可以获得交叉点坐标。然后您可以检查在该运动过程中是否会穿过该坐标。对于此检查，您可以执行以下操作：

public bool CheckMove(Vector2 current, Vector2 requested, Boundry boundry)
{
    // If your object doesn't move, it can't hit anything!
    if (current.X == requested.X && current.Y == requested.Y) { return false; }

    Vector2 impactPoint = /* Your code to get the impact
                            point from the link above */;

    Vector2 movement = requested - current;
    float timeToImpact = 0;
    // We checked for object movement already, so it's either moving in X, Y or both.
    // I choose to check for X first, but you could check for Y.
    if (movement.X != 0)
    {
        timeToImpact = (impactPoint.X - current.X) / movement.X;
    }
    else
    {
        timeToImpact = (impactPoint.Y - current.Y) / movement.Y;
    }

    // I don't consider a collision at 0 to be a collision since I think
    // it had to be resolved the period before.
    return timeToImpact <= 1 && timeToImpact > 0;
}