Hey guys, i have a 2D polygon object something along the lines of
typedef struct Poly2D_t {
vector<Touple2D> verts; // vector of x, y pairs
} Poly2D;
I need a function to classify each polygon as convex or concave. Is there an algorithm for this? For some reason i can't seem to find the method to do so on google.
All help is appriciated!
I don't know what the canonical solution would be but the easiest I can think of is by calculating all dot products of the form:
[formula]dot(p_n-p_{n-1}, (p_{n+1}-p_n)^\perp)[/formula].
If they all have the same sign the polygon is convex, otherwise it isn't.
The solution for mathematically proving that a circle is convex is by tracing a point from the edge across to all the other points on the edge looking for intersections of that ray with the arc. Dot product sounds like it'll work too.
I say Code! You say Build! Code! Build! Code! Build! Can I get a woop-woop? Woop! Woop!
Why not look up a convex hull finding algorithm? The Monotone Chain algorithm looks like it could be useful. If it's output matches your polly then it's a convex one.
Thanks for all the replies guys! I should have mentioned this is being used in a tool, so performance is not that big of an issue. I decided to go with japro's solution as it seemed to be the easiest to implement.
Thanks for all the help again!
If anyone is interested, here is my mock code (Tested and working) #include <vector>