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.
Optimal binning
Author
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?
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?
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.
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.
Author
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...
The disantvantage of this is that I have to make assumptions about the way the bins are placed...
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.
Author
Can you be a little more specific about this:
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.
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.
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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
