Thread: Advice Grid Collection of Data

Hi guys,

I have a program which generates lots of data points in 2D (x and y co-ordinates). Perhaps 1,000,000+ of these points. These are floating point numbers. The values all fall within a specific range -R/2 and +R/2.

I want to impose an 'imaginary' grid. Such that I can collect the number of each of these points falling within a specific grid location. The actual 'grid' size is variable.

But I am just wondering if any of you experts had a strategy/plan of attack for me to do this in the most effective/efficient manner?? Or even should I try and collate this data from my C++ program and then post-process it in some other s/w like matlab?

Please advise.

cheers

Use a quadtree to attack this problem.

Quadtrees operate off of recursively subdividing space into squares and if you use a balanced one, you can create a uniform grid and from there find out where each point would lie. Keep in mind, most of these trees typically work by only having one point per leaf but in your case, it's okay to just draw the tree up first and then fill them with points.

Originally Posted by CodeMonkey

What is a specific grid location? Some region in your plane?

Yes.

When people talk about grids like these, it can be almost anything really just so long as it represents space. For example in 2D, you could create a grid of hexagons or triangles or squares or rectangles. This easily extends into any dimension and is the subject of a lot of computational geometry.

So in the OP, he was asking about an efficient method of finding out which elements of a grid the points would lie in. One of the most popular and well-known structures used for this is a quadtree in 2D and an octree in 3D.

But a much more efficient algorithm is to use a Peano-Hilbert curve to mimic the quadtree. You see, it's a type of fractal that fills all 2^n x 2^n space and you mimic the tree by dividing the curve into fourths and comparing where the points on the curve are.

So say the total length of the curve is 16 so each point can have an index from 0 to 15 and you mimic the tree by going, "Okay, how many points in between 0 and 3? How many between 4 and 7? How many between 8 and 11? How many between 12 and 15?" You can easily construct a tree from this.