A random distribution of points lies on a map.
This data lies behind an API, and I want to grab the complete set of points within a given bounding box.
I can query the API with the bounding box and the API will return the set of points that fall within that box.
The problem is that the API will limit the result set to 10 items, with no pagination and no indication if there are more points that have been omitted.
So I made a recursive algorithm that takes a bounding box and requests the points that lie within it. If the result set is exactly 10 items, then I split the bounding box into four quadrants and recurse.
It works fine but my question is this: if want to minimize the number of API calls, what is the optimal way to split the bounding box?
Splitting it into quadrants was just an arbitrary decision. When there are a lot of points on the map, I have to drill down many levels before I start getting meaningful results. So I imagine it might be faster to split the box into, say, 9, 16, or more sections. But if I do that, then I eventually get to a point where a lot of requests are returning 0 results which isn’t so efficient.
Also, does the size of the limit on the results set affect the answer?
(This is all assuming that I have no prior knowledge of nominal point density in the bounding box)
0
How you divide the bounding box is a matter of optimizing API calls. Break it into quadrants and you risk to have to subdivide those further for not being small enough. Break it into grid and you risk to make superfluous API calls when quadrants would do.
Ideally you’d want to break it into a number of boxes that divides the number of points into 10 points each. However, the problem with 10 is that you cannot know if there are more points, so we’ll have to settle with 9.
Statistics approach
At this point, the deciding factor is determined by statistics. Statistically, what are the chances that an area will have exactly 9 points contained within? I’m guessing this is easily determined by your current zoom. If you are zoomed out, you’re likely not going to get only 9 points in quadrant. In order to eliminate this variable, stick with physical measurements (miles, kilometers, etc.) since they are not going to change with zoom. You’ll have to simply do the extra work of calculating the physical measurements from your current zoom (number of points in an area defined by width*height = number of points / kilometer^2 * width * height).
Now the tricky part is obtaining these statistics. This is largely determined by how your application works. If the users provide these points, then it is entirely variable and you’ll have to keep a running tally of number of points / kilometer^2. If these points are static, then you can do some optimization within your program.
Given the average density (number of points / kilometer^2) and the standard deviation, you can aim for one standard deviation from 9, and you will have an 84% (68% + 16% tail for being more than one standard deviation towards zero) chance of having all your points fall between 9 and 0. Once you know the maximum density from this calculation, the height and width will be the inverse of the maximum density multiplied by 9 minus the standard deviation.
I realize this is sort of a technical answer, but it would optimize. However also consider that a map isn’t uniformly distributed, so it would be optimal only if the distribution is consistent with the rest of the map. It may not work well for say, a city.
Alternative approach
An alternative approach if you have static point data could be to simply perform monte-carlo simulations, starting with subdividing into 2×2 squares and then moving to 3×3, 4×4, et cetera. Count the number of total API calls and pick the one requiring the least. Hope that helps!
2
I would choose one coordinate (x/y) and find dividing line that divides returned points to two parts, ideally 5/5.
This way you don’t call api extremely lot of time if there are dots clustered really close to corner of your original rectangle.
Another thing, if you have some good heuristic for density, you could skip calls for large rectangles and start with small enough so there is only small chance that they will be empty or contain lot more than 10 points.
eg. if you suspect cluster in top left corner and maybe few points in the rest, you could ask for 3 rectangles, one with cluster (and expect to recurse down) one under (or on side of it) and the rest.
1
I do not think that there is much you can do about it. If you know the point density, you could break down the quadrants accordingly.
If the points do not change you could cache them, so initially you would have a relatively high amount of calls to the API which will eventually minimize itself as your application matures.