Solution with discussion https://discuss.leetcode.com/topic/72999/python-detailed-easy-to-understand-solution
Convex Polygon https://leetcode.com/problems/convex-polygon/
Linear Scan using orientation concept: O(N)
Determining orientation between three points
- Given three points p0, p1, p2, what can we say about their orientation? Say we have two vectors v1:p0->p1 and v2:p1->p2. The turn from v1 to v2 could be clockwise, anti-clockwise or v1 and v2 could be collinear.
- Now the cross product between v1 and v2 is another vector which is perpendicular to the plane covering v1 and v2. If the turn is ant-clockwise, the cross-product is positive, otherwise it is negative. If the points are collinear, the cross product is zero.
- v1 = (x1-x0)i + (y1-y0)j and v2 = (x2-x1)i + (y2-y1)j. Cross product rules tell us i cross i and j cross j = 0. i cross j = k and j cross i = - i cross j.
- direction = sign(v1 X v2) = sign([(x1-x0) * (y2-y1) - (x2-x1) * (y1-y0)])
Property of a convex polygon
- Convex property tells us that if we take any two points on the polygon and skecth a striaght line between them, the line will lie within the polygon.
- If we order the points of the polygon as p0, p1, p2, p3, p4, ...pn-1, and the turns implied by the vectors implied by each three consecutive points should be in the same direction. This means that [p0, p1, p2] would imply two vectors p0->p1 and p1->p2 and [p1,p2,p3] would imply two vectors p1->p2 and p2->p3. If the turn from p0->p1 to p1->p2 is clockwise, then the turn from p1->p2 to p2->p3 is also clockwise.
- The code must take care of the special condition that three points might be collinear. We save the first non zero direction in a variable called prev_direction. Then any other direction must be same as prev_direction
class Solution(object): def get_direction(self, p0, p1, p2): x0, x1, x2 = p0, p1, p2 y0, y1, y2 = p0, p1, p2 direction = (x1-x0)*(y2-y1) - (x2-x1)*(y1-y0) if direction == 0: return 0 return 1 if (direction > 0) else -1 def isConvex(self, points): """ :type points: List[List[int]] :rtype: bool """ if len(points) < 3: return False prev_direction = 0 for i in range(len(points)): p0, p1, p2 = i%len(points), (i+1)%len(points), (i+2)%len(points) curr_direction = self.get_direction(points[p0], points[p1], points[p2]) if curr_direction: if curr_direction * prev_direction < 0: return False # Save the first non zero direction. All other directions are # should be the same as this direction. if not prev_direction and curr_direction: prev_direction = curr_direction return True