Python O(n), by checking the directions of every edge, learned from Robert Sedgewick's Algorithm course


  • 3
    X

    The idea is to check whether the edges are always make turns in the same directions (clockwise or counterclockwise)
    The method to check direction is from Robert Sedgewick's Algorithm course.

    0_1481526003952_upload-ab761926-b302-44da-8a64-2f9f7d63bf9f

    class Solution(object):
        def isConvex(self, points):
            """
            :type points: List[List[int]]
            :rtype: bool
            """
            def direction(a,b,c):
                return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
            d = None
            for i in range(1,len(points)):
                a = direction(points[i-2],points[i-1],points[i])
                if a == 0: continue
                if d == None: d = a
                else:
                    if a*d < 0: return False
            if direction(points[-2],points[-1],points[0]) * d < 0:return False
            return True

  • 0
    A

    I improved on your solution by making it more pythonic and wrapping around completely.

    class Solution(object):
        def isConvex(self, points):
            """
            :type points: List[List[int]]
            :rtype: bool
            """
            def direction(a,b,c):
                return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
            
            d = 0
            size = len(points)
            
            for i in range(size):
                print i, (i+1) % size, (i+2) % size, (i+3) % size
                a = direction(points[i],points[(i+1) % size],points[(i+2) % size])
                if a:
                    if not d:
                        d = a
                    elif a*d < 0:
                        return False
                    
            return True
    

    @xuhongnever said in Python O(n), by checking the directions of every edge, learned from Robert Sedgewick's Algorithm course:

    def direction(a,b,c):
    return (b[0]-a[0])(c[1]-a[1]) - (b[1]-a[1])(c[0]-a[0])
    d = None
    for i in range(1,len(points)):
    a = direction(points[i-2],points[i-1],points[i])
    if a == 0: continue
    if d == None: d = a
    else:
    if a*d < 0: return False
    if direction(points[-2],points[-1],points[0]) * d < 0:return False
    return True


Log in to reply
 

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