469 Convex Polygon
469. Convex Polygon
难度 : Medium
- The polygon is entirely contained in a closed half-plane defined by each of its edges.
这个算法很有意思也很make sense，叫包礼物。不过也是对付convex hull的，看到有人提这个：
You can make things a lot easier than the Gift-Wrapping Algorithm... that's a good answer when you have a set of points w/o any particular boundary and need to find the convex hull.
A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):
For each consecutive pair of edges of the polygon (each triplet of points), compute the z-component of the cross product of the vectors defined by the edges pointing towards the points in increasing order. Take the cross product of these vectors:
The polygon is convex if the z-components of the cross products are either all positive or all negative. Otherwise the polygon is nonconvex.
given p[k], p[k+1], p[k+2] each with coordinates x, y:
dx1 = x[k+1]-x[k]
dy1 = y[k+1]-y[k]
dx2 = x[k+2]-x[k+1]
dy2 = y[k+2]-y[k+1]
zcrossproduct = dx1 * dy2 - dy1 * dx2
If there are N points, make sure you calculate N cross products, e.g. be sure to use the triplets (p[N-2],p[N-1],p) and (p[N-1],p,p).
class Solution(object): def isConvex(self, points): """ :type points: List[List[int]] :rtype: bool """ n = len(points) zcrossproduct = None for i in range(-2, n-2): x = [ points[i], points[i+1], points[i+2] ] y = [ points[i], points[i+1], points[i+2] ] dx1 = x - x dy1 = y - y dx2 = x - x dy2 = y - y if not zcrossproduct: zcrossproduct = dx1 * dy2 - dy1 * dx2 elif ( dx1 * dy2 - dy1 * dx2 ) * zcrossproduct < 0: return False return True