Convex Polygon

Convex Polygon

What is this problem about?

The Convex Polygon interview question asks you to determine if a given set of points, which form a polygon in order, constitutes a convex polygon. A polygon is convex if all its interior angles are less than 180 degrees. If any interior angle is greater than 180 degrees, the polygon is "concave."

Why is this asked in interviews?

Google asks the Convex Polygon coding problem to evaluate your knowledge of computational geometry. It tests whether you can apply mathematical concepts like the "cross product" to a programming problem. It’s a "Medium" difficulty task that reveals if you can think about 2D space and vector orientation systematically.

Algorithmic pattern used

The primary Geometry interview pattern used here is the Cross Product of vectors.

1. For every three consecutive vertices A, B, and C, calculate the cross product of vectors BA and BC.
2. The sign of the cross product tells you the "direction" of the turn (clockwise or counter-clockwise).
3. In a convex polygon, as you move along the edges, every turn must be in the same direction.
4. If the sign of the cross product changes (from positive to negative or vice versa) at any vertex, the polygon is concave.

Example explanation

Points: (0,0), (2,0), (2,2), (0,2) (A square)

1. Turn at (2,0): Vector (0,0)-(2,0) and (2,2)-(2,0). Cross product is positive.
2. Turn at (2,2): Next vector pair. Cross product is positive.
3. Turn at (0,2): Next vector pair. Cross product is positive.
4. Turn at (0,0): Final vector pair. Cross product is positive. Since all turns are in the same direction, it is a convex polygon.

Common mistakes candidates make

• Collinear Points: Not handling the case where the cross product is 0 (three points in a straight line), which doesn't necessarily make the polygon concave.
• Winding Order: Assuming the points are always provided in a specific (e.g., clockwise) order.
• Edge Cases: Not checking the "wrap-around" turns that connect the last points back to the first points.

Interview preparation tip

Brush up on the formula for the 2D cross product: (x2-x1)(y3-y2) - (y2-y1)(x3-x2). This is the most efficient way to check the "handedness" of a turn without calculating actual angles.