How to check if the Polygon is Concave or Convex?using openGL

Question

How to check if the Polygon is concave or convex?using openGL. I take points as input from .txt file and I draw with these points a polygon then here comes the problem .. I need an algorithm to detect the type of the polygon .. concave or convex .

void drawPoints() {
glClear(GL_COLOR_BUFFER_BIT); //Clear display window.
if (points.size()<2) {
   glPointSize(3.0);
   glBegin(GL_POINTS);
}
else {
   glLineWidth(3.0);
   glBegin(GL_LINE_LOOP);
}


   for (int i = 0; i<(int)points.size(); i++) {
   Point& p_i = points[i];
   glVertex2f(p_i.GetX(), p_i.GetY());
}



glEnd();
glFlush(); //Process all OpenGL routines as quickly as possible.

}

score 2 · Accepted Answer · answered Aug 30 '16 at 18:28

2

How to check if the Polygon is concave or convex?

A polygon is defined to be convex if for any line that's being drawn between any two vertices none of the points of the lines comes to happen outside the (filled part) of the polygon. This is a generalization of the definition of convexity of a set.

So how do you test this? The usual approach is determining the convex hull of the polygon (e.g. with the Gift Wrapping algorithm) and then test if all edges of the polygon happen to coincide with its convex hull.

using openGL

Not. OpenGL just draws things. It is not meant for processing geometry (beyond what's required for drawing it).

answered Aug 30 '16 at 18:28

datenwolf

159,371
13
185
298

I would rephrase that last paragraph. OpenGL is absolutely meant for "Processing Geometry"; that's what Shaders are for. In the OP's case, however, determining "is this shape convex or concave" is a poor application of OpenGL, as while a clever use of Shaders could solve this problem, it's quite unobvious what the benefit of doing so is, when one could almost certainly solve it with less time and memory by simply writing an algorithm in c++ (or any other language) to iterate through the vertices of a polygon and check its convex-ness. – Xirema Aug 30 '16 at 21:16
@Xirema: Except for geometry shaders (to some degree) and tesselation shaders (in a very limited scope) OpenGL shaders are focused entirely on singular entities in the form of vertices and primitives, or just bulk, formless data in the case of compute shaders. Except for a few special functions required (clipping and adjacency) a typical OpenGL implementation has *zero* knowledge about geometry. Any "geometry knowledge" in shaders does not come from the OpenGL implementation, but the programmer, writing the shaders. – datenwolf Aug 30 '16 at 22:56
@Xirema: I know that this might seem strange, or highly weird for an API which sole purpose is generating images from geometry. But OpenGL has such a wide target audience, that any attempts of giving it geometrical "knowledge" would only limit, not empower the programmer who wants to use the API. It's intentional that geometric knowledge is to be supplied by the programmer or a 3rd party. – datenwolf Aug 30 '16 at 22:58
Computing convex hull to check convexity (more generally checking is faster than inferring) is an overkill. There are better answers here : http://stackoverflow.com/questions/471962/how-do-determine-if-a-polygon-is-complex-convex-nonconvex – ghilesZ Apr 06 '17 at 14:10

How to check if the Polygon is Concave or Convex?using openGL

1 Answers1