checking if a polygon is convex

[dcradu]

I have to do a Polygon class that has a function which verifies if the polygon is convex .
the class looks like this. the number of points that make the polygon is variable and i store them in a vector. Point is a class which I made earlier and has 2 variables: x and y and some functions like distance, modifiers etc.

class Polygon
{
public:
vector<Point> X;

Polygon();

void getPolygon(int n);
bool isConvex(Polygon&);
double area(Polygon&);
};

I don't have any ideas about how to check the convexity so if you have one please tell me. I found something called the "gift wrapping algorith" but I don't quite understand what it does.

[Disch]

The easiest way I know of to verify if a polygon is convex is to iterate over all points and verify that their orientation moves either clockwise or counter-clockwise.

IE, given 3 consecutive points on a polygon, A, B, and C

If the angle of orientation of AB is greater than the angle of BC, then angle ABC is bending clockwise. If less... then the angle is counter-clockwise.

If all angles are either CW or CCW, the polygon is convex. However if some angles are CW and others are CCW, then polygon is not convex.


The easiest way to implement finding out whether or not an angle is CW or CCW is to use the perpendicular dot product:

double perpDot( Vector A, Vector B )
{
    return (A.x * B.y) - (A.y * B.x);
}

if this is > 0 then vector A is oriented CW of vector B. If < 0, A is CCW of B. (I might have that backwards... it's hard to keep straight)

Either way.. this can be leveraged to check all angles in the polygon.

Pseudo-code

bool convex = true;

A, B, C = anyThreeConsecutivePointsInPolygon();

bool negative = (perpDot( B-A, C-B ) < 0);

for( ... each angle in the polygon ... )
{
    A, B, C = thePointsOfThisAngle();
    if( (perpDot( B-A, C-B ) < 0) != negative )
    {
        convex = false;
        break;
    }
}

// here, 'convex' is true if the polygon is convex.  'false' otherwise. 

[dcradu]

thanks very much