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

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

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
10
  • $\begingroup$ I also have tested ccw orientation on random examples (less thoroughly than you) without finding a counterexample. $\endgroup$
    – Joseph O'Rourke
    Commented May 25, 2016 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
    Commented May 25, 2016 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.
    Commented May 25, 2016 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.'s missing motivation ♦
    Commented May 25, 2016 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
    Commented May 25, 2016 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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