Snap one grid of points to a new grid

This is a good question for the DSP group. I could see myself asking it there, so don't hope for a complete solution from me!

You're resampling in 2D. Which is just like resampling in one dimension, only harder. So searching around for resampling information may be helpful, both for methods and for limitations on how good the result may be.

Is the data in rows and columns, or are each of the x, y points unique?

In other words, is there an x[1] that goes with y[1] through y[big], ditto x[2], etc.?

If so, then you resample everything horizontally, then resample everything vertically.

In either case, some 2D variable-step version of polyphase filtering is probably going to be your friend.

--

Tim Wescott 
Wescott Design Services 
http://www.wescottdesign.com

Treat it as a grayscale image (you didn't mention how wide Z is) and use a photographic resampling scheme (depends on whether you want to linearly interpolate, etc.) to up/down-convert to the desired "resolution"

?

Maybe I'm missing something here. When you say grid, you mean a grid with regular spacing, like increments of 10 or 20? That seems to be a rather simple task of dividing by the grid spacing, rounding and then multiplying by the grid spacing. If you are working with integers you add half the grid spacing before dividing and then just multiply. The integer truncation does the rounding job nicely.

I would write a program to do this. What languages are you familiar with? Forth is a good one and very easy to use because of it's interactivity. You get a command line that you can test each routine from as you write it.

Where is your data presently?

--

Rick

Oh, after reading Don's post I get it. You want the Z value to be adjusted to suit the new X,Y position after moving to the grid, right?

Don's solution might work pretty well.

--

Rick

I'd be more cautious than that. A lot depends on what "somewhat regularly spaced already" means as well as how sensitive the function (being "mapped") is to changes in x and y.

E.g., a potential data set:

(1,1,23) (2,1,18) (3,1,15) (0.9,1.99,8) (1.9,2.1,19) (2.9,1.05,16) (1.8,3.2,7) (2.1,2.8,25) (3.2,3.9,12)

I.e., the data aren't *exactly* aligned on a unit grid (my suggestion assumed they were "close enough" -- so the observed value of z didn't substantially differ from what it *would* have been "on the original, implied grid".

Mathematica *may* be able to do this. It can interpolate using predefined "interpolating functions" (linear, cubic, etc.) as well as allowing you to define your own (this assumes you know the sensitivity of the observed function in localized domains).

The caveat might be that you have to specify the function that you are interpolating as a list of x,y,z (instead of just z-values at an implicit REGULAR grid)

Simplest would be bilinear from nearest neighbours which implies sorting your data first by z,x,y to be efficient.

If your grid will be much coarser than your data sampling you might get away with summing all values that fall into a grid square and keeping a count of how many there were in each. It all depends on what you intend to do with the gridded data afterwards. The devil is in the detail.

The only caveat about treating it as an image interpolation problem is that if you intend to for example Fourier transform the gridded data later then you have to be very much more careful about how you interpolate your randomly sampled data to produce uniform coverage on a regular grid. Methods for doing this are published in the literature for aperture synthesis radio astronomy and MRI imaging.

--
Regards, 
Martin Brown

Exactly. Note, also, that the OP hasn't claimed the data were

*strictly* ON a grid to begin with. How tolerant the data is to tiny changes in x,y will indicate how readily *forcing* the data onto such a grid would work (without distorting the data before you've begun!)

Yes. (generic) Images are resampled with a different set of evaluation criteria. I offered the idea as a quickie way of seeing if the results would be what was desired (by the OP).

[without having to write a bit of code and *test* that code...]

If *my* problem, I'd explore Mathematica's capabilities more closely (delightful piece of code, that!)

you can't interpolate a point. what aren't you telling us?

you've got data, use a statistics package, or a database, or a general purpose programming language you are comfortable with.

--
umop apisdn 


--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

I agree. Although for bigger datasets IDL is also worth considering especially if you can get it on an academic license.

Such tools can be used for good or ill and I have seen some very good data turned into appalling incomprehensible infographics by it too!

--
Regards, 
Martin Brown

yes! but I use the free MatLab clone, octave. Have this problem ALL the time, but I don't snap to grid, I find the linearly interpolated value inside the x-y square and often change to a 'radial' format for special curve fitting.

However, can be a bit slow, so instead change code to C/C++ and that's a screamer.

LTspice has built-in ability to linearly interpolate all those pesky unevenly spaced .tran points into linear space.

Wow! Never thought of considering that, thanks! I see some 'fraught with perils' but still extremely interesting concept.

Matlab/Octave should work.

Cheers

Phil Hobbs

--
Dr Philip C D Hobbs 
Principal Consultant 
ElectroOptical Innovations LLC 
Optics, Electro-optics, Photonics, Analog Electronics 

160 North State Road #203 
Briarcliff Manor NY 10510 

hobbs at electrooptical dot net 
http://electrooptical.net

Not aware of that product. I've used MatLab, MathCAD and Mathematica in the past and "settled" on Mathematica.

The problem with all of them is they aren't particularly intuitive so, unless you use them "often", there is a start-up cost involved.

[I have learned to record command lines in my documentation so I can quickly get back a particular result -- without having to fumble around trying to remember syntax, optional arguments, etc.]

I don't think you understand his problem. He has three dimensional data which can be considered a surface. He wants to produce results where X and Y are on a grid of his choosing and the Z values are adjusted to fit the existing surface. Is that more clear?

I don't think the algorithm is all that simple depending, of course, on which algorithm he chooses. He has not indicated if this is a one time thing, likely because he considered doing it in Excel, or if he will have recurring sets of data to process. That makes a difference to the amount of optimization he might need.

--

Rick

I stumbled upon a program called Saga at SourceForge.

Looks good in several interesting ways - a possible keeper for future needs . As you say, like the rest, not particularly intuitive and comes with practi cally no documentation. But it's free.

For now, I think I've found a way to reduce the (row count) size of my orig inal dataset so that it will fit into Excel 2007. I'll still need to resam ple (snap) to my preferred grid, but at least I know how to do that in Exce l (or, at least I think I do.) Famous last words? :)

Thanks for the help and pointers, guys. I only have a couple of these sets to process, so assuming this first one i s the largest, I can probably mangle it fine from here.

What about finding the descriptive equation via curve fitting (least squares or some such)?

If he has some million data points, that equations would likely have an awful lot of terms... It could be accurate with not so many terms, but how accurate? It would be a lot of processing just to estimate the accuracy.

--

Rick

"Grid interpolation of scattered point data, triangulation, IDW, splines, ..."

Presumably, it lets you specify (x,y,z) instead of *implying* (x,y) for each z that you specify? ("scattered point data")

I'd *carefully* single out a portion of your raw data and "manually" work through what you *think* the output should be "in that vicinity" -- just so you aren't surprised if it applies some unexpected transform that manifests as an abnomaly in your data later in "analysis/processing".

This is a point-cloud description of a surface, which gives us a google search term.

Excel won't know what to do with a point cloud. There are programs that will take point cloud data and turn them into CAD descriptions.

Joe Gwinn