# Dividing a rectangle into a grid of rectangles/squares

I'm writing a program where I need to divide a large rectangle into small pieces, no constraint on being exactly equally sized or exactly rectangle(they can be a square as well) and even if they protrude out of the larger rectangle a little, it'll be fine. I know how to divide a rectangle into some number of rectangles, but my current situation is making it difficult to visualize how many rectangles should I divide it into.

Let me explain the scenario - I've been given a large rectangle with n number of uniformly distributed points inside it and I've to make smaller rectangles so that each rectangle has ~10^3-10^4 points in it. The n can vary easily from 10^5 - 10^8 and even above. My idea is to cluster those points into smaller rectangles so that I don't have to compare all points linearly and just compare their bounding rectangles to the geometric figure. So in earlier case, I would be comparing millions of points for each geometric figure, now I would be comparing much much less number of bounding rectangles.

For now I've hardcoded the values eg. 1000 smaller rectangles for 10^6 number of points and like that for 10^7 and 10^8. But it has a disadvantage that instead of calculating for continuous range, I'm hard coding for discrete range which does not work for 5000000 number of points or any such in middle. Also, they are usually made into thin strips which makes them very hard to fall completely within the geometric shape I'm comparing with.

I hope I've explained it clearly, but I'll provide a TLDR;

Given a rectangle with n number of points uniformly distributed inside it, split that rectangle into smalle rectangles with 10^3-10^4 number of points in each of them.

Also, the naive solution like dividing into very slim strips does not work for me because then most strips only intersect with geometric figure rather than falling within it completely, it would be preferable for an algorithm/function to make somewhat both axis uniform boxes.

 ________                           ________
| | | | |   <-- slim strips         |   |   |   <-- much better
| | | | |                           |---|---|
|_|_|_|_|                           |___|___|


Let's say the large rectangle is $$W$$ by $$H$$, and contains $$n$$ points, uniformly distributed. Let $$k = \frac{n}{10^4}$$. Then you want to have $$k$$ rectangles of more or less equal area, and you want them to be as nearly square as possible (if I understand your complaint about "strips"). So let's say that the side of the square will be around $$s$$. Then there are $$W/s$$ squares along the horizontal side, and $$H/s$$ along the vertical, giving a total of $$\frac{WH}{s^2} = k$$. Hence $$s \approx \sqrt{ \frac{WH}{k} }$$.
To be sure you don't get too many points per square, I'd compute the value $$s$$ and then round it down a little. Alternatively, compute $$s$$ first, and look at $$a = W/s$$ and $$b = H/s$$, which might not be integers. Round up $$a$$ to an integer $$A$$, and round up $$b$$ to an integer $$B$$. Then use nearly-square rectangles of height $$H/B$$ and width $$W/A$$.