CODEWITHSUNDEEP
c++algorithmgeometrycomputational-geometry
Amit Kumar
Amit Kumar

Reputation: 1517

How to make sure that a given set of points lie on the boundary of a possible square?

Given a set of integral coordinates, check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis. If such a square is possible give the minimum possible side of the square.

Suppose points are (0,0), (1,1), (2,2).
Answer : square is not possible .

Suppose points are (0,0), (0,2), (0,5), (0,7), `(3,0).
Answer : square is possible and minimum length of the side is 7.

I tried it and came up with many corner cases and it seemed impossible to tackle them individually. I was wondering if anyone can give a more generalized approach towards this kind of problem and how to think in the right direction. Thanks in advance. Range of coordinates: -1000 <= x ,y <= 1000

The number of points is <= 50.

New edit : One more corner case : (2,0) , (0,4) , (1,5) , (5,3) Answer : Square is possible with length 5 . Corner points of the square are (0,0) , (0,5) ,(5,5) ,(5,0)

Upvotes: 2

Views: 2602

Answers (4)

Sudeep Juvekar
Sudeep Juvekar

Reputation: 5108

The requirement of the axis helps us make following observations

  1. Every such square is bounded by two parallel vertical lines and every point on that vertical line has same X-coordinate. Let's call those coordinates maxX and minX. (One of them is smaller than other)
  2. Every such square is bounded by two parallel horizontal lines and every point on that vertical line has same Y-coordinate. Let's call those coordinates maxY and minY.
  3. This is crucial: Every point in input list must have a X-coordinate matching maxX or minX OR a Y-coordinate matching maxY or minY. (Notice the OR. If there is a point that matches neither, like (1, 1) in your earlier example, you have a counterexample).

Here is a c++-like pseudocode to compute these quantities. Assume you have an appropriate Point structure.

bool isSquare(vector<Point> points) { 
   double maxX = points[0].X;
   double minX = points[0].X;
   double maxY = points[0].Y;
   double minY = points[0].Y;

   // set maxX, minX, maxY, minY
   for(int i = 0; i < points.size(); i++) {
      maxX = max(points[i].X, maxX);
      minX = min(points[i].X, minX);
      maxY = max(points[i].Y, maxY);
      minY = min(points[i].Y, minY);
   }

   // Finally, find a point which matches neither {maxX, minX, maxY, minY}
   for(int i = 0; i < points.size(); i++) {
      if (points[i].X != maxX && points[i].X != minX && points[i].Y != maxY && points[i].Y != minY) return false;
    }

    // We are not done yet!
 }

Now passing the check in this code makes sure that the points at least form a rectangle and there is no point inside the rectangle. Making sure that the rectangle is a square is the harder part. For that part, you must check that:

  1. A point is on the corner of the rectangle., i.e., both its X-coordinate matches {maxX, minX} AND its Y-coordinate matches {maxY, minY}. If found, you then need to find the largest distance of such point from any other point on the corresponding edges.
  2. If no such corner exists, you are much better off!. In that case, length of the square-side is simply max(maxX-minX, maxY-minY).

You need to be careful while writing pseudocode for this corner-finding part and consider all cases. But I think once done, this would ultimately give the answer.

Upvotes: 1

Tristan Brindle
Tristan Brindle

Reputation: 16844

I'm trying to think of a way to do this in a single pass, but it's late at night here and I'm tired, so...

  • Run through all the elements once and record the minimum and maximum x and y values of the whole set. The side length of the square (if it exists) will be max(xmax-xmin, ymax-ymin).

  • Run through the points again. To describe a square parallel to the axes, each point must have

    x == xmin || x == xmax || y == ymin || y == ymax,

    that is, at least one coordinate must be on the side of the square. If any point fails, then you don't have a square.

I'm pretty sure this is sufficient, but doing it in two steps seems less than optimal. This is an interesting problem though, good luck.

Upvotes: 1

Nico Schertler
Nico Schertler

Reputation: 32647

If you define the square through xmin, xmax, ymin and ymax, then all points must lie on one of these coordinates. I.e. the square is valid, if for all vertices v:

v.x == xmin || v.x == xmax || v.y == ymin || v.y == ymax

Candidates for the bounds are the points' bounding rectangle's bounds. If you compute these boundaries, maintain a list of vertices for each edge.

If you can't assign every vertex to an edge, it is not possible to create the square.

Now it is very likely that the rectangle is not a square. So we need to enlarge its shortest side. If we have chosen the side, we need to choose whether to move the min or max edge. That's where the list of associated vertices comes into play. For the edge to move check whether all associated vertices are also associated with another edge. Then it is safe to move this edge. If we can move neither the min nor the max edge, it is impossible to create the square.

The resulting minimal side length is the distance of the edges.

Upvotes: 4

Nicko Po
Nicko Po

Reputation: 727

You can tackle this with the common concept of Axis Aligned Bounding Box (ABB). Given a set of points, compute ABB: Loop once through all points and find minimum x, minimum y, maximum x and maximum y. Then the box defined by two corners, lower left corner (min_x,min_y) and upper right corner (max, max y) will need to be checked against all the points to see if they lie on its perimeter. Since coordinates are integral (no floating point errors) its fairly easy to do: for each point, either the x-coordinate or the y-coordinate must match with the corresponding coordinates of the AAB, and the other coordinate has to be within range of the other coordinates. Hope that makes sense.

Upvotes: 0

Related Questions