# Python: Detailed & easy to understand solution

• 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

Useful references

Code

``````class Solution(object):
def get_direction(self, p0, p1, p2):
x0, x1, x2 = p0[0], p1[0], p2[0]
y0, y1, y2 = p0[1], p1[1], p2[1]
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
``````

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