Determine if given points form a rectangle

[Wictorian]

Using python I wanna determine if given points form a rectangle. Keep in mind that more than 4 pointswill be given and the rectangle can be rotated. I have done research and though quite a bit about this but couldn't come to a conclusion. Can you think of anything?

 

[Electronics Wizardy]

There are probably much better ways to do this, but this is my first though. Since a rectangle has 4 90 degree angles, Id check if there is a 90 degree angle for each point compared to 2 other points.

 

So if you have the points abcd, then check the angle a by checking the angles of cad, bac, bad. If there is a 90 degree angle found, continue to angle b and so on. If all have a 90 degree angle its a rectangle.

 

From my quick thoughts, there is no shape where each of the angles abcd has a 90 degree angle with 2 of the other points that isn't a rectangle. But I might be wrong.

 

 

Edit: One other solution. Find the center point, then find the distance to all the other points. If the distance are all the same, its a rectangle.

[Eigenvektor]

So you're saying you have an indeterminate number of points and if you connect those (in whichever way) they need to form a rectangle?

 

Quick thoughts:

• Try to find the points with the most extreme (+x,+y), (+x,-y), (-x,+y), (-x, -y) values.
• Check if these points form a rectangle (opposite lines, same length, 90° angles)
• Check if all other points are on the lines connecting these points

 

 

For rectangle A, the red point has the same x coordinate as several other points, but there is no point that has the same x, while also having the largest possible y value. So it must be a corner.

 

For rectangle B, the red point has the smallest possible x coordinate, so it must be an corner.

 

If you repeat that test for all other points, you should be able to identify the potential corner points. Once you have these, you can check if they form a rectangle. Once you have determined that is true. all that is left to do is to test if all of the gray points are along one of the lines connecting these corner points.

• Identify all points with the smallest x. If there is only one, it is a corner. If there are multiple, the one with the largest y and the smallest y must be corners.
• Identify all points with the largest x. If there is only one, it is an corner. If there are multiple, the one with the largest y and the smallest y must be corners.
• Identify all points with the smallest y. If there is only one, it is and corner. If there are multiple, the one with the largest x and smallest x must be corners.
• Identify all points with the largest y. If there is only one, it is and corner. If there are multiple, the one with the largest x and smallest x must be corners.

After these tests you should be left with exactly 4 corner points. If there are less or more, then it can't be a rectangle. Once you have the corners, form a line between each of these. Any combination of 3 corner points must form a right angle (r/g/b, g/b/y, b/y/r, y/r/g).

 

When you measure the distance between each center point of a right angle and its other two corners, there should at most be two different distances (if all distances are equal you have a square).

 

Every three-point combination must share one line with two other three point-combination that share two points. The independent lines must have the same length. E.g. y/r/g and r/g/b have the line between r/g in common. The lines between y/r and g/b must have the same length.

 

Every three-point combination must share no lines with at most one other three point combination that shares two points. Two lines of each combination must share the same length. E.g. r/g/b and b/y/r have no lines in common. The line between r/g and b/y have the same length. The lines between g/b and y/r have the same length.

 

You should now be able to test if all other points are on one of these lines between corner points.

[Sauron]

The simplest way to do this would be to figure out all combinations of 4 points, list all ways in which they can be connected between them with 4 edges and see if any of those form a rectangle.

 

A possible optimization would be to first check for each point if there are two points that form a right angle with it and remove it from the pool if the answer is no.

[wanderingfool2]

13 hours ago, Electronics Wizardy said:

Edit: One other solution. Find the center point, then find the distance to all the other points. If the distance are all the same, its a rectangle.

hmm, that's actually pretty neat to think about like that.  Mathematically it's pretty simple as well getting a center point.  (too late, can't think if this holds true in all scenarios)

 

I was going to suggest similar to your non-edited answer...If you have points A,B,C,D...then you check if AB (dot product) BC = 0, BC (dp) CD = 0, CD (dp) DA = 0, and DA (dot) AB = 0

 

Since dot products of vectors are 0

https://www.mathsisfun.com/algebra/vectors-dot-product.html

 

Dot products are super quick to calculate as well

[Franck]

17 hours ago, Wictorian said:

Using python I wanna determine if given points form a rectangle. Keep in mind that more than 4 pointswill be given and the rectangle can be rotated. I have done research and though quite a bit about this but couldn't come to a conclusion. Can you think of anything?

 

Do the corners are part of the list of given points ?

[Eigenvektor]

17 hours ago, Electronics Wizardy said:

Edit: One other solution. Find the center point, then find the distance to all the other points. If the distance are all the same, its a rectangle.

That only works if you have four points that correspond to the rectangle's corners. As Wictorian said, more than four points may be given.

[Wictorian]

19 hours ago, Eigenvektor said:

So you're saying you have an indeterminate number of points and if you connect those (in whichever way) they need to form a rectangle?

 

Quick thoughts:

• Try to find the points with the most extreme (+x,+y), (+x,-y), (-x,+y), (-x, -y) values.
• Check if these points form a rectangle (opposite lines, same length, 90° angles)
• Check if all other points are on the lines connecting these points

 

 

For rectangle A, the red point has the same x coordinate as several other points, but there is no point that has the same x, while also having the largest possible y value. So it must be a corner.

 

For rectangle B, the red point has the smallest possible x coordinate, so it must be an corner.

 

If you repeat that test for all other points, you should be able to identify the potential corner points. Once you have these, you can check if they form a rectangle. Once you have determined that is true. all that is left to do is to test if all of the gray points are along one of the lines connecting these corner points.

• Identify all points with the smallest x. If there is only one, it is a corner. If there are multiple, the one with the largest y and the smallest y must be corners.
• Identify all points with the largest x. If there is only one, it is an corner. If there are multiple, the one with the largest y and the smallest y must be corners.
• Identify all points with the smallest y. If there is only one, it is and corner. If there are multiple, the one with the largest x and smallest x must be corners.
• Identify all points with the largest y. If there is only one, it is and corner. If there are multiple, the one with the largest x and smallest x must be corners.

After these tests you should be left with exactly 4 corner points. If there are less or more, then it can't be a rectangle. Once you have the corners, form a line between each of these. Any combination of 3 corner points must form a right angle (r/g/b, g/b/y, b/y/r, y/r/g).

 

When you measure the distance between each center point of a right angle and its other two corners, there should at most be two different distances (if all distances are equal you have a square).

 

Every three-point combination must share one line with two other three point-combination that share two points. The independent lines must have the same length. E.g. y/r/g and r/g/b have the line between r/g in common. The lines between y/r and g/b must have the same length.

 

Every three-point combination must share no lines with at most one other three point combination that shares two points. Two lines of each combination must share the same length. E.g. r/g/b and b/y/r have no lines in common. The line between r/g and b/y have the same length. The lines between g/b and y/r have the same length.

 

You should now be able to test if all other points are on one of these lines between corner points.

This is nice. I have had some of the thoughts. However one obstacle is that corner points don't have to be given. Also for instace 4 points in the same line can be given. Then ir is difficult to determine which side/corner the points will be on.

[Wictorian]

19 hours ago, Sauron said:

The simplest way to do this would be to figure out all combinations of 4 points, list all ways in which they can be connected between them with 4 edges and see if any of those form a rectangle.

 

A possible optimization would be to first check for each point if there are two points that form a right angle with it and remove it from the pool if the answer is no.

There are infinite combinations.. Keep in midn that corners dont have to be given.

[Wictorian]

2 hours ago, Franck said:

Do the corners are part of the list of given points ?

Not necessarily.

[Sauron]

6 minutes ago, Wictorian said:

There are infinite combinations..

No, there are not infinite combinations of 4 points out of a finite set.

[Wictorian]

13 minutes ago, Sauron said:

No, there are not infinite combinations of 4 points out of a finite set.

What do you mean by combinaitons? 

 

Look at this picture. We can just extend the right side infinitely creating infinite combinations. 

[Sauron]

30 minutes ago, Wictorian said:

What do you mean by combinaitons? 

 

Look at this picture. We can just extend the right side infinitely creating infinite combinations. 

Oh, I see now. I thought you had to find the 4 corners of a rectangle within a group of points.

 

well, for a group of points to all be on a rectangle in this way you need to be able to find 4 lines that together include all of them. Any two points form a line so you can check all possible combinations of 4 lines to see if they intersect all points and if they cross in a way that forms a rectangle.

 

If you also want to find cases where one edge has 0 points then you can look for 1 line including all points (this necessarily lets you include all points in a rectangle), two perpendicular or parallel lines including all points, or two parallel and one perpendicular line.

 

The case where this still doesn't really work is where there is only one point for some edges.

[Franck]

2 hours ago, Wictorian said:

What do you mean by combinaitons? 

 

Look at this picture. We can just extend the right side infinitely creating infinite combinations. 

If that is your data then your task is not doable unless you accept a random rectangle as a valid answer

[wanderingfool2]

29 minutes ago, Franck said:

If that is your data then your task is not doable unless you accept a random rectangle as a valid answer

I thought that might be what is being asked...either that or whether or not the points form an unique rectangle, which would also be answerable.

 

Actually even in the general case, you could create an expression regarding all valid rectangles.

 

3 hours ago, Wictorian said:

What do you mean by combinaitons? 

 

Look at this picture. We can just extend the right side infinitely creating infinite combinations. 

I accidentally closed after I went through an initial guess on how to do things (probably inefficiently).  Let me ask this though to get clarification.

 

You have a set of points.  Are you to determine whether or not there exists an unique rectangle that fits all the points...or is the question, given a set of points determine if there exists a rectangle that have the points all along the edges

[Eigenvektor]

→

4 hours ago, Wictorian said:

This is nice. I have had some of the thoughts. However one obstacle is that corner points don't have to be given. Also for instace 4 points in the same line can be given. Then ir is difficult to determine which side/corner the points will be on.

This complicates things a lot. I think you need to add additional constraints to make this solvable. E.g. "smallest rectangle whose edges touch all points". If, for example, you only have two given points then there's an infinite number of solutions, which essentially makes this unsolvable. Or if all of your points are on the same line.

 

I think I'd still do a first round with a variation of what I proposed above, because that will be much faster:

1. Merge identical points (i.e. keep only one instance)
2. If the number of remaining points is
   • n ≤ 2 → no solution/infinite solutions, abort
   • n = 3 → see below
   • n ≥ 4 → go to step 3
3. Sort points by their x-coordinate
4. Keep the one(s) with the x_min and x_max
   • If there is only one for both keep them as corners
   • If there is only one for either x_min or x_max, but multiple for the other, abort, no solution
   • Otherwise keep the ones with y_min and y_max as corners
5. Repeat steps 3 and 4 for the y-coordinate
6. You should be left with 4 distinct corners
   • Otherwise, no solution, abort
7. Select three corners at random
8. It must be possible to connect them in a way that forms a right angle
   • Otherwise, no solution, abort
9. Keep the two corners that are not the center of the right angle
10. They must form a right angle with the remaining corner, using it as the center point
11. The two corners and the two other points must have the same distance from one another

You should now have a rectangle. Make sure that all remaining points are neither outside nor inside the rectangle (i.e. all of them are on its edge). Would it find a solution to the points below? I don't think so…

 

If you can't find a solution with these steps, you'll have to go the much more computationally expensive route to find four parallel/orthogonal lines that include all of the points as @Sauron said. Not sure how to find an abort condition here where you can be certain that no solution can ever be found.

 

3 point solution:

• Select two points (p1, p2) at random.
• Connect them with a straight line.
  • If point p3 is on that line, abort, no solution/infinite solutions
• Send a parallel line through the third point
• Now connect the two lines with orthogonal lines, starting at the two points
• You now have one possible solution

 

This already has three possible solutions, depending on which two points you pick as a starting point. The more points you have the more possible solutions there are (and the higher the chance there is none)… Not sure there's an elegant solution for an arbitrary number of points that is solvable in finite time.

 

[wanderingfool2]

35 minutes ago, Eigenvektor said:

If you can't find a solution with these steps, you'll have to go the much more computationally expensive route to find four parallel/orthogonal lines that include all of the points as @Sauron said. Not sure how to find an abort condition here where you can be certain that no solution can ever be found.

Luckily dot products are cheap, so you can do them without much load to find perpendicular.  Same with parallel. With a bit of optimizations in terms of picking the correct points,  you could reduce the problem down into quite a reasonable calculation.  (I suspect you could get it to a O(n) type of timing...vs having to sort the points would be O(nlogn)...so would get taxed under a large number of points)

 

My initial post that I accidentally deleted, where I was spitballing, my rough solution was as follows (and assuming unique points)

 

If len(points) == 4 return True  # since any 4 points in a 2d space you can generate multiple rectangles

From the rest of points grab any 5.

Of those 5 points,  you are guaranteed to have at least 2 of the points forming a line that follows the same path as the resulting rectangle.

With a bit of trickery (a bit of math), you can conclude 5 potential lines; where one of those 5 lines has to be the answer (if you eliminate all those lines then you know it's impossible).

 

With those 5 lines a few things can happen when looking at the 5 points.

If 3 of the 5 points that exist on the line then you know that line (AB) has to exist in the rectangle

Using the remaining 2 points (Lets call C and D) you can determine a few things,  if CD and AB are NOT parallel then you can determine the 2 lines that connect to AB.  (At which point the answer becomes trivial, you just check the remaining points...as if it doesn't exist on the 3 lines then you create the last wall...and if the remaining points don't match with any of those edges then it doesn't work.

 

You can do similar steps as well to optimize it down to doing hopefully a minimal amount of operations.

[Sauron]

45 minutes ago, Eigenvektor said:

This already has three possible solutions, depending on which two points you pick as a starting point. The more points you have the more possible solutions there are (and the higher the chance there is none)… Not sure there's an elegant solution for an arbitrary number of points that is solvable in finite time.

it depends; if you need to list all possible rectangles then yeah, it's probably impossible with these conditions - if you just need to find any rectangle then it's possible. You can probably optimize the edge combinatorics method since if more than two points are on the same line then that line MUST be an edge of the rectangle, or else there is no rectangle at all.

[Eigenvektor]

51 minutes ago, Sauron said:

You can probably optimize the edge combinatorics method since if more than two points are on the same line then that line MUST be an edge of the rectangle, or else there is no rectangle at all.

1 hour ago, wanderingfool2 said:

If 3 of the 5 points that exist on the line then you know that line (AB) has to exist in the rectangle

True. As long as you have 3 or more points on the same line, they must be part of an edge. Otherwise it's not possible to construct a rectangle with them.

 

So thinking a bit, assuming you have no 3+ points in a line.

- Pick any two points and run a straight line L1 through them

- If you have points on both sides of that line, start over

- Pick the point furthest away from L1, run line L2 (parallel to L1) through it

- All the remaining points are between L1 and L2

- If you have more than four points remaining, there is no solution, otherwise they would be part of a 3+ point line

- Run line L3 (orthogonal to L1/L2) through as many remaining points as possible

- You must now be able to run line L4 (parallel to L3) through the remaining points, otherwise this is not a solution and you need to start over with two different points

 

If you have three or more points on the same line, then there is no solution that doesn't include them as the "starting line", i.e. there must be a parallel line that goes through the point furthest away and there must be two orthogonal lines that can touch all of the remaining points.

 

Additional conditions

- If you have a 3+ point line and points on either side of it, there is no solution.

- If you have more than one 3+ point line and they are not parallel or orthogonal, there is no solution.

- If you (only) have two parallel 3+ point lines and more than 4 remaining points there is no solution

[wanderingfool2]

12 minutes ago, Eigenvektor said:

True. As long as you have 3 or more points on the same line, they must be part of an edge. Otherwise it's not possible to construct a rectangle with them.

 

So thinking a bit, assuming you have no 3+ points in a line.

- Pick any two points and run a straight line L1 through them

- If you have points on both sides of that line, start over

- Pick the point furthest away from L1, run line L2 (parallel to L1) through it

- All the remaining points are between L1 and L2

- Run line L3 (orthogonal to L1/L2) through as many remaining points as possible

- You must now be able to run line L4 (parallel to L3) through the remaining points, otherwise this is not a solution and you need to start over with two different points

 

If you have three or more points on the same line, then there is no solution that doesn't include them as the "starting line", i.e. there must be a parallel line that goes through the point furthest away and there must be two orthogonal lines that can touch all of the remaining points. So if you have a 3+ point line and points on either side of it, there can be no solution either. If you have more than one 3+ point line and they are not parallel or orthogonal, there can be no solution.

Yea, my initial post went through a lot more details about the scenarios that can arise out of grabbing 5 points...because initially that's all you really need to inspect.  It keeps the computational time down to almost a fix maximum for the initial bit.

 

It's just if 3 of the point match in the 5, it makes it easier.

You are guaranteed to have at least 2 points match.  My post I was going to mention about running more dot products to find the points which are furthest and constructing the rectangle from those...but then it involves me doing the math to do intersections, which I didn't really feel like doing again.

 

I mean in the worst case scenario if you have > 8 points, you can use 8 points to determine the sides.  At 8 points you guaranteed to find at least 1 true side.  Since it boils down a scenario that each side has 2 points (but at that stage it would be solved) or if one side has 3 points it gets back to being able to tell one side being part of the rectangle.

[Electronics Wizardy]

@EigenvektorI think I though of a possible solution that would find if 4 points could form a rectangle. 

 

From my thinking any 4 points can form a rectangle if no three points can create a triangle with the 4th point inside it. Then just check the 4 possible triangles to see if the last point is in the triangle, and if the last point isn't in the triangle for all its a combination of points that form the perimeter of a rectangle. 

 

Please prove this wrong, I can't find a set of 4 points that can't create a rectangle where the 4th point won't be inside the triangle. I want to see an exception to this rule.

 

 

[Wictorian]

18 hours ago, Franck said:

If that is your data then your task is not doable unless you accept a random rectangle as a valid answer

the answer must be either True or False. If we can construct any rectangle or not.

[Wictorian]

18 hours ago, wanderingfool2 said:

I thought that might be what is being asked...either that or whether or not the points form an unique rectangle, which would also be answerable.

 

Actually even in the general case, you could create an expression regarding all valid rectangles.

 

I accidentally closed after I went through an initial guess on how to do things (probably inefficiently).  Let me ask this though to get clarification.

 

You have a set of points.  Are you to determine whether or not there exists an unique rectangle that fits all the points...or is the question, given a set of points determine if there exists a rectangle that have the points all along the edges

@Eigenvektor

The solution isn't a unique rectangle, it is simply True or False indicating if a rectangle is constructable using the given points. Infinite amount of valid rectangles dont create an obstacle.

[Wictorian]

18 hours ago, Eigenvektor said:

→

This complicates things a lot. I think you need to add additional constraints to make this solvable. E.g. "smallest rectangle whose edges touch all points". If, for example, you only have two given points then there's an infinite number of solutions, which essentially makes this unsolvable. Or if all of your points are on the same line.

 

I think I'd still do a first round with a variation of what I proposed above, because that will be much faster:

1. Merge identical points (i.e. keep only one instance)
2. If the number of remaining points is
   • n ≤ 2 → no solution/infinite solutions, abort
   • n = 3 → see below
   • n ≥ 4 → go to step 3
3. Sort points by their x-coordinate
4. Keep the one(s) with the x_min and x_max
   • If there is only one for both keep them as corners
   • If there is only one for either x_min or x_max, but multiple for the other, abort, no solution
   • Otherwise keep the ones with y_min and y_max as corners
5. Repeat steps 3 and 4 for the y-coordinate
6. You should be left with 4 distinct corners
   • Otherwise, no solution, abort
7. Select three corners at random
8. It must be possible to connect them in a way that forms a right angle
   • Otherwise, no solution, abort
9. Keep the two corners that are not the center of the right angle
10. They must form a right angle with the remaining corner, using it as the center point
11. The two corners and the two other points must have the same distance from one another

You should now have a rectangle. Make sure that all remaining points are neither outside nor inside the rectangle (i.e. all of them are on its edge). Would it find a solution to the points below? I don't think so…

 

If you can't find a solution with these steps, you'll have to go the much more computationally expensive route to find four parallel/orthogonal lines that include all of the points as @Sauron said. Not sure how to find an abort condition here where you can be certain that no solution can ever be found.

 

3 point solution:

• Select two points (p1, p2) at random.
• Connect them with a straight line.
  • If point p3 is on that line, abort, no solution/infinite solutions
• Send a parallel line through the third point
• Now connect the two lines with orthogonal lines, starting at the two points
• You now have one possible solution

 

This already has three possible solutions, depending on which two points you pick as a starting point. The more points you have the more possible solutions there are (and the higher the chance there is none)… Not sure there's an elegant solution for an arbitrary number of points that is solvable in finite time.

 

As I said corners don't have to be given so your solution only works in a minority of the cases. I am looking for a solution that works with 100% accuracy meaning it should always find the solution (in True or False format). I think this should be possible or the question itself is not solvable. Also please dont worry about computation as it is not the point and not many points will be given.

[Wictorian]

7 hours ago, Electronics Wizardy said:

@EigenvektorI think I though of a possible solution that would find if 4 points could form a rectangle. 

 

From my thinking any 4 points can form a rectangle if no three points can create a triangle with the 4th point inside it. Then just check the 4 possible triangles to see if the last point is in the triangle, and if the last point isn't in the triangle for all its a combination of points that form the perimeter of a rectangle. 

 

Please prove this wrong, I can't find a set of 4 points that can't create a rectangle where the 4th point won't be inside the triangle. I want to see an exception to this rule.

 

 

You are (most likely) correct if the points must be on the corners of the triangle. However how can we downscale the points to 4?