Solution: Convex Polygon

Statement

You are given an array of points on the XY plane, where each point is represented as points[i] = $[x_i, \space y_i]$. These points, when connected sequentially, form a polygonA polygon is a two-dimensional (2D) geometric figure with straight lines connected to form a closed shape. Each line segment in the polygon is called an edge, and the points where two edges meet are called vertices..

Your task is to return TRUE if the polygon is convexA convex polygon is one with all interior angles of less than 180 degrees. Additionally, for any line drawn through the polygon, the line will intersect the polygon at most two points. and FALSE otherwise.

Note: It is guaranteed that the polygon formed by the given points is simple, meaning exactly two edges intersect at each vertex, and the edges do not intersect with each other elsewhere.

Constraints:

• $3 \leq$ points.length $\leq 10^3$

• points[i].length == 2

• $-10^4 \leq$ $x_i$, $y_i$ $\leq 10^4$

• All the given points are unique.

Solution

To determine whether a polygon is convex, the key idea is to analyze the cross product of vectors formed by three consecutive points. These cross products reveal the direction of turns between the points—consistently clockwise or counterclockwise. If the direction of all turns remains uniform throughout the polygon, it confirms that the polygon is convex.

The cross product of vectors formed by three points $P_1(x_1, \space y_1)$, $P_2(x_2, \space y_2)$, and $P_3(x_3, \space y_3)$ is computed using the formula $cp=(x_2​−x_1​) \times (y_3​−y_2​) − (x_3​−x_2​) \times (y_2​−y_1​)$, which helps to determine the direction of the turn:

• If the cross product is positive, the turn is counterclockwise.

• If the cross product is negative, the turn is clockwise.

• If the cross product is zero, the points are collinearCollinear points lie on the same straight line..

The algorithm steps are as follows:

1. Initialize a variable prev_cp to $0$. This variable will track the previous cross product.

2. Iterate through the polygon points. For each point points[i], calculate the cross product cp with its previous and next points.

   1. If cp is $0$, the points are collinear. In this case, skip them and proceed, as these three points do not define a direction.

   2. If cp is not $0$:

      1. Check if prev_cp and cp represent the same direction by multiplying them. If both are positive or both are negative, the product is positive. If one is positive and the other is negative, the product is negative, and we return FALSE.

      2. Otherwise, update prev_cp to cp.

3. If all points have been processed without returning FALSE, return TRUE, indicating that the given points form a convex polygon.

Let’s look at the following illustration to get a better understanding of the solution: