Collision detection with concave vertex array (sf::TriangesFan)

[fatnic]

I've created a vision cone using a vertex array and now I'd like to be able to check for collisions with other objects, such as the green box below.



However from what I've read Separating Axis Theorem will not work with concave shapes. Are there any other methods anyone can recommend I check out?

Thanks.

[Nexus]

You could have a look at the Boost.Geometry library. It's very powerful and supports loads of geometric operations -- in your case, you can use use the model::polygon class template to model the cone, and the intersects() algorithm to check whether the object is contained. It's well possible that Boost.Geometry comes in handy in many other places of your application.

In case you already use Thor, it would also be possible to triangulate the concave shape and check if one of the resulting triangles contains the point. Thor is simpler to get into, but more limited regarding geometry operations.

[Satus]

However from what I've read Separating Axis Theorem will not work with concave shapes.

I solved it by simply separating concave into smaller convex shapes.

[fatnic]

I had a look at Boost and it looks great! A bit OTT for what I need though. I have taken the advice of Satus and separated the shape into smaller triangles (simply done as it was already an sf::TrianglesFan) and it works perfectly.

Looping through the triangle segments with the function below can quickly tell if the point is within it.

bool pointInTriangle(Point t1, Point t2, Point t3, Point p)
{
    float d = ((t2.y-t3.y)*(t1.x-t3.x) + (t3.x-t2.x)*(t1.y-t3.y));

    float a = ((t2.y-t3.y)*(p.x-t3.x) + (t3.x-t2.x)*(p.y-t3.y)) / d;
    float b = ((t3.y-t1.y)*(p.x-t3.x) + (t1.x-t3.x)*(p.y-t3.y)) / d;
    float c = 1 - a - b;
       
    return 0 <= a && a <= 1 && 0 <= b && b <= 1 && 0 <= c && c <= 1;
}
 

Thanks for the advice.