Asked by Scott Sycamore
on 15 Apr 2019

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 by Matt J
on 15 Apr 2019

I think you are looking for griddata().

Scott Sycamore
on 15 Apr 2019

Sign in to comment.

Answer by John D'Errico
on 15 Apr 2019

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
on 15 Apr 2019

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.