# Are the triangles in DelaunayMesh oriented ccw?

MeshCells[R, 2] returns the triangles from R=DelaunayMesh[pts], where pts is a list of 2D points. My (limited) experiments indicate the triangle vertices are listed in counterclockwise order, which is exactly what I need. But I cannot find in the documentation a statement that this is a guaranteed property of DelaunayMesh and MeshCells. Is it in fact guaranteed?

Of course I could reorient them if ccw is not guaranteed.

(I'm using Mathematica 10.4.0.0.)

• @user21 to the rescue? (user21 = resident expert on all things mesh). Commented May 21, 2016 at 19:54
• I don't think that it is guaranteed. Commented May 21, 2016 at 22:32

user21 says it isn't guaranteed that the vertices will be in counter-clockwise order, but I can't find a counter-example.

Using the method described here we can make a little function that tests a polygon for whether its vertices are CCW

ccwQ[list_List] :=
Positive@Total[Subtract @@@ (list RotateLeft[Reverse /@ list])]
ccwQ[poly_Polygon] := ccwQ@First@poly
ccwQ[mesh_MeshRegion] := And @@ (ccwQ /@ MeshPrimitives[mesh, 2])
ccwQ[mesh_BoundaryMeshRegion] :=
And @@ (ccwQ /@ MeshPrimitives[mesh, 2])


Check that it works,

ccwQ /@ {Polygon[{{0, 0}, {1, 0}, {0, 1}}],
Polygon[{{0, 0}, {0, 1}, {1, 0}}]}
(* {True, False} *)


And then apply it to 50 examples of random 800-point DelaunayMesh regions, verifying that every single triangle is CCW:

In[119]:= Table[ccwQ@DelaunayMesh[RandomReal[1, {800, 2}]], {50}]

Out[119]= {True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True}


This seems to be general for the MeshRegion objects. It works on VoronoiMesh:

ccwQ@VoronoiMesh[RandomReal[1, {8000, 2}]]
(* True *)


as well as DiscretizeRegion results:

DiscretizeRegion[
ImplicitRegion[x^3 - y^7 <= 1, {{x, -2, 2}, {y, -2, 2}}]]
ccwQ@%
ccwQ@DiscretizeRegion[Disk[]]


So I haven't looked at the underlying code to see if it is guaranteed to always be true, but it seems to always be true. Chime in if you can find a counter-example

• I also have tested ccw orientation on random examples (less thoroughly than you) without finding a counterexample. Commented May 25, 2016 at 10:01
• It would be interesting to know if the tetrahedra in a 3D Delaunay triangulation are also consistently oriented. Commented May 25, 2016 at 10:03
• @JosephO'Rourke - how would you define orientation for points in 3D? In order for the points in the polygons to have a CW or CCW orientation, you have to specify the side you are observing from, right? What would the analogous metric be for the tetrahedron points? Commented May 25, 2016 at 10:09
• @Jason, a usual convention is for the tetrahedron to have its face normals pointing away from its centroid. FWIW, Sign[Det[PadRight[{p1, p2, p3}, {Automatic, 3}, 1]]] == 1 is a relatively compact way to test if the points of a triangle are oriented anticlockwise. Commented May 25, 2016 at 12:38
• @JasonB: I would require that the volume determinant from $p_1,p_2,p_3,p_4$ in order is positive. This is the same as requiring the four face normals to point outward. Commented May 25, 2016 at 13:48