[Solved]: Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

Problem Detail: 

I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid:

That is, using the image above, for each node in the Cartesian grid I would interpolate a value from the closest existing nodes (red).

Currently, my approach is to generate a kd-tree for the original solution nodes, then use a nearest-neighbor search to obtain the three closest nodes. I then use barycentric interpolation to obtain a value from these three points. The problem, however, is that my polar grid is much finer along the radial direction than it is in the azimuthal direction, which means that my nearest-neighbor search almost always selects points from the same radial. This has the result of creating "striations" in my new solution, instead of smoothly interpolating along the azimuthal direction (i.e., the results look no different than if I had simply mapped the nearest point to the "interpolated" point).

Unfortunately, I don't know how to achieve a better sampling without sacrificing the kd-tree and losing a lot of the speed improvements. Am I being thick-headed and missing an obvious solution? Or does anyone know a better way to approach this problem?

Asked By : vincentjs

Answered By : D.W.

I don't know if this has been studied by others. Speculating off the top of my head, let me outline two possible approaches.

Applying standard rectangular methods to polar coordinates

Here's one way to adapt more familiar interpolation methods (that work with Cartesian coordinates) to your setting. Let's start by looking at bilinear interpolation.

Let $P$ be the point on the Cartesian grid whose value you want to compute, using interpolation. Find the smallest "rectangle" of four nodes that surround the point $P$. A "rectangle" in polar coordinates is just like a rectangle in a Cartesian grid, except with up/down replaced with "inward"/"outward" and right/right replaced with "clockwise"/"counterclockwise". For instance, here is an example of a "rectangle" in a polar-coordinate grid:

This gives you 4 nodes that surround $P$. Finally, use these 4 nodes to interpolate and form the value for $P$. For instance, you could do bilinear interpolation, in the same way we do bilinear interpolation on a Cartesian grid, but now working with polar coordinates / barycentric coordinates.

This also makes clear how to generalize to other interpolation schemes, such as bicubic interpolation.

Ad-hoc method: supplement from adjacent radials

One possible approach you could try would be to pick the 3 closest nodes, then supplement them with a few other nodes from adjacent radials.

Let $P$ be your point. Start by picking the closest 3 nodes to $P$ (say). Then, supplement them. For instance, suppose all 3 nodes are on the radial $\theta$. Look at the radial just to the left of it, $\theta-\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$. Similarly, look at the radial just to the right of it, $\theta+\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.

Now use those points to interpolate. You might use weighted least-squares regression to fit a linear (or bilinear/bicubic/etc.) model, where the nodes that are closer to $P$ receive a higher weight. If you experiment a bit with the number of points chosen, the type of model, and the weights, you might find a scheme that reduces the "striation" artifacts.

Maybe better schemes are known; I don't know. I'm not expert in this area.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43744