Last Updated: 18 Apr, 2021

Convex polygon

Hard

Asked in company

Solve now

Problem statement

You are given an array ‘POINTS’ of size ‘N’. Each element of ‘POINTS’ contains two integers, ‘[X, Y]’ representing a point on the cartesian plane. These points, when joined sequentially, form a polygon. The task is to find if this polygon is convex (Convex polygon).

Example:

‘POINTS’ = [ [0, 0], [5, 0], [5, 5], [0, 5] ], ‘N’ = 4.

example

As the given polygon is a convex polygon, you should return ‘True’ as the answer.

Note:

1. The polygon formed by the given points is always a Simple polygon, i.e., exactly two edges intersect at each vertex, and the edges otherwise don’t intersect each other.

2. All the given points are unique.

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains an integer ‘N’ denoting the size of the array ‘POINTS’. Then, ‘N’ lines follow.

Each line contains two integers, ‘X’ and ‘Y’, representing an element in the array ‘POINTS’.

Output format:

For every test case, if the given polygon is convex, return ‘True’. Otherwise, return ‘False’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 1000
-10^4 <= Value in each element of ‘POINTS’ <= 10^4

Time limit: 1 second

Solve now

Approaches

01 Approach

For any edge ‘E’ in a convex polygon, every vertex ‘V’ should be either at one side of it (above/below) or on it. Consider the following two examples:

Let ‘AB’ be the edge between the vertices ‘(A, B)’ and ‘C’ be any vertex.

‘POS = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)’ (Position of point ‘C’ w.r.t. ‘AB’).

Here, ‘POS’ is the Z-component of the cross-product between the vectors ‘AB’ and ‘AC’. To decide if ‘C’ is below or above ‘AB’:

Suppose the angle between ‘AB’ and ‘AC’ is ‘T’ (‘0 < T < 180’), then the Z-component of ‘AB x AC’ will be coming out of the page. Thus, we have a positive ‘POS’ value.
Suppose the angle between ‘AB’ and ‘AC’ is ‘-T’ (‘0 < T < 180’), then the Z-component of ‘AB x AC’ will be going into the page. Thus, we have a negative ‘POS’ value.

In other words, ‘POS’ can be:

Positive: If ‘C’ is on one side of the edge ‘AB’ (let’s say above).
Negative: If ‘C’ is on the other side of the edge ‘AB’ (let’s say below).
Zero: If ‘C’ is on edge ‘AB’.

So, for any edge, if we find two vertices having opposite signs of ‘POS’, then we declare that the polygon is not convex.

Algorithm:

Run a loop where ‘a’ ranges from ‘0’ to ‘N - 1’ to iterate through all the edges ‘ab’ and ‘bc’:
- Set ‘POSITIVE = 0’. To count the number of positive 'POS' values.
- Set ‘NEGATIVE = 0’. To count the number of negative 'POS' values.
- Set ‘b = (a + 1) % N’. To handle the boundary case when ‘a = N - 1’.
- ‘xA = POINTS[a][0]’ and ‘yA = POINTS[a][1]’. Coordinates of point ‘a’.
- ‘xB = POINTS[b][0]’ and ‘yB = POINTS[b][1]’. Coordinates of point ‘b’.
- Run a loop where ‘c’ ranges from ‘0’ to ‘N - 1’ to iterate through all the vertices:
  - ‘xC = POINTS[c][0]’ and ‘yC = POINTS[c][1]. Coordinates of point ‘c’.
  - ‘POS = (xB - xA) * (yC - yA) - (yB - yA) * (xC - xA)’.
  - If ‘POS > 0’, then:
    - ‘POSITIVE += 1’.
  - Else, if ‘POS < 0’, then:
    - ‘NEGATIVE += 1’.
- If ‘POSITIVE > 0’ and ‘NEGATIVE > 0’, then we have vertices on both sides of the edge ‘ab’:
  - Return ‘False’ as the polygon is not convex.
Return ‘True’ as the answer.

Solve now

02 Approach

For a convex polygon, all the internal angles must be less than 180 degrees.

For the three vertices, ‘A’, ‘B’ and ‘C’, we have one edge from ‘A’ to ‘B’ and one edge from ‘B’ to ‘C’. So, for each such triplet, the angle between ‘AB’ and ‘BC’ must be less than 180 degrees.

From the sign of the ‘POS’ value computed in the previous approach, we can find out whether the angle between ‘AB’ and ‘BC’ exceeds 180 degrees or not. For the same ‘A’, ‘B’, ‘C’, depending on the order in which we chose them, ‘POS’ can produce either the exterior or the interior angle values. But, we know that the given polygon cannot have all its interior angles greater than 180 degrees. So, if all the ‘POS’ values are either positive or negative (all values have the same sign), we can say that the polygon is a convex polygon.

We have, ‘pos = (A.x - B.x) * (C.y - B.y) - (A.y - B.y) * (C.x - B.x)’.

Here, 'POS' is the Z-component of the cross-product between the vectors ‘AB’ and ‘AC’.

Algorithm:

Run a loop where ‘a’ ranges from ‘0’ to ‘N - 1’ to iterate through the pairs of edges ‘ab’ and ‘bc’:
- ‘b = (a + 1) % N’. To handle the boundary case when ‘a = N - 1’.
- ‘c = (b + 1) % N’. To handle the boundary case when ‘b = N - 1’.
- ‘xA = POINTS[a][0]’ and ‘yA = POINTS[a][1]’. Coordinates of point ‘a’.
- ‘xB = POINTS[b][0]’ and ‘yB = POINTS[b][1]’. Coordinates of point ‘b’.
- ‘xC = POINTS[c][0]’ and ‘yC = POINTS[c][1]. Coordinates of point ‘c’.
- ‘POS = (xA - xB) * (yC - yB) - (yA - yB) * (xC - xB)’.
- If ‘POS > 0’, then:
  - ‘POSITIVE += 1’.
- Else, if ‘POS < 0’, then:
  - ‘NEGATIVE += 1’.
- If ‘POSITIVE > 0’ and ‘NEGATIVE > 0’, then at least one interior angle is more than 180 degrees:
  - Return ‘False’ as the polygon is not convex.
Return ‘True’ as the answer.

Solve now