# Ordering the Boundary points of a Polygon

I feel like this should be simple, but I keep running into walls.

Say someone gives you the coordinates of the vertices of a pentagon and the center point of the hexagon. Is there any way to get an "ordered" list of the boundary points?

Let me try to put this in a picture. For instance, if someone gave me a list {+,m,\pi,[],2} plus the center point C, and I plot it and find

                   2

m              +
C

[]     \pi


Is there anyway I can extract the list:

{2,+,\pi,[],m} up to cyclic permutation? Ideally I would like to be able to differentiate orientations, clockwise vs counterclockwise, but I don't really care about cyclic permutation.

Thanks for any help in advance!

Big CRUCIAL edit:

Thanks everyone for your help, I have been trying lots of suggestions, but I let out a crucial element in all of this. My points are in 3D! It seems to me that all of these routines, ConvexHullMesh, FindCurvePath, etc. all work with 2D coordinates. I was thinking about trying to project onto a plane perpendicular to the central point, since I know the center, but that might be too lengthy.

Here are the points:

Center:

{0.951057,-0.309017,0.}


Neighbors:

{{0.723607, -0.525731, -0.447214}, {0.850651, 0., -0.525731}, {0.894427, 0., 0.447214},
{0.951057, 0.309017, 0.}, {0.587785, -0.809017, 0.}, {0.688191, -0.5, 0.525731}}

• – Michael E2 Aug 26 '14 at 14:41
• Thanks Michael E2! Both FindCurvePath and FindShortestTour seem to be on the right track. FindCurvePath seems a little better for my purpose because it ONLY outputs a list. However, I would still like to figure out if there is a way I can specify, or at least know, the orientation. – Tim Aug 26 '14 at 14:48
• Are all 3D points coplanar? Then projection is the way to go. – Yves Klett Aug 26 '14 at 16:58
• The 3D points are NOT coplanar. I have in mind triangulating a surface with curvature. – Tim Aug 26 '14 at 17:00
• No Problem! Here is an example of points that are giving me issues. Center: {0.951057,-0.309017,0.} Neighbors: {{0.723607, -0.525731, -0.447214}, {0.850651, 0., -0.525731}, {0.894427, 0., 0.447214}, {0.951057, 0.309017, 0.}, {0.587785, -0.809017, 0.}, {0.688191, -0.5, 0.525731}} – Tim Aug 26 '14 at 17:13

In version 10, you can use MeshCoordinates[ConvexHullMesh[...]] as in RunnyKine's answer, but you need to re-order them using MeshCells:

 pentagon=N@Table[{Cos[2 Pi k /5], Sin[2 Pi k /5]}, {k, 5}]
points = N@RandomSample[Join[pentagon, {{0, 0}}]]
chm=ConvexHullMesh[points];
ordering=MeshCells[chm,2][[1,1]]
out=MeshCoordinates[chm][[ordering]]
MemberQ[RotateRight[pentagon,#]&/@Range,out]
(* True *)

Row[{Graphics[Polygon[MeshCoordinates[chm]]],Graphics[Polygon[out]]}] Update: Additional ways to extract the ordered coordinates of chm:

out2 = Cases[Normal@chm["Graphics"], _Polygon, Infinity][[1,1]] (*Thanks: @Michael E2 *)
out2 == out
(* True *)

out3=chm["FaceCoordinates"][]
out3 == out
(* True *)

• Now that's unexpected, since chm draws a polygon. This also works: Cases[Normal@chm["Graphics"], _Polygon, Infinity]. (+1 btw. :) – Michael E2 Aug 26 '14 at 15:30
• @Michael, i too was surprised. It seems that it works like GraphicsComplex,.i.e., ConvexHullMesh gives the unordered vertex coordinates, and various cells are constructed using the indices of these vertices. – kglr Aug 26 '14 at 15:35
• Nice, I was just about to post the "FaceCoordinates" solution. – RunnyKine Aug 26 '14 at 16:09
• @RunnyKine, had to try a dozen of those chm["Properties"] to finally find one that worked:) – kglr Aug 26 '14 at 16:12
• Yeah, I did the same :) – RunnyKine Aug 26 '14 at 16:13

If you have Version 10, you could use ConvexHullMesh.

pts = RandomReal[{-10, 10}, {6, 2}];


You can then order them by doing:

chull = ConvexHullMesh[pts];


And here are the points:

MeshCoordinates[chull]


Note: This does not always order the points but one can use MeshCells which will give the ordering correctly. See @kguler's answer.

• We're going to have to start calling you the Mesh Master. ;) +1 – Michael E2 Aug 26 '14 at 15:11
• @MichaelE2 Thanks. I think I like that name :) – RunnyKine Aug 26 '14 at 15:13
• Thanks @RunnyKine! I originally tried using the ConvexHullMesh, but I couldn't find the function MeshCoordinates... Now my task is to try to figure out a way to differentiate orientations! – Tim Aug 26 '14 at 15:30
• Can we stop down-voting without giving reasons? That'll help a lot. Thanks – RunnyKine Aug 26 '14 at 15:34
• I agree, but hazarding a guess, the DV is probably because this doesn't always work. See kguler's answer. Seems courteous to point out the problem first, though. – Michael E2 Aug 26 '14 at 15:41

Could use ConvexHull in the ComputationalGeometry standard add-on package.

Needs["ComputationalGeometry"]


We'll create a simple example.

pts = RandomReal[{-10, 10}, {6, 2}];
ListPlot[Append[pts, First[pts]], Joined -> True] Now find and plot the (ordered) outer points.

hullindices = ConvexHull[pts];
hullpts = pts[[hullindices]];
ListPlot[Append[hullpts, First[hullpts]], Joined -> True] • Thanks @Daniel Lichtblau. It was the extraction, the pts part that I didn't know how to do! – Tim Aug 26 '14 at 15:31

The following works in your special case but can't be generalized.

l = {"+", "m", "π", "[]", "2"};
SeedRandom@0;
rl = RandomSample[l, 5];
g = With[{cg = CycleGraph},
VertexCoordinates -> (Rule @@@
VertexLabels -> "Name", ImagePadding -> 10]] Clockwise:

First /@ First@FindHamiltonianCycle@g

{"m", "[]", "+", "π", "2"}


Counterclockwise:

First /@ First@FindEulerianCycle@g

{"m", "2", "π", "+", "[]"}

• Ah, this is interesting since you are able to determine orientation. I don't see an obvious generalization, but I will play with this because I like where it is headed. – Tim Aug 26 '14 at 15:31
• @Tim It will always work if your Graph is a ring, if a vertex is inside the ring then Find*Cycle won't work. – Öskå Aug 26 '14 at 15:59

I found half an answer that works well except for the orientation part.

As several of you have hinted at the FindCurvePath function is on the right track, but it only works in two dimensions. My options are thus projecting/rotating any polygon to some canonical plane, or, more easily, using the FindShortestTour function which solves the "traveling salesman problem" in arbitrary dimension. Luckily, the shortest path that connects these points is the boundary path.

For example:

vectors={a,b,c,d,e};

points={{0.951057, -0.309017, 0.}, {0.525731, 0., 0.850651}, {0.951057, 0.309017, 0.}, {0.688191, 0.5, 0.525731}, {0.688191, -0.5, 0.525731}};

{a,b,c,d,e}[[FindShortestTour[points]// Flatten // Delete[#, {{1},{-1}] &]]`

Seems to be working for me!

Now, I just need to figure out orientation! This will probably involve using the center point.