Check if 4 Line Segments form a Rectangle

In this article, we will solve the problem of Check if 4 Line Segments form a Rectangle. This is a core problem of Computational Geometry.

Table of contents:

1. Introduction to Problem Statement
2. Properties of the Rectangle
3. Solving the problem
4. Tracing a Few Examples
5. Implementing the Solution
6. Time and Space Complexity

Introduction to Problem Statement

In this problem, 4 line segments are given. Each line segment is denoted by the co-ordinates of its starting point and ending point. The problem is to ascertain whether these given line segments form a rectangle.

Properties of the Rectangle

Here, we state a few properties of the rectangle that we shall use to solve this problem.

1. A rectangle has four sides and four vertices.
2. Opposite sides of a rectangle are equal.
3. Adjacent sides of a rectangle are perpendicular.
4. Diagonals of a rectangle are equal.
5. The adjacent sides of the rectangle, along with the diagonal, satisfy the Pythagoras Theorem, i.e.,

a² + b² = c²

We shall use these properties in order to check whether the given line segments form a rectangle.

Solving the problem

This problem can be further broken into subproblems, and we shall proceed to the next subproblem only if the given line segments satisfy the current subproblem. The subproblems are as follows:

1. To check whether the total number of distinct end points in the given set of line segments is exactly 4 (because a rectangle has four vertices).
2. If the number of end points is 4, then we proceed in determining the distinct distances between all pairs of vertices. Note that in a rectangle there would be atmost 3 distinct distances (and at least 2, in case of a square).
3. If the number of distinct distances is three, we check whether the sum of squares of the smaller distances equals the square of the longer distance. If this holds true, then the given line segments form a rectangle.
4. If the number of distinct distances is equal to two, we check whether the twice the square of the smaller distance is equal to the square of the larger distance. If this holds true, then the given line segments form a rectangle.

Here, if the given line segments fail to satisfy even one of the given conditions, then we can conclude they do not form a rectangle. We need not further proceed.

Tracing a Few Examples

Now, we shall trace an example where the line segments are given by [(1, 1), (1, -1)], [(1, -1), (-1, -1)],[(-1, -1), (-1, 1)], and [(-1, 1), (1, 1)]. We obesrve the following:

• Here we can observe that there are four distinct points, given by (1, 1), (1, -1), (-1, -1), (-1, 1).
• On determining pairwise distances we find two distinct distances, given by 2 and 2√2.
• Since there are two distinct distances, we see here that the twice the square of 2 is 8, which is exactly the square of 2√2. Hence, the given line segments form a rectangle.

We shall now trace another example where the line segments are given by [(1, 1), (2, 2)], [(2, 2), (3, 2)], [(3, 2), (2, 1)], [(2, 1), (1, 1)].

• Here, we can observe that there are four distinct points, which are (1, 1), (2, 2), (3, 2), and (2, 1).
• On determining the pairwise distances, we find three distinct distances, given by √2, √5, and 1.
• Now, sum of sqaures of √2 and 1 is 3, which is not equal to the square of √5. Hence, the given line segments do not form a rectangle.

Implementing the Solution

We shall implement the solution using C++.

#include<iostream>
#include<vector>
#include<set>

using namespace std;

class EndPoints
{
  vector<vector<int> > points;
  public:
  set<int> dist;
  int size = 0;
    EndPoints(){
      points = {};
    }
    void add(int a, int b)
    {
      vector<int> v = {a, b};
      for(int i = 0; i<size; i++)
      {
        if(points[i][0] == a && points[i][1] ==b)
        {
          return;
        }
      }
      points.push_back(v);
      ++size;
    }
    int dist_cal(){
     
      for(int i = 0; i < size; i++)
      {
        for(int j = i + 1; j < size; j++)
        {
          dist.insert((points[j][1] - points[i][1])*(points[j][1] - points[i][1]) +
          (points[j][0] - points[i][0]) * (points[j][0] - points[i][0]));
        }
      }
      return dist.size();
    }
       
};

int check_rect(int arr[4][4])
{
  EndPoints s;
  for(int i = 0; i< 4; i++)
  {
    s.add(arr[i][0], arr[i][1]);
    s.add(arr[i][2], arr[i][3]);
  }
  if(s.size!=4) return 0;
  else{
    switch(s.dist_cal())
    {
      case 3: if (*s.dist.begin() + *(++s.dist.begin())==*s.dist.rbegin() ) return 1;
      else return 0;
      case 2: if(2* (*s.dist.begin()) == *s.dist.rbegin()) return 1;
      else return 0;
      default: return 0;

    }
  }
}

int main()
{
  int arr[4][4] = { 
        {1, 1, 1, -1},
        {1, -1, -1, -1},
        {-1, -1, -1, 1},
        {-1, 1, 1, 1}
    };
  if (check_rect(arr) == 1)
  {
    cout<<"RECTANGLE";
  }
  else cout<<"NOT A RECTANGLE";
}

Here, we note the following:

• The input is given in the form of a 4 x 4 array, where in each 1 x 4 array, the first two numbers denote the coordinates of the first point and the last two numbers denote the coordinates of the second points respectively.
• Here, we have a class called endpoints whose purpose is to store the distinct endpoints we have, and also to calculate the pairwise distances between them.
• First, we take each endpoint of each line segment, and if it is not already added to the class, we add it to the class and increment the size variable.
• After adding all endpoints, if the number of endpoints is exactly 4, then we proceed to finding all the pairwise distances. We use a set for the same because it is sorted and each element gets added only once. We find the squares of distances since we use only them to confirm the Pythagoras theorem.

Time and Space Complexity

Here, we know the maximum number of time each for loop shall run, since we shall always give the input in terms of a 4 x 4 array. Hence, although there are multiple for loops, the given code runs with a constant time complexity(O(1)).

Similarly, we know the maximum extra space that will be required to run on the program which will not depend on the input (whose size is fixed). Hence, the space complexity is also given by O(1).

In this article at OpenGenus, you must have the complete idea to solve the problem "Check if 4 Line Segments form a Rectangle".