# Getting ordered coordinates out of ConvexHullRegion

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


The older ComputationalGeometryConvexHull function works correctly:

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


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.

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


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


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

• 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?). Apr 21, 2016 at 23:15
• @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.
– kglr
Apr 21, 2016 at 23:19
• @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"]
– kglr
Apr 21, 2016 at 23:26
• When I copy you code I find a some parenthesis out of sync also added a more efficient way then FindPath Apr 21, 2016 at 23:41
• Hi, kglr. ConvexHullMesh does not have properties like "BoundaryVertices" at least in 13.2. So this answer needs an update. Jul 9, 2023 at 10:02

Assuming the goal is to create the graphics:

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


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


• 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. Apr 21, 2016 at 23:12
• @ZachB, added a more efficient version. Apr 21, 2016 at 23:39
• Thanks, wish I could select multiple answers. +1'ed. Apr 22, 2016 at 0:14
• @ZachB, no worries, I am no a hunter-gatherer any longer ;-) Apr 22, 2016 at 0:27
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]}]


• Another good answer, thanks! Apr 22, 2016 at 0:13
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.

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


gives