Sign in to follow this  
Lord_Vader

Optimal binning

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Can you be a little more specific about this:

[quote]
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? -->

[img]http://img829.imageshack.us/img829/1974/finegrid.jpg[/img]
for example?

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

Share this post


Link to post
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 [i]of some variety[/i], 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 this post


Link to post
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 [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img] ). I am going to use a fine grid as suggested or semi - manual partitioning.

Share this post


Link to post
Share on other sites
[quote name='Lord_Vader' timestamp='1335196857' post='4934137']
By fine grid you mean a grid of equal sized and equal spaced superimposed rectangles?
[/quote]
Yes, except for the "superimposed" part. I am not sure what you mean by that, but your picture is correct. By "fine" I mean that you can make the resolution of the grid 200x100 instead of 8x4, and then most cells will only map to one or two rectangles.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this