Extract rectangular grid from triangulation

I have a noisy set of 2D points that are known to be on a nearly rectangular grid (with some warping). I am trying to determine the connecting vertices for the likely grid (may be missing/additional points). I think what I am trying to do is "quadrangulate" a triangulation. Perhaps my question can be better illustrated by the following code:

% Create original grid
x = 100*linspace(0, 1, 10);
[X, Y] = meshgrid(x, x);
% Add noise and generate npts-by-2 matrix
X = X + randn(size(X));
Y = Y + randn(size(Y));
P = [X(:) Y(:)];
% Triangulate noisy data
DT = delaunayTriangulation(P);
%%
% Some algorithm to produce 10-by-10 matrix of indices I into P
% where P(I, 1) == X(:)
% and P(I, 2) == Y(:)
%%
figure 
triplot(DT)
hold on
% Plot desired resulting mesh
surf(X,Y,0*X,...
  'facecolor','none',...
  'edgecolor','r',...
  'LineWidth', 2)
view(2)

Answer 1

[Matt J]

I think you are looking for griddata().

[Scott Sycamore]

No. Assume I have only P from the above code. I want to find out a "rectangular adjancy matrix" similar to what delaunayTriangulation does for a triangular adjancy matrix.

Answer 2

[John D'Errico]

The simple answer is to just round the points to a lattice. That is, just assign each point to the nearest lattice point. Since a regular lattice already has the connectivitty you seem to be looking for, you would then be done.

The problems that could arise are either noise that is too large, or missing data. Since you don't say what is to be done with this lattice, I have no idea what you might want to do with those missing points that fail to be filled in. You might use interpolation techniques, even my own inpaint_nans tool, found on the File Exchange. But you don't say that any values are associated with each point or not. So interpolation has no meaning unless there is a values assigned to each data point too, and all you have said is the phrase 2-D.

In the case of seriously large noise, where it becomes ambiguous where a point would be rounded to, I think you are in trouble. You might try some fuzzy logic, in the sense that you consider the probability that any point belongs in any node of the lattice, while not allowing two points to inhabit the same node of that lattice. Then find the assignment that maximizes the overall resulting likelihood function. A reasonable search tool for this problem might be GA. It will take some work to do, but it should be doable.

[Scott Sycamore]

Thank you, John. The application is in stereo vision with some projected structured light (dots in a rectangular pattern). I can identify the vertices (dots) in each camera image, but I then need to correlate the detected vertices between the two before I can then triangulate to get the real-world 3D positions. Your suggestion of using GA with some fuzzy logic is worth exploration. I was hoping that someone had already investigated this and could hand me a perfect out-of-the-box solution. Now, back to the real world.