Problem Solving: Quadrilateral Shapes

In this lesson, we’ll devise a solution to write a program that takes coordinates and identifies the geometric shape.

So let’s get to it!

Quadrilateral shapes

A quadrilateral is a four-sided two-dimensional shape. If a quadrilateral has four equal sides and every two adjacent sides are at right angles to each other, we will call it a square. If a quadrilateral has opposite equal sides, but differently sized adjacent sides, and every two adjacent sides are right-angled, we call it a rectangle.

Rhombus is a quadrilateral with equal sides. The only difference between a rhombus and a square is that in a rhombus, the angles are not right angles.

Similarly, parallelogram is similar to a rectangle (it has equal opposite sides), but none of the angles are right angles.

Let us write a program that recognizes quadrilateral shapes.

Problem statement

Write a program that takes coordinates of four points, each having an x-axis and a y-axis coordinates, from the user as input and tells whether these points form a rectangle, a square, a rhombus, or any general quadrilateral.

Sample input

P1	0 0
P2	1 0
P3	1 1
P4	0 1

Sample output

Square

Designing the strategy (algorithm)

To write a program for the above problem, we first need to figure out the memory requirement of the program. We need to take four points, each with an x-axis and a y-axis coordinates. Since two numbers correspond to one point, we will take a total of eight integers as input for four points.

This is what we have so far:

Now, we have four coordinates and we need to calculate each side. Each side is nothing but the distance between two points. How do we calculate sides and compare each side with the other sides to identify shapes in the program?

Let us assume that the user will always give input in a counterclockwise order.

All we need to do is compute four distances for sides and two distances for diagonals. In other words, we need the distances between $\overline{P_1P_2}$, $\overline{P_2P_3}$, $\overline{P_3P_4}$, $\overline{P_4P_1}$, $\overline{P_1P_3}$, and $\overline{P_2P_4}$ as s1, s2, s3, s4, d1, and d2, respectively. This is almost impossible to compute right now, as distance computing involves calculating the square root, which, at this point, we don’t know how to compute. We will solve it without computing the square root.

Computing the distance between two coordinates

To calculate the distance between two coordinates, we can use the distance formula.

$$Distance =\sqrt{(p2x-p1x)^2 + (p2y-p1y)^2}$$

To simplify the above formula:

$$Distance^{2} ={(p2x-p1x)^2 + (p2y-p1y)^2}$$

Programatically, it can be written as:

$$Distance Square=((p2x-p1x)*(p2x-p1x))+((p2y-p1y)*(p2y-p1y))$$

If the two distances are of the same length, then their distance squares will also be of the same length. Also, note that computing a squared distance is less costly than calculating the distance (taking the square root of the squared distance). So in this example, we can avoid taking the square root.

Using squared distance instead of distance

Hence, instead of using distance to compute sides, we will use the distance-square metric due to the following fact: if the two sides are of equal length, then their squares are also of equal length. (Note, however, that this statement’s inverse may not be true).

Let us compute each side and diagonal (by computing their distance squares).

Now we have a formula for each side of the quadrilateral shape. After computing s1, s2, s3, s4, d1, and d2. We will compare each computed distance with the others to determine the shape. For example, if s1 is equal to s2, s3, and s4, we can move on to check the diagonal distance of d1 and d2, and if both diagonals and all sides are equal, then we can say that it’s a square. But if the diagonals are not of the same length but the four sides are of the same length, we can say it’s a rhombus.

In the same way, we will calculate the equality of the opposite sides and further compare diagonals. If they are the same, we can call it a rectangle. Otherwise, we will call it a parallelogram.

If the opposite sides are not equal, it is an irregular shape and qualifies to be called a general quadrilateral.

Let us write the complete code below and run it to see the output.

In lines 17–20, we compute each side’s squared distance.

In lines 21–22, we compute both diagonals’ distances.

In line 24, we match s1 with s2, s3, and, s4 to check if all sides are equal or not.

In line 26, we match the distances of both diagonals, d1 and d2, to check if all sides are equal. If d1 and d2 are equal, we can say it’s a square. Otherwise, it is a rhombus.

In lines 31–37 whether we have a rectangle or a parallelogram. If two sides are equal, we check the diagonal in line 33. If the diagonals are equal, we can say that it is a rectangle. Otherwise, it is a parallelogram.

In line 39, we have the else part. If all conditions are false, the else part gets executed and it’s printed that the shape is a quadrilateral.