Determine if given points form a rectangle

[Wictorian]

1 minute ago, Wictorian said:

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?

Actually this doesn't work on 3 point lines. 

[tikker]

22 hours ago, Wictorian said:

Also for instace 4 points in the same line can be given.

2 minutes ago, Wictorian said:

Actually this doesn't work on 3 point lines. 

 If points lie on a line then the answer is yes, since they are the simply one of the four sides in that case.

 

For 1, 2 and 3 points the answer is simply yes I think:

• One point can be part of anything, so naturally a rectangle is possible.
• Two points form a line and can thus by nature be part of a rectangle.
• Three points form a triangle. If you draw a line from the apex perpendicular to the base you have the length of the two sides perpendicular to the base. The apex then forms one of the corners of the rectangle if it reaches beyond the base, or is in between two corners if it's within the base (in a parallel fashion) giving the two sides parallel to the base, of which the base is part.

For four points you can check if they form a line or, if not, exploit some relation between the corners of a rectangle and its centre of mass, for example, as mentioned in the first reply's edit, to calculate it directly.

 

Not a solution, but you can thus somewhat focus the problem to determining if 5 or more points can form a rectangle.

[Electronics Wizardy]

58 minutes ago, Wictorian said:

Actually this doesn't work on 3 point lines. 

Should work fine for lines, as there won't be a point inside the triangle, it would be on the line. Only allow points that are inside the triangle to fail it. Then 3 and 4 points in a line would still work.

 

 

[Wictorian]

1 hour ago, Electronics Wizardy said:

Should work fine for lines, as there won't be a point inside the triangle, it would be on the line. Only allow points that are inside the triangle to fail it. Then 3 and 4 points in a line would still work.

 

 

Then ok, it works. However, how can we downscale the points to 4? What comes to my mind is similar to what @Sauron suggested. We can find all the combinations of 4 points and apply this rule to all of the combinations. If each combination is valid, then a rectangle is possible. Actually I think this will work, no?

[Electronics Wizardy]

1 hour ago, Wictorian said:

Then ok, it works. However, how can we downscale the points to 4? What comes to my mind is similar to what @Sauron suggested. We can find all the combinations of 4 points and apply this rule to all of the combinations. If each combination is valid, then a rectangle is possible. Actually I think this will work, no?

Can you just try any combination of 4 points in the list of points you have? Then you will have a list of the possible combinations of 4 points that can form a rectangle.

[Eigenvektor]

3 hours ago, Wictorian said:

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.

My last post, based on what @Sauron and @wanderingfool2 said, should be the generic solution, if you have at least 3 points. For n < 3 the answer is always true.

 

11 hours ago, Electronics Wizardy said:

@Eigenvektor 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.

I would go so far as to say: Any 3 points on the edge of any convex shape will either form a line (same edge) or form a triangle that can never contain any other point of the shape's hull. If it contains another point, the shape must be concave.

 

The triangle formed by any 3 edges of a rectangle will always be a right angled triangle that halves the rectangle. The fourth point will be on the opposite side of the right angle's center point and will have the same distance from the triangle's hypotenuse.

[Wictorian]

3 hours ago, Electronics Wizardy said:

Can you just try any combination of 4 points in the list of points you have? Then you will have a list of the possible combinations of 4 points that can form a rectangle.

But the question is if all of the points combined can form a triangle. However I think what I suggested should work.

[wanderingfool2]

On 6/30/2022 at 10:14 PM, Electronics Wizardy said:

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.

haha, I totally forgot to factor in if the 4'th point is inside a triangle.  You are correct, any 4 points where it's outside should be able to form infinite rectangles.

 

9 hours ago, Wictorian said:

But the question is if all of the points combined can form a triangle. However I think what I suggested should work.

So can I ask this...do you know if there is a maximum amount of points for this?  Or is it just more of a generalized thing, where the # could be from 5 - 1 billion billion

 

Or if this is help for a particular homework assignment, do you need a solution that runs within a reasonable amount of time for larger data sets?

 

Just would like to know where you are getting stuck on or need more insight into.

 

I mean if I were implementing this, I would still do it where you push through 5 points initially to do an analysis on, as still with 5 points you can determine 5 potential lines of a rectangle.

 

One trick that you can use, if there is a line that's defined by points A B (m = (Ay - By)/(Ax - Bx), Ab = y - m*Ax)...from there, you can use "C" to find "b" using m and compare b's to determine if the point is "above" or "below" the line.   Do the same for C,D,E...if they all exist above line AB then it's a potential line.  If there exists a point C where it's positive, and D where it's negative (the below/above) then you know line CD doesn't exist, and line AB doesn't exist.  As it would create a geometry impossible with a rectangle.

 

That's how I would narrow down the 10 potential lines from 5 points down to 5 potential lines.  From there it's just about checking the 5 potential lines  (using a method mentioned in previous post...about finding the extreme points for each point...as you know that those must exist in a rectangle...so you can slowly eliminate the 5 remaining down to a final rectangle..or rather potential rectangles).  From there you can just add in more points and check if it's on a line.

 

# Very psudocody and not full of all logic needed I think (or not fully flushed out logic)
# no way efficient
# wrote this as quickly as possible so will have flaws and would need fixes in logic and slight math tweaks likely

point

isrectangle(points):
	# to lazy to deal with 4, so lets assume 5 points and above
    # code here for dealing with 4
    potentiallines, truelines = 5pointHelper(points[0:4])
    
    From here, you could do a few things.  Check all potentiallines against all points...at which point you will hopefully get a true line (if above 5 points)
    You can also continue on like the rest of the algo...for a true line, find the most extreme points in point (using dot product)..and grabbing one that produces the highest and lowest result (that isn't on the line).
    from there, that means you have can build 3 out of the 4 walls.  Then check the points along the lines
    
5pointHelper(points):
	for start_index in range(0,4): #permutations
    	for index in range(start_index+1,5):
        	lines.append(points(start_index), points(index)
            
     for line in lines:
     	rtn = validline(line, points)
     	if rtn == 1
        	potentiallines.append line
        elif rtn == 2
        	trueline.append line
            
     # if having a true line that's good

validline(line, points):
	direct_match = 0
	direction = 0 # unknown direction at the moment
	for point in points:
    	pt_dir = abovebelow(line, point)
        if direct_match >= 3:
        	return 2
        if pt_dir == 0: # on same line could be same point though that formed the line
        	direct_match++
        	continue
        if direction == 0:
        	direction = direction
        elif direction * pt_dir < 0: # we know we just switched negative to positive or positive to negative
        	return 0
    if direct_match >= 3:
    	return 2 # 2 means this line exists, as 3 points matched it
    return 1 # survived this long that means this line is consistent with the points (not a guarantee that it's a line, but at least the points given don't give a simple contradiction.

abovebelow(line, point):
	if line_m == 0: # special case
    	return point_x - line_b # or should this be reversed?  Can't bother to think it through.  It's this or b - x
        
    return (point_y - line_m * point_x) - b # should this be revsered?  again, not bothering

getline(point_a, point_b):
	if bx == ax:
    	m = 0, b = ax # special case
        return
	# math here for m, b calculation
    m = (by - ay) / (bx - ax)
    b = (ay - m * ax) # standard equation.  I mean I could be wrong here as in my forumla might have flipped some stuff...but writing this as quickly as possible

 

[Wictorian]

11 hours ago, wanderingfool2 said:

haha, I totally forgot to factor in if the 4'th point is inside a triangle.  You are correct, any 4 points where it's outside should be able to form infinite rectangles.

 

So can I ask this...do you know if there is a maximum amount of points for this?  Or is it just more of a generalized thing, where the # could be from 5 - 1 billion billion

 

Or if this is help for a particular homework assignment, do you need a solution that runs within a reasonable amount of time for larger data sets?

 

Just would like to know where you are getting stuck on or need more insight into.

 

I mean if I were implementing this, I would still do it where you push through 5 points initially to do an analysis on, as still with 5 points you can determine 5 potential lines of a rectangle.

 

One trick that you can use, if there is a line that's defined by points A B (m = (Ay - By)/(Ax - Bx), Ab = y - m*Ax)...from there, you can use "C" to find "b" using m and compare b's to determine if the point is "above" or "below" the line.   Do the same for C,D,E...if they all exist above line AB then it's a potential line.  If there exists a point C where it's positive, and D where it's negative (the below/above) then you know line CD doesn't exist, and line AB doesn't exist.  As it would create a geometry impossible with a rectangle.

 

That's how I would narrow down the 10 potential lines from 5 points down to 5 potential lines.  From there it's just about checking the 5 potential lines  (using a method mentioned in previous post...about finding the extreme points for each point...as you know that those must exist in a rectangle...so you can slowly eliminate the 5 remaining down to a final rectangle..or rather potential rectangles).  From there you can just add in more points and check if it's on a line.

 

# Very psudocody and not full of all logic needed I think (or not fully flushed out logic)
# no way efficient
# wrote this as quickly as possible so will have flaws and would need fixes in logic and slight math tweaks likely

point

isrectangle(points):
	# to lazy to deal with 4, so lets assume 5 points and above
    # code here for dealing with 4
    potentiallines, truelines = 5pointHelper(points[0:4])
    
    From here, you could do a few things.  Check all potentiallines against all points...at which point you will hopefully get a true line (if above 5 points)
    You can also continue on like the rest of the algo...for a true line, find the most extreme points in point (using dot product)..and grabbing one that produces the highest and lowest result (that isn't on the line).
    from there, that means you have can build 3 out of the 4 walls.  Then check the points along the lines
    
5pointHelper(points):
	for start_index in range(0,4): #permutations
    	for index in range(start_index+1,5):
        	lines.append(points(start_index), points(index)
            
     for line in lines:
     	rtn = validline(line, points)
     	if rtn == 1
        	potentiallines.append line
        elif rtn == 2
        	trueline.append line
            
     # if having a true line that's good

validline(line, points):
	direct_match = 0
	direction = 0 # unknown direction at the moment
	for point in points:
    	pt_dir = abovebelow(line, point)
        if direct_match >= 3:
        	return 2
        if pt_dir == 0: # on same line could be same point though that formed the line
        	direct_match++
        	continue
        if direction == 0:
        	direction = direction
        elif direction * pt_dir < 0: # we know we just switched negative to positive or positive to negative
        	return 0
    if direct_match >= 3:
    	return 2 # 2 means this line exists, as 3 points matched it
    return 1 # survived this long that means this line is consistent with the points (not a guarantee that it's a line, but at least the points given don't give a simple contradiction.

abovebelow(line, point):
	if line_m == 0: # special case
    	return point_x - line_b # or should this be reversed?  Can't bother to think it through.  It's this or b - x
        
    return (point_y - line_m * point_x) - b # should this be revsered?  again, not bothering

getline(point_a, point_b):
	if bx == ax:
    	m = 0, b = ax # special case
        return
	# math here for m, b calculation
    m = (by - ay) / (bx - ax)
    b = (ay - m * ax) # standard equation.  I mean I could be wrong here as in my forumla might have flipped some stuff...but writing this as quickly as possible

 

this is not for an assignment or anything, just a problem I am trying to solve. Thus thus doesnt have a real world application and we dont have to worry about the runtime. Also I think your way is more complicated than what I suggested.

[wanderingfool2]

11 hours ago, Wictorian said:

this is not for an assignment or anything, just a problem I am trying to solve. Thus thus doesnt have a real world application and we dont have to worry about the runtime. Also I think your way is more complicated than what I suggested.

haha, yea if was  for homework then I would be mentioning the "easiest" to follow solution would likely get you a less than stellar grade.

 

I mean, the easiest solution is just running through all the combinations of lines.  It's a very O(n^2) kind of thing...so for datasets of lets say a 10 might not seem like much, but then by the time you hit 100 data set size you could be getting quite large.  Although then again, when you do find a line with more than 3 points on it, you can effectively eliminate all points that are on that line...so the dataset becomes smaller

 

e.g. 5 points, there are 10 combinations of lines that could be created

10 points, there are 45 combinations

100 points, there are 4950 combinations

1000 points, 499500 combinations

 

The biggest thing though, do you know do you know how many points you will have?  Or specifically, do you know the minimum amount of points you could have?  I mean if you have a minimum of 8 unique points that could be on a rectangle, it actually can simplify things a lot (because you can create a custom function that will tell you exactly where 1 line is, and potentially up to 4 lines exact)...and by having 1 line exact you can easily run a method to identify the rest

 

[Wictorian]

4 hours ago, wanderingfool2 said:

haha, yea if was  for homework then I would be mentioning the "easiest" to follow solution would likely get you a less than stellar grade.

 

I mean, the easiest solution is just running through all the combinations of lines.  It's a very O(n^2) kind of thing...so for datasets of lets say a 10 might not seem like much, but then by the time you hit 100 data set size you could be getting quite large.  Although then again, when you do find a line with more than 3 points on it, you can effectively eliminate all points that are on that line...so the dataset becomes smaller

 

e.g. 5 points, there are 10 combinations of lines that could be created

10 points, there are 45 combinations

100 points, there are 4950 combinations

1000 points, 499500 combinations

 

The biggest thing though, do you know do you know how many points you will have?  Or specifically, do you know the minimum amount of points you could have?  I mean if you have a minimum of 8 unique points that could be on a rectangle, it actually can simplify things a lot (because you can create a custom function that will tell you exactly where 1 line is, and potentially up to 4 lines exact)...and by having 1 line exact you can easily run a method to identify the rest

 

It is really not an issue .. 

 

Minimum is 1 points, there is no maximum. 

 

By the way what I am talking about is finding all combinations of 4 POINTS and see if we can make a triangle with 3 of them and 4th point in the triangle. If none of the combinations can make such a triangle, then I conclude the points can construct a rectangle.  This reasoning is not faulty is it?

[Gimmick21]

2 hours ago, Wictorian said:

 If none of the combinations can make such a triangle, then I conclude the points can construct a rectangle.  This reasoning is not faulty is it?

You sure about that?

 

Edit:

An Idea:

Build the convex hull of all points.

1. If there are points inside the hull -> no rectangle

2. if the hull includes all points on the line -> reduce hull to corners

2.1.

If the hull has more than 8 corners -> no rectangle

If: Point count of hull <=3 -> true

if: 3 < Point count of hull < 8 -> use each edge-line of the polygon as an edge-line start for a rectangle and construct the bounding rectangle, each point has to be on the border of the rectangle

 

[wanderingfool2]

11 hours ago, Gimmick21 said:

You sure about that?

Should be true.

Quickly drew it so obviously it doesn't have exact right angles but you can get the rough approx of how to generate a rectangle using the 3 points

 

13 hours ago, Wictorian said:

It is really not an issue .. 

 

Minimum is 1 points, there is no maximum. 

 

By the way what I am talking about is finding all combinations of 4 POINTS and see if we can make a triangle with 3 of them and 4th point in the triangle. If none of the combinations can make such a triangle, then I conclude the points can construct a rectangle.  This reasoning is not faulty is it?

Can't think of anything wrong with that logic (not giving 100% thought though).   *edit thought about it more and no it wouldn't work

 

It leads back to efficiency though.  If you make all triangles possible...and test each point to see if it's in a triangle assuming you have a rectangle you will have the following amount of triangles formed (formula points choose 3)

5 points - 10 triangles, each triangle requires checking with 5 points = 50 ops

10 points - 120 triangles, 10 checks each = 1200 ops

100 points - 161700 triangles, 100 checks = 1,670,000 ops

1000 points - 166167000 triangles and 166,167,000,000 ops

 

So if you have lets say 1000 points, and it's a rectangle you would have to do at least 100 billion operations to determine that it's truly a rectangle...if you do a combination of building a triangle and seeing if the 4th point is in the triangle.

 

[Gimmick21]

54 minutes ago, wanderingfool2 said:

Should be true.

 

 

Number of operations can be reduced drastically with convex hull for lots of points, It think. After that the triangle idea can be aplied for the reduced number of points.

[wanderingfool2]

7 hours ago, wanderingfool2 said:

Can't think of anything wrong with that logic (not giving 100% thought though).   *edit thought about it more and no it wouldn't work

So I did give it more thought, and no it wouldn't work.  It only works for 4 points and less

 

Consider a circle, grab 9 points anywhere on that circle.  None of them will have a triangle, with a point inside, yet clearly it won't be able to make a rectangle.

 

It gets back to my algo again.  Form line segments and check whether or not it's on the left/right side of the line.  You have 5 potential lines, just check if the points line up with any of those 5...if they do then you know it must be in the rectangle...from there check for continuity with the remaining points.

[mariushm]

I'd start by sorting the points based on x, y coordinates ... i want the first point I work with to be the left most point and top most point. 

Then going to the right, find the first point with x higher than the point's x coordinates, and y coordinates bigger or smaller... basically find the point that's furthest away to the right  

As an example in picture below there's 2 points A and B As a rectangle must have 90 degrees corners, you can therefore determine the angle (red) and from there you can figure out the other angle (orange) and you can determine all the points between A and B and all the points on the yellow line, and all the points on the equivalent yellow line starting from B down and so on.

Also, you can probably do some quick tests ... for example if there's a B higher on y axis than A's y then you have rectangle angled like in the picture, so if there's a point with x coordinates <= than x coordinate of A and y less than A's y coordinate, that point won't be in a rectangle, so right away it's a fail.

Can't write it in words but should also look into circles, treat AB as the radius of a circle, there's probably some tricks that you can use  to figure out the points on the yellow line (since it's 90 degrees, you can probably just use cos instead of sin or something like that, my trigonometry is a bit rough these days) and the points on the line starting down from B are just the points from a plus an x,y offset because of the 90 degree angles. Same for the points between a potential CD line (parallel with the AB line)

 

 

 

 

[Franck]

Have you thought this might actually be a XY problem ?

 

Also this is a rectangle :

 

[Eigenvektor]

17 hours ago, wanderingfool2 said:

Consider a circle, grab 9 points anywhere on that circle.  None of them will have a triangle, with a point inside, yet clearly it won't be able to make a rectangle.

As I said above, this should be true for any convex shape (triangle, rectangle, pentagon, hexagon, ..., circle). If you select three random points on their edge, they will always form either a line or a triangle that contains no other points.

 

I guess I should've added that this means that you cannot use this test to determine whether you have a rectangle or not, because the relationships is 1:n, not 1:1. You can only infer the inverse: if this condition is false, it cannot possibly be a rectangle. But if it is true, it could still be any other kind of non-concave shape.

[Wictorian]

12 hours ago, mariushm said:

I'd start by sorting the points based on x, y coordinates ... i want the first point I work with to be the left most point and top most point. 

Then going to the right, find the first point with x higher than the point's x coordinates, and y coordinates bigger or smaller... basically find the point that's furthest away to the right  

As an example in picture below there's 2 points A and B As a rectangle must have 90 degrees corners, you can therefore determine the angle (red) and from there you can figure out the other angle (orange) and you can determine all the points between A and B and all the points on the yellow line, and all the points on the equivalent yellow line starting from B down and so on.

Also, you can probably do some quick tests ... for example if there's a B higher on y axis than A's y then you have rectangle angled like in the picture, so if there's a point with x coordinates <= than x coordinate of A and y less than A's y coordinate, that point won't be in a rectangle, so right away it's a fail.

Can't write it in words but should also look into circles, treat AB as the radius of a circle, there's probably some tricks that you can use  to figure out the points on the yellow line (since it's 90 degrees, you can probably just use cos instead of sin or something like that, my trigonometry is a bit rough these days) and the points on the line starting down from B are just the points from a plus an x,y offset because of the 90 degree angles. Same for the points between a potential CD line (parallel with the AB line)

 

 

 

 

what if all the points have the same x?

[Wictorian]

10 hours ago, Franck said:

Have you thought this might actually be a XY problem ?

No.