9
$\begingroup$

I'm trying to get the ordered coordinates of a convex hull using MeshCoordnates[ConvexHullMesh[data]], but the coordinates are uselessly out of order:

With[{d = RandomReal[{0, 1}, {20, 2}]},
 ListPlot[
  d,
  AspectRatio -> 1,
  Epilog -> Polygon[MeshCoordinates[ConvexHullMesh[d]]]
  ]
 ]

enter image description here

The older ComputationalGeometry`ConvexHull function works correctly:

Needs["ComputationalGeometry`"]
With[{d = RandomReal[{0, 1}, {20, 2}]},
 ListPlot[
  d,
  AspectRatio -> 1,
  Epilog -> {Opacity[0.2], Polygon[d[[ConvexHull[d]]]]}
  ]
 ]

enter image description here

Is there some way to get the ordered coordinates from ConvexHullMesh?

Edit: I need to manipulate the polygon; the goal is not to just display the graphics.

$\endgroup$
9
$\begingroup$

For graphing, my preferred approach is posted already by user21.

To get the ordered coordinates you can reorder MeshCoordinates[ConvexHullMesh[d] using FindCurvePath:

With[{d = RandomReal[{0, 1}, {20, 2}]}, mc=MeshCoordinates[ConvexHullMesh[d]];
ListPlot[ d, AspectRatio -> 1, Prolog -> {Yellow,Polygon[mc[[FindCurvePath[mc][[1]]]]]}]]

Mathematica graphics

An alternative way to get the ordering of the coordinates is to use the "BoundaryVertices" property of ConvexHullMesh[d]:

ConvexHullMesh[d]["BoundaryVertices"]

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

which is a rotated version of

FindCurvePath[MeshCoordinates[ConvexHullMesh[d]]][[1]]

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

And, the property "Coordinates" can be used instead of MeshCoordinates; so

#["Coordinates"][[#["BoundaryVertices"][[1]]]]&@ConvexHullMesh[d]

gives the ordered coordinates.

d = RandomReal[{0, 1}, {20, 2}];
chcoords=#["Coordinates"][[#["BoundaryVertices"][[1]]]]&@ConvexHullMesh[d];
ListPlot[ d, AspectRatio -> 1, Prolog -> {Yellow,Polygon[chcoords]}]

Mathematica graphics

Yet another way to get the ordered coordinates is to get the "GraphicsComplex" property and extract

Cases[Normal@ConvexHullMesh[d]["GraphicsComplex"],Polygon[x_]:>x,Infinity][[1]]
$\endgroup$
  • $\begingroup$ Thanks, didn't know about FindCurvePath. I wonder if the ComputationalGeometryPackage uses that internally, or if it has a more direct and efficient approach (assuming FindCurvePath is somewhat expensive?). $\endgroup$ – ZachB Apr 21 '16 at 23:15
  • $\begingroup$ @ZachB, Thank you for the accept. I am not familiar with the ComputationalGeometry package, but we should be able to see the code for ConvexHull function. $\endgroup$ – kglr Apr 21 '16 at 23:19
  • 1
    $\begingroup$ @ZachB, you can see the code for ConvexHull using nb = NotebookOpen[ ToFileName[{$InstallationDirectory, "AddOns", "Packages", "ComputationalGeometry"}, "ComputationalGeometry.m"]]; NotebookFind[nb, "compute 2D convex hull using Graham's scan \ algorithm"] $\endgroup$ – kglr Apr 21 '16 at 23:26
  • $\begingroup$ When I copy you code I find a some parenthesis out of sync also added a more efficient way then FindPath $\endgroup$ – user21 Apr 21 '16 at 23:41
  • $\begingroup$ @user21, thank you; i added the missing {. $\endgroup$ – kglr Apr 21 '16 at 23:56
8
$\begingroup$

Assuming the goal is to create the graphics:

With[{d = RandomReal[{0, 1}, {20, 2}]},
 Show[ListPlot[d, AspectRatio -> 1], ConvexHullMesh[d]]]

enter image description here

And here is a more efficient version than FindPath:

With[{d = RandomReal[{0, 1}, {20, 2}]}, 
 ListPlot[d, AspectRatio -> 1, 
  Epilog -> 
     GraphicsComplex[
      MeshCoordinates[#], {Opacity[0.2], MeshCells[#, {2, All}]}] &[
   ConvexHullMesh[d]]]]

enter image description here

$\endgroup$
  • $\begingroup$ Sorry, just clarified in question -- I actually need the points that comprise the polygon so I can manipulate the hull, so the goal is not (immediately) to create the graphics. $\endgroup$ – ZachB Apr 21 '16 at 23:12
  • $\begingroup$ @ZachB, added a more efficient version. $\endgroup$ – user21 Apr 21 '16 at 23:39
  • $\begingroup$ Thanks, wish I could select multiple answers. +1'ed. $\endgroup$ – ZachB Apr 22 '16 at 0:14
  • 1
    $\begingroup$ @ZachB, no worries, I am no a hunter-gatherer any longer ;-) $\endgroup$ – user21 Apr 22 '16 at 0:27
6
$\begingroup$
d = RandomReal[{0, 1}, {20, 2}];
hull = ConvexHullMesh[d];

The ordering can be obtained directly using MeshCells:

MeshCells[hull, 2]
(* {Polygon[{2, 6, 5, 4, 3, 1}]} *)

So:

points = MeshCoordinates[hull];
order = MeshCells[hull, 2][[1, 1]];
Graphics[{Yellow, Polygon[points[[order]]], Black, Point[d]}]

enter image description here

$\endgroup$
  • $\begingroup$ Another good answer, thanks! $\endgroup$ – ZachB Apr 22 '16 at 0:13
5
$\begingroup$
pts = RandomReal[1, {20, 2}];
mesh = ConvexHullMesh[pts]

You can simple use MeshPrimitives.

MeshPrimitives[mesh, 2]
(* {Polygon[{{0.135494, 0.556868}, {0.147549, 0.121726}, 
             {0.423421, 0.0565637}, {0.894244, 0.172512}, 
             {0.917483, 0.413526}, {0.911708, 0.8986}, 
             {0.708881, 0.866828}, {0.272797, 0.654125}}]} *)

A 2D convex hull mesh will consist of a single Polygon. Coordinates are easy to extract from there.

MeshCells does the same, but uses point indices instead of point coordinates.

$\endgroup$

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.