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

Question

我有一组由用户绘制的点，它们将围绕某些对象进行绘制。

我需要以某种方式将这组点转换为形状，以便我可以找到区域以检测碰撞。

图像将澄清： 将点集表示为形状http://www.imagechicken.com/uploads/1277188630025178800.jpg。

我迄今为止最好的想法是迭代每个像素，确定它是否在形状“内部”或“外部”，但那将非常缓慢，而且我甚至不确定如何确定“内部”/“外部”的位...

任何提示？如果有帮助，我正在使用.NET（C#和XNA）。

- elwyn

Answer 1

感谢另一个论坛上的帮助，我终于搞定了。

我使用了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);
}

谢谢你们两个的建议

- elwyn

Answer 2

您可以将形状看作是由几个简单封闭多边形组成的联合体。
以下是每个对象是否在任何多边形内的检查方式：
所有点都连接在一起，每条线都有一个定义它的方程式。
对于每个对象，建立通过该对象的线的方程式。
现在，对于每个对象方程式，您需要检查有多少条线（那些在点之间）与该对象方程式相交 - 但仅计算两个点之间范围内的交点（而不是在两个点之外的其余部分的线上），并且仅计算对象一侧的交点（选择一侧-无所谓）。
如果计数为偶数，则对象在形状外部 - 否则在内部。

- Itay Karo

Answer 3

在我说任何事情之前，我要声明一下，我在这个领域没有经验，以下是我解决问题的方式。

很多游戏使用的一种策略是命中框。检测一个点是否在一个正方形内比其他图形要容易得多。但这并不能给你一个精确的碰撞，它可能就在你想要的对象外面。

我以前见过使用碰撞“气泡”的方法。这里是我为你找到的链接。它解释了在掌机游戏《超级大乱斗》中使用碰撞气泡的方法。

给定一个点、距离公式和半径，你可以很容易地实现碰撞气泡。

更进一步，我做了一些研究，发现了一个非常棒的算法（比前两个建议更高级），叫做“Gilbert-Johnson-Keerthi凸物体碰撞检测算法”。这里是一个链接。提供的实现是用D语言编写的。如果你在使用C#，那么将其转换应该不会太难（我强烈建议你消化一下这个算法）。

希望这能给你一些方向。

- Meiscooldude