5
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ @user21 to the rescue? (user21 = resident expert on all things mesh). $\endgroup$ – Yves Klett May 21 '16 at 19:54
  • 3
    $\begingroup$ I don't think that it is guaranteed. $\endgroup$ – user21 May 21 '16 at 22:32
3
$\begingroup$

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[]]

Mathematica graphics

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

$\endgroup$
  • $\begingroup$ I also have tested ccw orientation on random examples (less thoroughly than you) without finding a counterexample. $\endgroup$ – Joseph O'Rourke May 25 '16 at 10:01
  • $\begingroup$ It would be interesting to know if the tetrahedra in a 3D Delaunay triangulation are also consistently oriented. $\endgroup$ – Joseph O'Rourke May 25 '16 at 10:03
  • $\begingroup$ @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? $\endgroup$ – Jason B. May 25 '16 at 10:09
  • $\begingroup$ @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. $\endgroup$ – J. M. will be back soon May 25 '16 at 12:38
  • $\begingroup$ @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. $\endgroup$ – Joseph O'Rourke May 25 '16 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.