Poor delaunay triangulation output

I have an array of 2D coordinates which roughly follow a grid pattern. I am attempting to join these 'nodes' in the array to create quadrilaterals (or could work with triangles) from the coordinates.

I have attempting to use delaunay triangulation but the result is poor (as shown here: http://db.tt/VBn4iNmg) with many 'skinny' triangles near the top-left of the figure instead of the more regular triangles near the bottom-centre. I've attempted to use some of the qhull options to improve the output but I've not succeeded. Can you please help me with my conundrum?

Many thanks, David

Answer 1

[John D'Errico]

Since a delauny triangulation describes a convex domain ALWAYS, this is the expected behavior. If your data is not truly convex but close to it, then there will always be thin triangles near the edges. Sorry, but this is just the nature of the beast. A common fix for the problem is to use an alpha shape. For example...

[X,Y] = meshgrid(0:10);

Xe = X + randn(size(X))/10;
Ye = Y + randn(size(Y))/10;
XYe = [Xe(:),Ye(:)];

tri = delaunayn(XYe);
triplot(tri,XYe(:,1),XYe(:,2))

As you can see, the triangulation has thin triangles around the edges, but it is a convex dwomin that contains ALL of the points.

T = alphaShape(XYe,1);
plot(T)

Here we see a result that is NOT convex, but it lacks the thin triangles.

Note that alphaShape was introduced into MATLAB with release R2014b.