How to check if 4 lines make a rectangle?

I’ve been tring to make the game Connect the dots and now I have a question. What is the easiest or the right way to check when four dots are connected and are making a rectangle.

Here is a link to my implementation so far: https://editor.p5js.org/misho_0501/sketches/0we1QgL1c

2 Likes

Maybe you could create a two-dimensional boolean Array, and every time the user creates a new line you set the values responsible for the dots to true.
Edit:
Just realised you can not store the directions of the lines that way. Maybe create an int array, or a three dimensional boolean array if that’s even possible? Not a very elegant solution though.

are you checking for axis-aligned rectangles, or ANY rectangles (including ones at a 45 degree angle)? do you know anything about the order of the points you are checking? are your rectangles defined using pixel unit points as integers, or are they created through floating point numbers?

there are a number of interesting general solutions.

the one that checks equality of four points from the centerpoint is pretty clever!

boolean isRectangle(double x1, double y1,
                 double x2, double y2,
                 double x3, double y3,
                 double x4, double y4)
{
  double cx,cy;
  double dd1,dd2,dd3,dd4;

  cx=(x1+x2+x3+x4)/4;
  cy=(y1+y2+y3+y4)/4;

  dd1=sqr(cx-x1)+sqr(cy-y1);
  dd2=sqr(cx-x2)+sqr(cy-y2);
  dd3=sqr(cx-x3)+sqr(cy-y3);
  dd4=sqr(cx-x4)+sqr(cy-y4);
  return dd1==dd2 && dd1==dd3 && dd1==dd4;
}
2 Likes

I know the order of the points, it is saved in 2-dimential array. The points are set using integers and doesn’t have a floating value. I’m checking for every rectangle that is part of a grid, so no 45 degree rectangles. Thanks for this answer that you have provided, I’ll check if this is a good solution for my problem and write again.

If you know the order and they are integers, the problem is much easier. Many of the solutions are complex because the point order is unknown.

Now that I understand your game demo a bit better, I see that you aren’t really testing points or lines, but a grid of edges.

Do you want to detect rectangles of any size?

._._._._.
|_._._._|

or just four closest points with single lines?

._.
|_|

Also – should this detect one large rectangle, or two small rectangles, or three rectangles?

._._.
|_|_|

Only one rectangle that is 4 points connected and it should be considered two separate rectangles.

Okay, the good new is that this is one of the easiest possible rectangle detection cases – however you aren’t storing your line data in an efficient way, either for checking clicks, or for drawing lines, or for detecting rectangles / quads, or for advanced features (like moving your dots and having your lines move, or laying out your dots in other configs like hex, et cetera).

  1. dots is a 2d array of vectors, each with x,y – you’ve done that
  2. get rid of lines[]. since you only care about edges on a grid, just add properties to each dot, dot.right=false and dot.down=false, marking each edge.
  3. in order to efficiently draw lines or check for collisions, you need three dots – the current dot, and its right / down neighbors – if they exist (they don’t always). while looping through dots, before you do anything, get the neighbors.
  4. refactor your click, mouseover, and rendering loops to loop over dots and check their neighbors
  5. draw an enclosed grid unit (rect/square/quad) if (adot.right && adot.down && rightdot.down && downdot.right). Because of how you store the edge properties, finding four edges that make a square is easy.

One of the interesting things about this approach is that it is robust for any point layout. So, if you random-walk your points over time, or drew them on an angle, or with perspective distortion, or in 3d on a rippling flag…the click detect and line drawing and square drawing algorithms will all still work correctly – they only care that there is a mesh of neighbors. It is even robust against missing dots in the grid if you wanted a non-rectangular outline, or to punch holes out of it. To make it work with something other than a rectangular mesh, though, you would need to change the data format.

1 Like