Collision between mouse and convex shape

[mentor]

I'd like to detect collision between mouse and convex shape, but I have no idea how can I do that. I need a pixel-perfect collision, so getGlobalBounds() method won't do here. I need to know if the mouse is inside my convex shape or not. What's the best way to achieve that?

[kitteh-warrior]

If you need pixel-perfect collisions, I recommend using an array of bits to be used as a collision mask. If the cursor appears within the getGlobalBounds(), do further checking (because looping through them every check would be a waste of processing).

Another possible solution, which is not "pixel-perfect", but can be rather accurate is Separating Axis Theorem.

[eXpl0it3r]

Collision detection is a big topic and not SFML specific, as such there are tons and tons and tons of article about it.

Also don't forget that collision detection is just one part of a collision system. The often more complex part is actually the collision responds.

[mentor]

Thanks for your answers. Yes, I know that collision detection is a really big topic, but I thought you might get me into solution that would be best suitable for convex shape. I'll read about SAT and try to do something with this array of bits and collision mask.

The thing is I need to check collision between mouse and a convex shape. I don't need to check collision between sprites or two shapes, I have a one point and I need to check if it's within a certain shape, so at least it's that easier.

[Jesper Juhl]

One way to do that is to "draw" a line between the mouse point and another point that is certainly outside the shape. Then check if this line intersects any edges of the (convex) polygon. If it does then the mouse point is within the polygon, if not, it is outside.

Edit: no, that's not right. If it intersects one edge it is inside.
See also: http://www.mathopenref.com/coordintersection.html

[mentor]

It sounds like a simple and fast solution, perhaps it might be the one I'm looking for since I'm detecting collision between mouse and shape only. Thanks.

[shadowmouse]

Actually, that's not technically correct either for a convex shape. If you have an E shape with the mouse in the bottom leg of the E, and the point that is definitely outside of the E above the top leg, then the line could cross 5 edges. Would it not be more accurate to say if it intersects and odd number of edges?

[Jesper Juhl]

An E shape is a concave shape.
But anyway, I admit my geometry is a little rusty, so I may well be wrong.

[shadowmouse]

Damn, I'm really not on form at the moment. It seemed convex because it has sticky-outy-bits (even I in my current stupid form know that isn't the technical term).

[mentor]

I'm pretty sure I wouldn't have such E-shape shapes in my project. But I thought about this problem shadowmouse mentioned. I might have a line crossing two edges of a shape, but the mouse could still be outside the shape. So I should keep a track of number of edges the line intersects and if this number is greater than 0 and is odd then mouse should be inside shape. If this number is even, I can assume the mouse is outside.

[Jesper Juhl]

I'm pretty sure that what I said above "if it crosses exactly one edge it is inside" is correct (for a convex shape). But go look it up, like here: http://erich.realtimerendering.com/ptinpoly/

[Hapax]

For any polygon, it would be crosses odd number of edges means inside, crosses even number of edges means outside, so for a convex shape, it can only cross zero, one, or two edges and only crossing one (the odd value) edge means it's inside. Zero or two are both outside.
Just to confirm what Jesper and Shadowmouse were saying 

p.s. I implemented it (for convex and concave polygons) like this.