I believe this time it's far beyond my ability to get a good grade of the contest!


  • 8

    get the cross product of the sequential input edge a, b as tmp, then:

    if tmp == 0, a -> b 180° on the same line;
    elif tmp > 0, a -> b clockwise;
    else tmp < 0, a -> anticlockwise;

    tmp = (p1[0]-p0[0])(p2[1]-p0[1])-(p2[0]-p0[0])(p1[1]-p0[1])

    class Solution(object):
        def isConvex(self, points):
            last = 0
            for i in xrange(2, len(points) + 2):
                p0, p1, p2 = points[(i - 2) % len(points)], points[(i - 1) % len(points)], points[i % len(points)]
                tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1])
                if last * tmp < 0:
                    return False
                last = tmp
            return last * tmp >= 0
    

    Update instead of just maintaining the sequential cross product result, any of the two cross product shouldn't multiplies to minus:

    class Solution(object):
        def isConvex(self, points):
            last, tmp = 0, 0
            for i in xrange(2, len(points) + 3):
                p0, p1, p2 = points[(i - 2) % len(points)], points[(i - 1) % len(points)], points[i % len(points)]
                tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1])
                if tmp:
                    if last * tmp < 0:
                        return False
                    last = tmp
            return True
    

  • 0
    D

    @Ipeq1 Can you please explain this line ?

    tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1])


  • 0

    @deshpana Hi, I've updated the post


  • 6

    @deshpana Line tmp = (p1[0]-p0[0])*(p2[1]-p0[1])-(p2[0]-p0[0])*(p1[1]-p0[1]) is to calculate the determinant of 2x2 matrix det([p1-p0,p2-p0]).

    Note that for any two 2D vectors v1=(x1,y1), v2=(x2,y2), the cross product is calculated by the determinant of 2x2 matrix [v1,v2]:

    • v1 x v2 = det([v1, v2]),

    where the sign represents the positive direction of z-axis determined by right-hand system from v1 to v2. So det([v1, v2]) >= 0 if and only if v1 can be rotated at most 180 degrees counterclockwise to v2.


  • 0
    D

    @zzg_zzm Awesome. Thank you !


  • 4

    Fails for example [[0,0],[0,1],[1,1],[2,1],[2,2],[2,3],[3,3],[3,0]]:

    0_1480887383993_polygon_boomerang.png


  • 0

    @StefanPochmann you are right, thanks for pointing it out and I've updated the code.


  • 1

    @StefanPochmann Thanks, I have just added the test case.


  • -1

    @StefanPochmann Hello, your example here is not a convex polygon, as from Wikipedia( link text ), A convex polygon is a simple polygon (not self-intersecting) in which no line segment between two points on the boundary ever goes outside the polygon. Equivalently, it is a simple polygon whose interior is a convex set. In a convex polygon, all interior angles are less than or equal to 180 degrees, while in a strictly convex polygon all interior angles are strictly less than 180 degrees.

    for the (2,1) in your example, the interior angle is 270 degree instead of 90, which makes your example not a convex polygon.


  • 0

    @xuehaohu Yes, I know. What's your point?


  • 0

    @StefanPochmann NVM. it was my bad! now getting you were saying the code above does not treat ur example as non-convex polygon


  • 0
    J

    Same as my idea, using Cross Product.
    For anyone who doesn't know about that, check CLRS 33.1


  • 0
    L

    @Ipeq1 Thanks for your good solution.
    However, I think there is a confusing part. You consider two consecutive edges of the polygon. p0, p1, and p2 are three consecutive vertices. The vectors for the consecutive two edges should be p1-p0, and p2-p1. Since p2 and p0 are not consecutive points, p2-p0 is not an edge of the polygon if there are more than three vertices in the polygon.


Log in to reply
 

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