Collision detecting custom sketched shape, represented as list of points

Question

I have a set of points, drawn by the user. They will be drawing around some objects.

I need to somehow turn this set of points into a shape, so I can find the area to detect collisions.

An image will clarify:

.

The best idea I have had so far involves iterating over every pixel determining if it is 'inside' or 'outside' the shape, but that would be horribly slow, and I'm not even sure how to do the determining 'inside'/'outside' bit...

Any hints? I am using .NET (C# and XNA) if that helps you help me!

Answer 1

You can think of your shape as an union of several shapes each of which is a simple closed polygon.
the check for every object if it is inside any of the polygons in the following manner:
All dots connected by lines - each line has an equation defining it.
For every object - build an equation for a line passing through this object.
now - for each object equation you need to check how many lines (those between the dots) intersects this object equation - but count only the intersection points that are in the rage between the two dots (and not in the rest of the line outside the two dots) and only the intersection points that are in one side of the object (pick a side - doesn't matter).
If the count is even - the object is outside the shape - otherwise it is inside.

Answer 2

Hey Elwyn,

Just a precursor to anything I will say, I have no experience in this field, this is just how I would go about the problem.

A tactic a lot of games use for this is known as Hit Boxes. It is much easier to detect if a point is inside a square than any other figure. But this doesn't give you an exact collision, it could be right outside your desired object.

I've seen Collision 'Bubbles' used before. Here is a link I found for you. This explains the use of Collision Bubbles in the console game Super Smash Brothers.

Given a point, the distance formula, and a radius, you can easily implement collision bubbles.

To take it even one step forward, I did a little bit of research, I saw a nifty little algorithm (more advanced that the top two suggestions), the "Gilbert-Johnson-Keerthi Collision detection algorithm for convex objects." Here is a link for ya. The implementation provided is written in D. If your working in C# it shouldn't be too hard to translate (I would highly suggest digesting the algorithm too).

Hope this gives you some direction.

Answer 3

Well I got it working thanks to some help on another forum.

I used the GraphicsPath class to do all the hard work for me.

This is what my method ended up looking like:

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);
}

Thanks for your suggestions both of you