Here's why the "cross product" works for this (plus Python solution)


  • 0
    M

    I put "cross product" in quotes because, strictly speaking, it's not defined for 2D space. Summarizing what I've learned from the following, et al.:

    http://www.gamedev.net/topic/289972-cross-product-of-2d-vectors/#entry2828289

    http://stackoverflow.com/questions/243945/calculating-a-2d-vectors-cross-product

    When U = (Ux, Uy, 0) and V = (Vx, Vy, 0), what U x V really returns is the magnitude in the z axis. This can be used to tell us which way the two vectors are "winding" (which gives you a sense of whether the angle between the two vectors is greater or less than 180°... or which way two vectors are turning when placed head to tail).

    As long as you do the math consistently this "cross product" should maintain its sign for each triplet of points as you go around the polygon (e.g., define V1 = P1-P0 and V2 = P2 - P0 (V2 = P2-P1 also works, for this particular purpose)). The sign itself isn't important for this particular purpose, just whether it changes.

    My solution (which works though one could optimize with early exits, etc.):

    class Solution(object):
        @classmethod
        def get_prod(self, pt_a, pt_b, pt_c):
            v1x = pt_b[0]-pt_a[0]
            v1y = pt_b[1]-pt_a[1]
            v2x = pt_c[0]-pt_a[0]
            v2y = pt_c[1]-pt_a[1]
            return v1x*v2y - v1y*v2x
    
        def isConvex(self, points):
            """
            :type points: List[List[int]]
            :rtype: bool
            """
            pt_1 = points[0]
            pt_2 = points[1]
            prods = set()
            for pt_3 in points+points[:2]:
                prod = self.get_prod(pt_1, pt_2, pt_3)
                prods.add(prod)
                # print(pt_1, pt_2, pt_3, prod)
                pt_1, pt_2 = pt_2, pt_3
            return not (min(prods) < 0 and max(prods) > 0)
    

  • 0

    @MartyMacGyver Yes, indeed cross product is not defined for 2D space since the product vector must be orthogonal to the plane formed by the two vectors for calculation.

    Another way to "embed" 2D vectors into 3D space is to force z-component as zero, i.e., let "2D" vectors

    • v1 = (x1, y1, 0), v2 = (x2, y2, 0),

    then by the determinant formula of 3D cross product, we have

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

    where e = (ix, iy, iz) is the triplet of 3 axis unit vectors. Only iz-direction has non-zero coefficient which is exactly 2x2 determinant det([[x1, y1], [x2, y2]]), and we only care about its sign for convexity.


Log in to reply
 

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