I have 2d points (x, y) with float coordinates, when I draw them, I need to group the points if they are close to each other, and they should be grouped using a fixed-size rectangle. And the problem is that these rectangles should not intersect, and all neighboring points should be grouped. If you have paper nearby, you can draw a large rectangle, for example 4 * 5 cm - the area where all the points are located. Now we randomly set points, and, say, if there are points whose distance is 1 cm, they should be grouped into a 2 * 3 rectangle.
I can’t find an algorithm how to do this, and performance is important too ... I was looking for nesting, clustering, but what I need is a little different. And by the way, if some grouping rectangles must be outside the general area in order to meet the conditions, even so, this is not a problem. For example. you have a 4 * 5 area and points
(1,0), (2,1), (4,1), (4,3), (2,4)
then the result should look like rectangles (0,0 - 3,2) & (3,1 - 6,3) and one point left (2,4) , because all the other points were grouped, and this point now has no neighbors . The coordinates of my points are not whole, but they are floating, and the number of points can be several hundred (up to 500). And I don’t want to divide the area into the same rectangles and just count how many points there are, I mean, for example, above that I could make callbacks (0,0 - 3,2), (3,0 - 6,2), (3,3 - 3,6), (3,3 - 6,6) and just sum the points 2 for the first rectangle, 1 (!) For the second, which means leaving it as it is, 1 for third and 1 for the 4th => one straight line will be drawn, and all other points => the wrong result in accordance with the task. Any ideas? At least what algorithms can be useful, where to look ...
PS while the number of groups / points as a result does not matter, ei other acceptable results, for example, higher, can be (1,0-4,2) and (2,2-5,4) rectangles, and the remaining points