13
$\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$

5 Answers 5

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$
6
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 23:41
  • 1
    $\begingroup$ Hi, kglr. ConvexHullMesh does not have properties like "BoundaryVertices" at least in 13.2. So this answer needs an update. $\endgroup$
    – matheorem
    Jul 9, 2023 at 10:02
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$
4
  • $\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, 2016 at 23:12
  • $\begingroup$ @ZachB, added a more efficient version. $\endgroup$
    – user21
    Apr 21, 2016 at 23:39
  • 1
    $\begingroup$ Thanks, wish I could select multiple answers. +1'ed. $\endgroup$
    – ZachB
    Apr 22, 2016 at 0:14
  • 1
    $\begingroup$ @ZachB, no worries, I am no a hunter-gatherer any longer ;-) $\endgroup$
    – user21
    Apr 22, 2016 at 0:27
7
$\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$
1
  • $\begingroup$ Another good answer, thanks! $\endgroup$
    – ZachB
    Apr 22, 2016 at 0:13
6
$\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$
2
$\begingroup$

using ConvexHullRegion

d = RandomReal[{0, 1}, {20, 2}];
ConvexHullRegion[d]
First@ConvexHullRegion[d]

gives

enter image description here

$\endgroup$

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.