碰撞检测自定义草图形状，表示为点列表

Question

我有一组由用户绘制的点。他们将围绕一些物体进行绘画。

我需要以某种方式将这组点变成一个形状，这样我就可以找到检测碰撞的区域。

图像将澄清：

以形状表示的点集 http://www.imagechicken.com/uploads /1277188630025178800.jpg 。

到目前为止，我最好的想法是迭代每个像素，确定它是在形状的“内部”还是“外部”，但这会非常慢，而且我什至不知道如何确定“内部”/ “外面”位...

有什么提示吗？我正在使用 .NET（C# 和 XNA），如果这对你有帮助的话，请帮助我！

Answer 1

您可以将您的形状视为多个形状的联合，每个形状都是一个简单的闭合多边形。
按以下方式检查每个对象是否位于任何多边形内：
所有点均由线连接 - 每条线都有一个定义它的方程。
对于每个对象 - 为穿过该对象的直线建立一个方程。
现在 - 对于每个对象方程，您需要检查有多少条线（点之间的线）与该对象方程相交 - 但仅计算两个点之间的交点（而不是在线之外的其余部分）两个点）并且仅位于对象一侧的交点（选择一侧 - 无关紧要）。
如果计数为偶数，则物体位于形状外部，否则位于形状内部。

Answer 2

只是我要说的任何事情的先兆，我在这个领域没有经验，这就是我解决问题的方式。

许多游戏为此使用的一种策略称为“Hit Boxes”。检测一个点是否在正方形内比检测任何其他图形要容易得多。但这并不能给你一个精确的碰撞，它可能就在你想要的物体之外。

我以前见过使用碰撞“气泡”。 这里是我为您找到的链接。这解释了主机游戏《任天堂明星大乱斗》中碰撞气泡的使用。

给定一个点、距离公式和半径，您可以轻松实现碰撞气泡。

为了向前迈出一步，我做了一点研究，我看到了一个漂亮的小算法（比前两个建议更先进），“凸物体的吉尔伯特-约翰逊-科尔蒂碰撞检测算法”。 这里是给您的链接。提供的实现是用 D 编写的。如果您使用 C# 工作，翻译起来应该不会太难（我强烈建议也消化该算法）。

希望这能给您一些指导。

Answer 3

好吧，多亏了另一个论坛上的一些帮助，我才成功。

我使用 GraphicsPath 类来完成所有艰苦的工作。

这就是我的方法最终的样子：

public bool IsColliding(Vector2 point)
{
    GraphicsPath gp = new GraphicsPath();

    Vector2 prevPoint = points[0];
    for (int i = 1; i < points.Count; i++)
    {
        Vector2 currentPoint = points[i];

        gp.AddLine(prevPoint.X, prevPoint.Y, currentPoint.X, currentPoint.Y);

        prevPoint = currentPoint;
    }
    gp.CloseFigure();   //closing line segment

    return gp.IsVisible(point.X, point.Y);
}

感谢你们俩的建议