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.:
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-pt_a v1y = pt_b-pt_a v2x = pt_c-pt_a v2y = pt_c-pt_a return v1x*v2y - v1y*v2x def isConvex(self, points): """ :type points: List[List[int]] :rtype: bool """ pt_1 = points pt_2 = points 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)
@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.