469. Convex Polygon

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

There are at least 3 and at most 10,000 points.

Coordinates are in the range -10,000 to 10,000.

You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise do not intersect each other.

public class Solution {

public boolean isConvex(List<List<Integer>> points) {

// For each set of three adjacent points A, B, C, find the cross product AB · BC. If the sign of

// all the cross products is the same, the angles are all positive or negative (depending on the

// order in which we visit them) so the polygon is convex.

boolean gotNegative = false;

boolean gotPositive = false;

int numPoints = points.size();

int B, C;

for (int A = 0; A < numPoints; A++) {

// Trick to calc the last 3 points: n - 1, 0 and 1.

B = (A + 1) % numPoints;

C = (B + 1) % numPoints;

int crossProduct =

crossProductLength(

points.get(A).get(0), points.get(A).get(1),

points.get(B).get(0), points.get(B).get(1),

points.get(C).get(0), points.get(C).get(1));

if (crossProduct < 0) {

gotNegative = true;

} else if (crossProduct > 0) {

gotPositive = true;

}

if (gotNegative && gotPositive) return false;

}

// If we got this far, the polygon is convex.

return true;

}

// Return the cross product AB x BC.

// The cross product is a vector perpendicular to AB and BC having length |AB| * |BC| * Sin(theta) and

// with direction given by the right-hand rule. For two vectors in the X-Y plane, the result is a

// vector with X and Y components 0 so the Z component gives the vector's length and direction.

private int crossProductLength(int Ax, int Ay, int Bx, int By, int Cx, int Cy) {

// Get the vectors' coordinates.

int ABx = Bx - Ax;

int ABy = By - Ay;

int BCx = Cx - Bx;

int BCy = Cy - By;

// Calculate the Z coordinate of the cross product.

return (ABx * BCy - ABy * BCx);

}

}

////////////////////////////////////////////////////////////////////////////////////

class Solution {

public:

bool isConvex(vector<vector<int>>& points) {

long long n = points.size(), pre = 0, cur = 0;

for (int i = 0; i < n; ++i) {

int dx1 = points[(i + 1) % n][0] - points[i][0];

int dx2 = points[(i + 2) % n][0] - points[i][0];

int dy1 = points[(i + 1) % n][1] - points[i][1];

int dy2 = points[(i + 2) % n][1] - points[i][1];

cur = dx1 * dy2 - dx2 * dy1;

if (cur != 0) {

if (cur * pre < 0) return false;

else pre = cur;

}

}

return true;

}

};