# Beyond my knowledge... Java solution with in-line explanation

• Well, I have to say that this problem is beyond my knowledge. @Ipeq1 and @zzg_zzm have explained how to solve this problem in their posts
The algorithm itself is not hard but I have no idea there exists such a way to determine if a polygon is convex or not. Laugh at me for my ignorance... I believe 90% of programmers can solve this problem if they were given the formula.
Anyway, following is the Java solution with in-line explanation. Accepted, 32ms. Reference: http://csharphelper.com/blog/2014/07/determine-whether-a-polygon-is-convex-in-c/

``````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 BAx = Ax - Bx;
int BAy = Ay - By;
int BCx = Cx - Bx;
int BCy = Cy - By;

// Calculate the Z coordinate of the cross product.
return (BAx * BCy - BAy * BCx);
}
}
``````

• If you want to know more of the theory, please refer to CLRS 3rd Edition Chapter 33, 33.1-5 page 1020

• @shawngao Nice solution!

Rewrote using the geeks for geeks method of determining the orientation of three points:
http://www.geeksforgeeks.org/orientation-3-ordered-points/

``````public boolean isConvex(List<List<Integer>> points) {
List<Integer> back1 = points.get(points.size() - 1);
List<Integer> back2 = points.get(points.size() - 2);
boolean seenPositive = false, seenNegative = false;

for (List<Integer> curr : points) {
int orientation = orientation(back2, back1, curr);

if (orientation < 0)
seenNegative = true;
else if (orientation > 0)
seenPositive = true;

if (seenPositive && seenNegative) return false;

back2 = back1; back1 = curr;
}

return true;
}

private int orientation(List<Integer> point1, List<Integer> point2, List<Integer> point3) {
int orientation = (point2.get(1) - point1.get(1)) * (point3.get(0) - point2.get(0)) -
(point2.get(0) - point1.get(0)) * (point3.get(1) - point2.get(1));
return orientation == 0 ? 0 : orientation / Math.abs(orientation); // 0, 1 or -1
}
``````

• Maybe Google just want the top 10% mathematicians, but not programmers. heheda

• Thanks @shawngao . Here is the python2 version:

``````class Solution(object):
def isConvex(self, points):
neg, pos = False,False
N = len(points)
def cross_product(a,b,c):
x_ab,y_ab = a[0]-b[0],a[1]-b[1]
x_bc,y_bc = b[0]-c[0],b[1]-c[1]
return (x_ab * y_bc - y_ab * x_bc)
points +=points[0:2]
for i in xrange(N):
if cross_product(points[i],points[i+1],points[i+2]) >0: neg=True
if cross_product(points[i],points[i+1],points[i+2]) <0: pos=True
return False if neg and pos else True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.