Need ideas to fill in missing grid points
11 views (last 30 days)
Show older comments
Hi,
I am wondering if anyone can point me to a matlab function (or user algorithm) to help me fill in missing points on a grid. What i have is a list of x,y locations for points which correspond to points on an (imperfect, but regular) grid -- e.g. (1.02,1.03), (2.04,0.98),(0.96,1.023), etc...
Many of the points are missing. I'd like to determine the "best fit" grid which describes the points that i have so that i can fill in the missing ones.
This is kind of like a curve fitting approach, but its for a grid.
I've thought of computing some kind of merit function and then running some kind of best-fit optimizer, but I'd like guaranteed convergence on something close.
picture of example imperfect grid is attached.
Also, I do NOT have Z data. I am only interested in identifying a set of uniform lattice points that "Best match" the XY locations of the samples that I do have.
THanks if you have anygood ideas!
1 Comment
Star Strider
on 31 Aug 2015
It might be helpful if you attach a .fig file of your plot. That contains all the (x,y) data, so it will be possible to test code with it.
Answers (4)
Star Strider
on 27 Aug 2015
MATLAB has a number of Interpolation functions. Probably the most appropriate in your application is Scattered Data Interpolation.
0 Comments
John D'Errico
on 27 Aug 2015
Edited: John D'Errico
on 27 Aug 2015
I'm a bit unsure if you have z values for each of those points or not. If each (x,y) pair has an associated z value, then you should use a code that is designed to do exactly this. Gridfit is on the file exchange for download. It will essentially fit a function of two variables (really, a simple 2-d spline), returning the fitted surface on that grid.
If you are only trying to find a grid itself, in the (x,y) plane, reducing this to a complete lattice of points, then you need to be more specific about your goals. I.e.,
1. Must the lattice fully span all of your points?
2. Must the lattice be a regular one, so uniform spacing?
2 Comments
John D'Errico
on 31 Aug 2015
If the lattice need not have the same spacing in both dimensions, then this is just a pair of independent 1-d problems, thus do it in x, then in y.
A lattice could be defined by the start and end points, and the number of steps between those points. The start and end points are bounded by the first and last point in that lattice. So the problem is a simple optimization in two variables. Assume the number of points in that lattice is known. Try to solve the problem with say n steps, then n+1, then n+2, etc. Take the best result.
Your objective function for the optimization is simple. Associate each data point with the nearest lattice line. Compute the distance to that lattice line, then square those distances and sum the squares over all points. (Note that these steps are all done trivially and efficiently in a vectorized form.)
Since the problem is a two variable one, fminsearch would solve it nicely, although since it is a bounded optimization, you will need to use my fminsearchbnd, as found for download from the file exchange. Alternatively, you could use tools from the optimization toolbox.
If the lattice spacing must be the same for both x and y, then the optimization would run over the start point in x, the start point in y, and the spacing, so essentially a 3 variable problem.
Image Analyst
on 31 Aug 2015
So you have an N-by-2 array where column 1 is the x coordinate and column 2 is the y coordinate. You mention you do not have Z data - what would that even be?
Anyway, if you know how many rows you have, even though they're slightly wiggly, and you know how many columns you have, then you can use kmeans() in the stats toolbox and get the mean x values for all the columns and mean y values for all the rows. So now you have your grid and it's a simple matter to pick a "missing" location and assign the estimated x and y location for that missing point.
Kelly Kearney
on 31 Aug 2015
This function might help you: colinear. I wrote it for exactly the same problem you're facing, to extract a grid based on a set of scattered points along each grid line, with a bit of error.
You may have to fiddle around with the rounding tolerance and angle-limit function. I found that with nearly-regular grids like this one, various diagonals tend to be more linear than the nearly-horizontal and nearly-vertical ones you really want to find.
5 Comments
Kelly Kearney
on 1 Sep 2015
New version now uploaded. A proper README with examples will be added tomorrow.
Kelly Kearney
on 1 Sep 2015
And now the README is up, with an example very similar to your problem. Hope it helps!
See Also
Categories
Find more on Interpolation in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!