We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convex Polygon

Number: 469

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of points representing the vertices of a simple polygon (i.e., the polygon does not intersect itself except at adjacent vertices), determine if the polygon is convex. A polygon is convex if every internal angle is less than 180 degrees, meaning that for every set of three consecutive points, the turn is in the same direction (either all clockwise or all counter-clockwise).

Key Insights

  • The polygon is convex if the cross product of every pair of consecutive edges has the same sign.
  • Calculate the cross product for each trio of consecutive points to detect the turn direction.
  • Use modulo arithmetic to manage wrapping from the last vertex to the first.
  • Skip cross products that are zero (collinear points) in the consistency check.

Space and Time Complexity

Time Complexity: O(n), where n is the number of vertices.
Space Complexity: O(1) (constant extra space usage).

Solution

The solution involves iterating through each vertex and computing the cross product of vectors formed by three consecutive vertices. The sign of the cross product indicates a clockwise or counterclockwise turn. Initially, we establish a baseline direction from the first non-zero cross product. As we continue checking, if the sign deviates from the initial sign, the polygon is not convex and we return false. Otherwise, if all valid turns are consistent, the polygon is convex. This approach leverages simple arithmetic operations and a single loop, ensuring the algorithm runs in linear time with constant space.

Code Solutions

def isConvex(points):
    n = len(points)
    prev_cross = 0

    # Process each vertex; wrap-around using modulo
    for i in range(n):
        p1 = points[i]
        p2 = points[(i + 1) % n]
        p3 = points[(i + 2) % n]
        
        # Vectors p1->p2 and p2->p3
        dx1 = p2[0] - p1[0]
        dy1 = p2[1] - p1[1]
        dx2 = p3[0] - p2[0]
        dy2 = p3[1] - p2[1]
        
        # Compute cross product
        cross = dx1 * dy2 - dy1 * dx2
        
        # Establish baseline or check consistency if non-zero
        if cross != 0:
            if prev_cross == 0:
                prev_cross = cross
            elif cross * prev_cross < 0:
                return False
    return True

# Sample Test
print(isConvex([[0,0],[0,5],[5,5],[5,0]]))  # Expected output: True
print(isConvex([[0,0],[0,10],[10,10],[10,0],[5,5]]))  # Expected output: False
← Back to All Questions