Back to General and Gameplay Programming

Classifying a 2D polygon as convex or concave

General and Gameplay Programming Programming

Started by gabrielauditore December 24, 2011 02:08 AM

5 comments, last by fastcall22 12 years, 3 months ago

gabrielauditore

100

Author

December 24, 2011 02:08 AM

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!

japro

887

December 24, 2011 02:23 AM

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.

Tweet tweet!
My videos on YouTube
OpenGL Example Collection

Kyall

287

December 24, 2011 06:52 AM

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!

AngrySCV

102

December 24, 2011 05:43 PM

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.

gabrielauditore

100

Author

December 24, 2011 08:52 PM

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>



typedef struct Touple2D_t {

	float x, y;



	Touple2D_t() : x(0.0f), y(0.0f) { }

	Touple2D_t(float _x, float _y) : x(_x), y(_y) { }



	Touple2D_t operator-(const Touple2D_t& t) {

		return Touple2D_t(x - t.x, y - t.y);

	}

} Touple2D;



typedef struct Poly2D_t {

	std::vector<Touple2D> verts;

} Poly2D;



float dot(Touple2D& l, Touple2D& r) {

	return (l.x * r.x + l.y * r.y);

}



Touple2D perp(Touple2D& t) {

	return Touple2D(-1.0f * t.y, t.x);

}



bool isConvex(Poly2D& p) {

	unsigned int size = p.verts.size();

	if (size <= 2) return true;

	int sign = 0;



	for (unsigned int i = 1; i < size - 1; ++i) {

		float result = dot(p.verts - p.verts[i-1], perp(p.verts[i + 1] - p.verts));



		if (sign == 0)

			sign = ((result < 0)? -1 : 1);

		else if (sign != ((result < 0)? -1 : 1))

			return false;

	}



	return true;

}