Create triangular mesh from random list of points

Question

I have a list of points. I would like to take these points and create a mesh of triangles from them, making sure triangles don't overlap. So here's a list of points:

p0 = Transpose[{RandomReal[{0, 10}, {100}], RandomReal[{0, 12}, {100}]}];
ListPlot@p0

Now I've managed to take the first point in the list, find its two nearest neighbours and construct a triangle from this:

Graphics[{Thick, Red, Line[Append[Nearest[p0, p0[[1, All]], 3], p0[[1, All]]]]}]

What I'd not like to do is from this starting point keep connecting points to make a mesh where all the triangle corners are at one of the points and no triangles overlap. Any suggestions on how to do this?

--Below may be irrelevant--

I imagine DelaunayTriangulation might come into this, however I'm not sure how. Also when I run it I don't understand what it returns:

DelaunayTriangulation[p0] // MatrixForm

Answer 1

First, you can generate your random points like so:

SeedRandom[1];
pts = RandomReal[{0, 12}, {100, 2}];

The DelaunayTriangulation command returns an adjacency list representation of the triangulation.

Needs["ComputationalGeometry`"];
dt = DelaunayTriangulation[pts];
dt // Column

This says that the first point should be connected to the 2nd, the 24th, etc. Given {u, {v1,v2,v3,___}}, we need a toPairs function to form {{u,v1},{u,v2},{u,v3},___}. We then need to map toPairs onto the triangulation and Flatten that result one level. This is all accomplished as follows.

toPairs[{m_, ns_List}] := Map[{m, #} &, ns];
edges = Flatten[Map[toPairs, dt], 1];

Finally, we visualize using a GraphicsComplex.

Graphics[GraphicsComplex[pts, {Line[edges], 
  Red, PointSize[Large], Point[pts]}]]

Answer 2

There are some new functions in Mathematica 10 that make this very easy:

r = {{-6, 6}, {-6, 6}};
pts = RandomSample[Permutations[Range[-5, 5], {2}], 10];
Grid[{
  {"The sites", "Delaunay trianguation", "Voronoi diagram"},
  {
   Graphics[{Red, Point[pts]}, PlotRange -> r],
   Show[dm = DelaunayMesh[ pts], Graphics[{Red, Point[pts]}], 
   PlotRange -> r],
   Show[VoronoiMesh[ pts], Graphics[{Red, Point[pts]}], PlotRange -> r]
   }
  }, Frame -> All]

Head[dm]
MeshCoordinates[ dm ]
MeshCells[ dm , 2]
MeshCells[ dm , 2][[ All, 1]]

MeshRegion

{{-5., -4.}, {3., -4.}, {5., -2.}, {4., 0.}, {-4., -1.}, 
{-3., 2.}, {0., -1.}, {3., -5.}, {2., 4.}, {5., -5.}}

{Polygon[{5, 1, 7}], Polygon[{6, 7, 9}], Polygon[{7, 6, 5}], 
 Polygon[{9, 7, 4}], Polygon[{1, 8, 7}], Polygon[{8, 10, 2}], 
 Polygon[{2, 3, 4}], Polygon[{3, 2, 10}], Polygon[{2, 4, 7}], 
 Polygon[{8, 2, 7}]}

{{5, 1, 7}, {6, 7, 9}, {7, 6, 5}, {9, 7, 4}, {1, 8, 7}, {8, 10, 
  2}, {2, 3, 4}, {3, 2, 10}, {2, 4, 7}, {8, 2, 7}}

So you use DelaunayMesh to create a MeshRegion from the point set, and then you can use MeshCells as shown to get the triangles. MeshCells gives you triples of indexes into the MeshCoordinates.

I took the above code from Interactive Computational Geometry (disclaimer - I am the author).

Answer 3

It seems you are asking for the Delaunay triangulation.

There's a function for this in the Computational Geometry package, which Mark described.

Another, usually much faster option is using ListDensityPlot:

ldp = ListDensityPlot[ArrayPad[p0, {0, {0, 1}}], Mesh -> All, 
 ColorFunction -> (White &)]

You can extract the polygons from this graphic if needed.

Cases[ldp, Polygon[idx_] :> idx, Infinity]

This will return the triangles as point index triplets.

You can also use the undocumented function ListDensityPlot relies on, if you wish.