Reverse complex 2D lookup table

1. for f(x,y) you can use f(x,y)->(a,b) 2D LUT (Look Up Table)

   But the stored grid points must be selected so dense so that there is max one bump per grid rectangle, otherwise interpolation would not work correctly.

   If you want to use linear interpolation then the local min/max must be points inside LUT, for polynomial interpolation of higher order is this not always needed. I would use 4 point cubic interpolation

2. how to compute g(a,b)->(x,y)

   • first is reverse mapping possible?
   • so how many (x,y) points return the same (a,b)=f(x,y) ?
   • it is the same as question: Is f function or not?

   if f is not function then you got a problem and you can not solve this, unless somehow subdivide the range to sub ranges where f is function and then you will have to select the proper range according to some rules dependent on what are you trying to do. So let assume that f is function

   So how to compute (x,y)=g(a,b) that f(x,y)=(a,b)?

   1. I would start with approximation of the result. So try enough (x,y) values along the whole range and store the closest point to the desired output so that |f(x,y)-(a,b)| is minimal.

   2. Then start this again but not on full range but around this point instead

      • recursively increasing accuracy up to a point you need.
      • look here Increasing accuracy of solution of transcendental equation there I am computing similar problem have 1D LUT of 2D points (a(t),y(t)) and need the inverse 3D point (a0,y0,z0) You can use my approximation class there

Nesting of approximations is done like this:

int n=5;  // recursions
double e; // Error Of Solution Variable
approx ax,ay;
//            min    max   step   
for (ax.init(-100.0,+100.0,10.0,n,&e);!ax.done;ax.step())
for (ay.init(-100.0,+100.0,10.0,n,&e);!ay.done;ay.step())
    {
    e=|f(ax.a,ay.a)-(a,b)|;
    }
// here (ax.a,ay.a) should hold your solution for input point `(a,b)`

• initial step should be as small so there is no bump missed
• if your g(a,b) shape is too complex then this will probably not work properly

From this you can compute the inverse LUT table …

• Each recursion divides the step by 10 so choose n wisely.

For 2D and singular point is the performance of this not that bad O((log(N))^2). I am doing this on 3D O((log(N))^3) with 100 points per e computation and that is painfully slow (about 35 seconds)

• where N=(10^n)*(max-min)/step, and n is the number of recursions
• accuracy is step/(10^n)
• do not forget to change the min,max to your used ranges …