469. Convex Polygon

Problem Description

In this problem, we are given a set of points in the form of a two-dimensional array points, where each element points[i] represents a point in the X-Y plane as [x_i, y_i]. The points are given in an order that represents the vertices of a polygon. We are asked to determine whether the polygon formed by these given points is a convex polygon.

A convex polygon is one in which all interior angles are less than 180 degrees and every line segment between two vertices of the polygon stays inside or on the boundary of the polygon. This means, while traversing the polygon edges in a consistent direction (clockwise or counterclockwise), the direction in which we turn at each vertex to proceed to the next vertex should consistently be either all left (counter-clockwise turn) or all right (clockwise turn) for a convex polygon.

The problem guarantees that the polygon is a simple polygon, meaning that the polygon does not intersect itself and has exactly two edges meeting at each vertex.

Intuition

The intuition behind the solution is to check the sign of the cross product of consecutive edges of the polygon for the entire sequence of points. By doing this, we check the direction of the turn at each vertex. If at all vertices the turns are in the same direction (either all clockwise or all counterclockwise), then we have a convex polygon; otherwise, it is non-convex.

In mathematical terms, the cross product of two vectors can give us a sense of the rotational direction between them: if the cross product is positive, the second vector is rotated counterclockwise with respect to the first, and if negative - clockwise. When the cross product is zero, the vectors are collinear.

To carry out this solution, the procedure is as follows:

1. Iterate through all vertices of the polygon.
2. At each vertex, calculate the vectors (edges) that connect this vertex to the next one (i+1)%n and to the one after (i+2)%n.
3. Compute the cross product of these two vectors.
4. If the cross product's sign changes at any point while we iterate through the vertices, this means that we've detected a change in the rotational direction, indicating that the polygon is not convex.
5. If we complete the iteration without detecting a sign change, the polygon is convex.

Learn more about Math patterns.

Solution Approach

The implementation follows directly from the established intuition. Since we are checking for convexity by looking at the rotational direction at each vertex, we are utilizing a very basic geometric algorithm that involves cross product calculation.

Here is a step-by-step breakdown of the code implementation:

1. Initialize variables pre and cur to 0. These will track the cross product of the current pair of consecutive edges and the previous one, respectively.

2. Loop through each vertex in the polygon using for i in range(n):

   • n is the number of points in the polygon.

3. Inside the loop, calculate two vectors (x1, y1) and (x2, y2):

   • The vector (x1, y1) extends from the current vertex points[i] to the next vertex points[(i + 1) % n].
   • The vector (x2, y2) extends from the current vertex points[i] to the vertex after the next points[(i + 2) % n].

4. Compute the cross product cur of these vectors using the determinant:

   • cur = x1 * y2 - x2 * y1

5. The very first non-zero cross product becomes the reference (pre) for the expected sign of all future cross products. This is because a non-zero cross product indicates the presence of an angle (not a straight line).

6. On finding a non-zero cross product, check if the current cross product cur has a different sign from the previous, pre:

   • If the signs differ (cur * pre < 0), then a change in the rotational direction has been detected, which implies that the polygon is not convex, and the function returns False.
   • If the signs are the same, update pre with the value of cur to compare with the cross product at the next vertex.

7. After checking all vertices, if no sign change is detected, the function returns True, confirming that the polygon is convex.

This algorithm effectively uses a linear scan over the set of vertices and constant space for the variables. It reflects an efficient approach to determining polygon convexity, with a time complexity of O(n) where n is the number of vertices.

Additionally, the code uses the modulo operator % which ensures that the indexing wraps around the list of points. This is especially useful for calculating vectors that involve the last point connecting to the first ((n-1) to 0). No additional data structures or complicated patterns are used, making this solution straightforward and elegant in terms of space and time efficiency.

Example Walkthrough

Let's consider a given set of points for a quadrilateral: points = [(0, 0), (1, 1), (1, 0), (0, -1)].

Following the solution approach, we want to determine whether this quadrilateral is a convex polygon by examining the cross products of consecutive edges.

1. We initialize pre and cur to 0.

2. The number of points n is 4.

3. We begin looping through each vertex:

   For i = 0:

   • The vector (x1, y1) is from points[0] to points[1], which is (1 - 0, 1 - 0) = (1, 1).
   • The vector (x2, y2) is from points[0] to points[2], which is (1 - 0, 0 - 0) = (1, 0).
   • The cross product cur is 1 * 0 - 1 * 1 = -1.
   • Since pre is zero, we set pre = cur, so now pre = -1.

   For i = 1:

   • The vector (x1, y1) is from points[1] to points[2], which is (1 - 1, 0 - 1) = (0, -1).
   • The vector (x2, y2) is from points[1] to points[3], which is (0 - 1, -1 - 1) = (-1, -2).
   • The cross product cur is 0 * (-2) - (-1) * (-1) = -1.
   • cur has the same sign as pre, so we continue with pre still -1.

   For i = 2:

   • The vector (x1, y1) is from points[2] to points[3], which is (0 - 1, -1 - 0) = (-1, -1).
   • The vector (x2, y2) is from points[2] to points[0], which is (0 - 1, 0 - 0) = (-1, 0).
   • The cross product cur is (-1) * 0 - (-1) * (-1) = 1.
   • cur has a different sign from pre, therefore, we now know the polygon is not convex, and we can return False.

Through this example, we can see how the computation of cross products for consecutive edges at each vertex can reveal a change in the rotational direction, signaling that the polygon is not convex. Our quadrilateral, based on the given set of points, is not a convex polygon.

Solution Implementation

Time and Space Complexity

The given Python code is designed to check if a polygon defined by a list of points is convex. Here's an analysis of its computational complexity.

Time Complexity:

The time complexity of the algorithm can be summarized as follows:

1. Loop Over Points: The code features a for-loop that iterates through the list of polygon vertices, where n is the number of points in the polygon. The loop runs exactly n times.

2. Constant Time Operations: Inside the loop, the code performs a constant number of operations. These operations include arithmetic calculations and if-conditions that do not depend on the size of the input. Therefore, these operations have a constant time complexity O(1).

Considering the above points, the overall time complexity of the function is dominated by the for-loop, which runs n times, with each iteration having O(1) operations. Thus, the total time complexity is O(n).

Space Complexity:

The space complexity of the algorithm is as follows:

1. Variables: The code uses a constant number of variables (n, pre, cur, x1, y1, x2, y2) regardless of the size of the input.

2. Input Storage: The space taken by the input list of points is not included in the space complexity analysis since it is a given input to the function and not an additional space requirement created by the function.

As a result, the space complexity of the function is constant, O(1), as it does not allocate any additional space that is dependent on the size of the input.

Therefore, the final complexities are:

• Time Complexity: O(n)
• Space Complexity: O(1)

Learn more about how to find time and space complexity quickly using problem constraints.