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.
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!
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.
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).
dots is a 2d array of vectors, each with x,y – you’ve done that
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.
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.
refactor your click, mouseover, and rendering loops to loop over dots and check their neighbors
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.