Jobs

Interviews

Discussions

Convex Polygon

Medium

Asked by:

29 views

Topics:

Arrays

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

There are at least 3 and at most 10,000 points.
Coordinates are in the range -10,000 to 10,000.
You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don't intersect each other.

Example 1:

Input: [[0,0],[0,1],[1,1],[1,0]]
Output: True
Explanation

Example 2:

Input: [[0,0],[0,10],[10,10],[10,0],[5,5]]
Output: False
Explanation

Try coding it in LeetCode

Convex Polygon

Medium

Asked by:

29 views

Topics:

Arrays

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

There are at least 3 and at most 10,000 points.
Coordinates are in the range -10,000 to 10,000.
You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don't intersect each other.

Example 1:

Input: [[0,0],[0,1],[1,1],[1,0]]
Output: True
Explanation

Example 2:

Input: [[0,0],[0,10],[10,10],[10,0],[5,5]]
Output: False
Explanation

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type represents the polygon's vertices, and what is the expected precision for the coordinates (e.g., integers or floating-point numbers)?
Can the input list of vertices be empty, or contain fewer than three points (which wouldn't form a polygon)?
Is the input list of vertices guaranteed to be in a specific order (e.g., clockwise or counter-clockwise)?
Are there any constraints on the coordinates of the vertices, such as maximum or minimum values?
By 'convex', do you mean strictly convex (no three consecutive points are collinear) or convex (three consecutive points can be collinear)? And how should collinear points be handled?

Brute Force Solution

Approach

To determine if a shape is a convex polygon using a brute force method, we'll examine every possible combination of three points within the shape. The core idea is to verify that all other points in the shape consistently lie on the same side of each line formed by any two points.

Here's how the algorithm would work step-by-step:

Take the first three points of the shape and create a triangle.
Consider the line formed by the first two points of this triangle.
Check where all the other points in the shape are located relative to this line. They should all be on the same side.
If even one point is on the other side, the shape is not convex. We stop here.
Otherwise, repeat the process by considering the line formed by the next two points of the triangle.
Again, check that all other points are on the same side of the line. If not, stop.
Do this for all three lines formed by the triangle.
Now, choose a different set of three points to form a new triangle and repeat the whole process with this new triangle.
Continue this process until you have checked all possible combinations of three points. If all combinations pass the test (all other points are always on the same side for every line), the shape is convex.

Code Implementation

def is_convex_polygon(points):
    number_of_points = len(points)
    
    # Need at least 3 points to form a polygon
    if number_of_points < 3:
        return False

    def cross_product(point_a, point_b, point_c):
        return (point_b[0] - point_a[0]) * (point_c[1] - point_a[1]) - \
               (point_b[1] - point_a[1]) * (point_c[0] - point_a[0])

    for i in range(number_of_points):
        for j in range(i + 1, number_of_points):
            for k in range(j + 1, number_of_points):

                # Iterate over the edges of the triangle
                for edge_index in range(3):
                    if edge_index == 0:
                        point_one = points[i]
                        point_two = points[j]
                    elif edge_index == 1:
                        point_one = points[j]
                        point_two = points[k]
                    else:
                        point_one = points[k]
                        point_two = points[i]

                    same_side = True
                    side = 0

                    # Check all the other points
                    for point_index in range(number_of_points):
                        if point_index != i and point_index != j and point_index != k:
                            
                            # Determine which side of the line the point is on
                            cross_product_result = cross_product(point_one, point_two, points[point_index])

                            if side == 0 and cross_product_result != 0:
                                side = 1 if cross_product_result > 0 else -1
                            elif cross_product_result != 0 and \
                                 (1 if cross_product_result > 0 else -1) != side:
                                
                                # If point is on different side, not convex
                                same_side = False
                                break

                    if not same_side:
                        return False

    return True

Big(O) Analysis

Time Complexity

O(n^4) – The provided algorithm iterates through all possible combinations of three points to form triangles, which takes O(n^3) time because we choose 3 points out of n. For each such triangle, it iterates through all the other points (O(n)) to check if they lie on the same side of each edge of the triangle. Since there are three edges in a triangle, this check is still O(n) for each triangle. Therefore the total time complexity is O(n^3) * O(n) = O(n^4).

Space Complexity

O(1) – The algorithm iterates through combinations of points within the input polygon, but it doesn't create any auxiliary data structures whose size depends on the number of points (N). It only uses a constant number of variables for indices and potentially intermediate calculations during side determination. Therefore, the auxiliary space complexity is constant, independent of the input size N, resulting in O(1) space complexity.

Optimal Solution

Approach

To check if a shape is a convex polygon, we don't need to check every angle. The trick is to examine the direction of turns we make as we travel around the shape's edges, and see if all the turns go the same way.

Here's how the algorithm would work step-by-step:

Imagine walking around the edge of the shape, connecting the points in order.
At each point, figure out if you are turning left or right. This is based on the angle formed by the two lines meeting at that point.
Keep track of whether you've seen only left turns, only right turns, or a mix of both.
If you find both left turns and right turns at any point in your journey, then the shape is not convex.
If you make it all the way around the shape and you've only seen left turns or only seen right turns (or no turns at all, meaning it's a straight line), then the shape is convex.

Code Implementation

def is_convex(points):
    number_of_points = len(points)
    if number_of_points < 3:
        return True

    # Determine initial turn direction
    turn_direction = 0
    for i in range(number_of_points):
        point_one = points[i]
        point_two = points[(i + 1) % number_of_points]
        point_three = points[(i + 2) % number_of_points]

        cross_product = (point_two[0] - point_one[0]) * (point_three[1] - point_two[1]) - \
                        (point_two[1] - point_one[1]) * (point_three[0] - point_two[0])

        if cross_product != 0:
            turn_direction = cross_product > 0
            break

    # If all points are co-linear.
    if turn_direction == 0:
        return True

    # Check that all subsequent turns are in the same direction.
    for i in range(number_of_points):
        point_one = points[i]
        point_two = points[(i + 1) % number_of_points]
        point_three = points[(i + 2) % number_of_points]

        cross_product = (point_two[0] - point_one[0]) * (point_three[1] - point_two[1]) - \
                        (point_two[1] - point_one[1]) * (point_three[0] - point_two[0])

        if cross_product != 0:
            current_direction = cross_product > 0
            # If turn changes direction, it's not convex
            if current_direction != turn_direction:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each point (vertex) of the polygon once to determine the direction of the turn at each vertex. The number of vertices is represented by n, which is the size of the input array. For each vertex, a constant number of calculations (cross product) is performed to determine the turn direction. Since the number of operations is directly proportional to the number of vertices, the time complexity is O(n).

Space Complexity

O(1) – The algorithm described iterates through the input points, calculating the direction of turns. It only needs to store a constant number of variables to track the turn direction and whether mixed turn types have been encountered. No auxiliary data structures like lists or hash maps are created that depend on the number of input points. Therefore, the space used remains constant regardless of the number of points, N, in the polygon, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Input is null or an empty array.	Return 'false' or throw an exception indicating invalid input, as a polygon requires at least three points.
Input array contains fewer than 3 points.	Return 'false' immediately, as a polygon cannot be formed with fewer than three points.
The points are collinear (lie on the same line).	The cross-product will be zero for all triplets; return 'false' since it's not a polygon.
The points are in reverse order (clockwise vs counter-clockwise).	The cross-product signs will all be negative, indicating clockwise, so handle consistently.
Points are very close together (floating point precision issues).	Use a small epsilon value to compare cross-product results to zero, accounting for floating-point errors.
Integer overflow when calculating the cross product with large coordinates.	Use long integers or a similar data type to prevent overflow during cross-product calculations.
The polygon is self-intersecting.	The simple cross product method won't work; a more robust algorithm for self-intersection detection is needed.
Duplicate points in the input array.	Remove the duplicate points as they do not affect convexity, or handle them as collinear points.

Input is null or an empty array.

How to Handle:

Return 'false' or throw an exception indicating invalid input, as a polygon requires at least three points.

Input array contains fewer than 3 points.

How to Handle:

Return 'false' immediately, as a polygon cannot be formed with fewer than three points.

The points are collinear (lie on the same line).

How to Handle:

The cross-product will be zero for all triplets; return 'false' since it's not a polygon.

The points are in reverse order (clockwise vs counter-clockwise).

How to Handle:

The cross-product signs will all be negative, indicating clockwise, so handle consistently.

Points are very close together (floating point precision issues).

How to Handle:

Use a small epsilon value to compare cross-product results to zero, accounting for floating-point errors.

Integer overflow when calculating the cross product with large coordinates.

How to Handle:

Use long integers or a similar data type to prevent overflow during cross-product calculations.

The polygon is self-intersecting.

How to Handle:

The simple cross product method won't work; a more robust algorithm for self-intersection detection is needed.

Duplicate points in the input array.

How to Handle:

Remove the duplicate points as they do not affect convexity, or handle them as collinear points.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type represents the polygon's vertices, and what is the expected precision for the coordinates (e.g., integers or floating-point numbers)?
Can the input list of vertices be empty, or contain fewer than three points (which wouldn't form a polygon)?
Is the input list of vertices guaranteed to be in a specific order (e.g., clockwise or counter-clockwise)?
Are there any constraints on the coordinates of the vertices, such as maximum or minimum values?
By 'convex', do you mean strictly convex (no three consecutive points are collinear) or convex (three consecutive points can be collinear)? And how should collinear points be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first three points of the shape and create a triangle.
Consider the line formed by the first two points of this triangle.
Check where all the other points in the shape are located relative to this line. They should all be on the same side.
If even one point is on the other side, the shape is not convex. We stop here.
Otherwise, repeat the process by considering the line formed by the next two points of the triangle.
Again, check that all other points are on the same side of the line. If not, stop.
Do this for all three lines formed by the triangle.
Now, choose a different set of three points to form a new triangle and repeat the whole process with this new triangle.
Continue this process until you have checked all possible combinations of three points. If all combinations pass the test (all other points are always on the same side for every line), the shape is convex.

Code Implementation

def is_convex_polygon(points):
    number_of_points = len(points)
    
    # Need at least 3 points to form a polygon
    if number_of_points < 3:
        return False

    def cross_product(point_a, point_b, point_c):
        return (point_b[0] - point_a[0]) * (point_c[1] - point_a[1]) - \
               (point_b[1] - point_a[1]) * (point_c[0] - point_a[0])

    for i in range(number_of_points):
        for j in range(i + 1, number_of_points):
            for k in range(j + 1, number_of_points):

                # Iterate over the edges of the triangle
                for edge_index in range(3):
                    if edge_index == 0:
                        point_one = points[i]
                        point_two = points[j]
                    elif edge_index == 1:
                        point_one = points[j]
                        point_two = points[k]
                    else:
                        point_one = points[k]
                        point_two = points[i]

                    same_side = True
                    side = 0

                    # Check all the other points
                    for point_index in range(number_of_points):
                        if point_index != i and point_index != j and point_index != k:
                            
                            # Determine which side of the line the point is on
                            cross_product_result = cross_product(point_one, point_two, points[point_index])

                            if side == 0 and cross_product_result != 0:
                                side = 1 if cross_product_result > 0 else -1
                            elif cross_product_result != 0 and \
                                 (1 if cross_product_result > 0 else -1) != side:
                                
                                # If point is on different side, not convex
                                same_side = False
                                break

                    if not same_side:
                        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine walking around the edge of the shape, connecting the points in order.
At each point, figure out if you are turning left or right. This is based on the angle formed by the two lines meeting at that point.
Keep track of whether you've seen only left turns, only right turns, or a mix of both.
If you find both left turns and right turns at any point in your journey, then the shape is not convex.
If you make it all the way around the shape and you've only seen left turns or only seen right turns (or no turns at all, meaning it's a straight line), then the shape is convex.

Code Implementation

def is_convex(points):
    number_of_points = len(points)
    if number_of_points < 3:
        return True

    # Determine initial turn direction
    turn_direction = 0
    for i in range(number_of_points):
        point_one = points[i]
        point_two = points[(i + 1) % number_of_points]
        point_three = points[(i + 2) % number_of_points]

        cross_product = (point_two[0] - point_one[0]) * (point_three[1] - point_two[1]) - \
                        (point_two[1] - point_one[1]) * (point_three[0] - point_two[0])

        if cross_product != 0:
            turn_direction = cross_product > 0
            break

    # If all points are co-linear.
    if turn_direction == 0:
        return True

    # Check that all subsequent turns are in the same direction.
    for i in range(number_of_points):
        point_one = points[i]
        point_two = points[(i + 1) % number_of_points]
        point_three = points[(i + 2) % number_of_points]

        cross_product = (point_two[0] - point_one[0]) * (point_three[1] - point_two[1]) - \
                        (point_two[1] - point_one[1]) * (point_three[0] - point_two[0])

        if cross_product != 0:
            current_direction = cross_product > 0
            # If turn changes direction, it's not convex
            if current_direction != turn_direction:
                return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is null or an empty array.	Return 'false' or throw an exception indicating invalid input, as a polygon requires at least three points.
Input array contains fewer than 3 points.	Return 'false' immediately, as a polygon cannot be formed with fewer than three points.
The points are collinear (lie on the same line).	The cross-product will be zero for all triplets; return 'false' since it's not a polygon.
The points are in reverse order (clockwise vs counter-clockwise).	The cross-product signs will all be negative, indicating clockwise, so handle consistently.
Points are very close together (floating point precision issues).	Use a small epsilon value to compare cross-product results to zero, accounting for floating-point errors.
Integer overflow when calculating the cross product with large coordinates.	Use long integers or a similar data type to prevent overflow during cross-product calculations.
The polygon is self-intersecting.	The simple cross product method won't work; a more robust algorithm for self-intersection detection is needed.
Duplicate points in the input array.	Remove the duplicate points as they do not affect convexity, or handle them as collinear points.

Input is null or an empty array.

How to Handle:

Return 'false' or throw an exception indicating invalid input, as a polygon requires at least three points.

Input array contains fewer than 3 points.

How to Handle:

Return 'false' immediately, as a polygon cannot be formed with fewer than three points.

The points are collinear (lie on the same line).

How to Handle:

The cross-product will be zero for all triplets; return 'false' since it's not a polygon.

The points are in reverse order (clockwise vs counter-clockwise).

How to Handle:

The cross-product signs will all be negative, indicating clockwise, so handle consistently.

Points are very close together (floating point precision issues).

How to Handle:

Use a small epsilon value to compare cross-product results to zero, accounting for floating-point errors.

Integer overflow when calculating the cross product with large coordinates.

How to Handle:

Use long integers or a similar data type to prevent overflow during cross-product calculations.

The polygon is self-intersecting.

How to Handle:

The simple cross product method won't work; a more robust algorithm for self-intersection detection is needed.

Duplicate points in the input array.

How to Handle:

Remove the duplicate points as they do not affect convexity, or handle them as collinear points.