Algorithm for two-dimensional rebinning

Question

I have a 12-by-50 array that needs rebinning. The array represents a bivariate probability distribution, p(a,b), where a and b are non-Cartesian coordinates. However, I want to rebin it so that I have a distribution in Cartesian coordinates, p(x,y).

a and b are (mildly) nonlinearly related to x and y, however I make the simplifying assumption that (a,b) bins look like convex quadilaterals (crooked boxes!) in (x,y) space. I can make look-up tables relating (a,b) to (x,y) at all bin corners.

Anyone know of an algorithm that does this rebinning, to save me from reinventing the wheel?

I'm especially looking for analytical solutions, but will go for solutions involving chopping up (a,b) bins into many mini-bins and sorting these in the proper (x,y) bin according to their center position.

Please note that this is a rebinning task, not just an interpolation (which would be a piece of cake).

Answer 1

There are two general categories of solutions you can try. One is an exact analytic approach: figure out the exact fractional area f of bin (a,b) that overlaps bin (x,y), then just sum up the f*p(a,b) for all overlapping a and b for that bin to get p(x,y). (If the a,b bins are not all the same size, you should instead find the actual area and divide by the area of the (x,y) bin.) If the equations for the boundaries of the bins are simple enough, this should be relatively straightforward, if a bit tedious.

The other category is anti-aliasing, the same method that is used in computer graphics. Basically, you replace the entire bin at (a,b) with a bunch of equally spaced points, and drop those points into the x,y plane and add them to the bin that contains that value. So, for example, with anti-aliasing of 4, you would imagine an array of points (a+3/8,b+3/8), (a+1/8,b+3/8), (a-1/8,b+3/8), ... that each contained 1/16th of the value of the (a,b) bin; you'd then find where each of those 16 locations fell on the x,y plane and would add that 1/16th value to each bin.

(Stochastic solutions exist as well, but for your problem they will introduce larger errors and take longer to compute.)