# Optimal binning

This topic is 2274 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello all,

I have a question for you:

I am looking for the optimum way (in terms of performance) to bin random points in (semiregular) rectangular areas on a plane:

To be precise I have some rectangular areas in the x,y plane and I have an array of many points (say million) on that plane that are placed in a specific way. What I want to do is to write an efficient function that it gives me which points are in each bin. You can see how the rectangular bins look at the following picture. The points will be distributed on that plane. One idea is to locate the bins in the beggining and in the middle by bisection but what about those rectangles in the right that are placed irregularly? Is there a fast and efficient solution to this problem? Any comment will help me.

[attachment=8442:binning.png]

Thank you.

##### Share on other sites
How are the rectangles generated?

##### Share on other sites
Nevermind.

PS: The 'delete post' seems seems to have gone missing.

##### Share on other sites
Thanks for the replies and the link.

The rectangles are not produced by any algorithm. They are produced manually based on some criteria.

So I guess that I have to partition the area 3 say 3 regions. In the first 2 regions I will use bisection to locate the bin and for the leftmost bin I will compare the point coordinates
with the boarders of the rectangles. How that's sound?

##### Share on other sites
I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

##### Share on other sites
Hmmm, right. Since there are not too many bins I could also use the first level of the tree (I don't even need to make a tree). I can partition the space in say 4 areas then look up where the point belongs and then use a different treatment for each area.

The disantvantage of this is that I have to make assumptions about the way the bins are placed...

##### Share on other sites
I don't know if you are responding to my post or to something else, but none of what I posted makes assumptions about how your bins are placed.

##### Share on other sites

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.
[/quote]

By fine grid you mean a grid of equal sized and equal spaced superimposed rectangles? -->

for example?

About the tree the point is that I don't want to create one for only 58 bins.

##### Share on other sites
If you want performance, use spatial subdivision. If you want to write simple code and not build a spatial subdivision mechanism of some variety, give up on performance.

That's not to say, of course, that the simplest brute-force algorithm will be "too slow." That depends a lot on how fast you really need this to be.

##### Share on other sites
Thanks,

Since I don't want to spend time making a quad - tree in Fortran (yes, I have to do it in Fortran ). I am going to use a fine grid as suggested or semi - manual partitioning.

1. 1
Rutin
19
2. 2
3. 3
JoeJ
16
4. 4
5. 5

• 26
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001782
×