Ordering the Boundary points of a Polygon

Question

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

Answer 1

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[5],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"][[1]]
out3 == out
(* True *)

Answer 2

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.

Answer 3

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]

Answer 4

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[5]}, 
  Graph[UndirectedEdge @@@ Thread@{rl, RotateLeft@rl}, 
    VertexCoordinates -> (Rule @@@ 
     Thread@{rl, VertexCoordinates /. AbsoluteOptions[cg, VertexCoordinates]}),
    VertexLabels -> "Name", ImagePadding -> 10]]

Clockwise:

First /@ First@FindHamiltonianCycle@g

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

Counterclockwise:

First /@ First@FindEulerianCycle@g

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

Answer 5

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.

Answer 6

Another way to do it for 3D polygons is by looking at the normal of the polygon. For 2D, you would have to add a third coordinate (like zero for all of them) in order for this to work.

Here are the steps:

1. The function takes in a list of 3D points representing the 3D polygon vertices.
2. Decide if you want clockwise or counterclockwise.
3. Compute the normal of the polygon using three of its points and the cross product (provided they are all co-planar).
4. Project the 3D points to a 2D plane by omitting the coordinate axis that aligns most closely with the normal vector.
5. Compute the centroid of the projected points while calculating the angle of each point relative to the centroid.
6. Sort the original 3D points based on these angles.

Here is the code:

ClearAll[OrderPointsClockwise3D];

OrderPointsClockwise3D[pts_List, clockwise_: True] := Module[
  {normal, plane, projectedPts, centroid, angles, sortedPts},

  (* Compute the normal of the polygon using the cross product *)
  normal = Cross[pts[[2]] - pts[[1]], pts[[3]] - pts[[1]]];
  
  (* Project points to 2D plane by omitting the dimension with the largest magnitude in the normal *)
  plane = Ordering[Abs[normal], -1][[1]];
  projectedPts = Delete[#, plane] & /@ pts;
  
  (* Compute centroid of the projected points *)
  centroid = Mean[projectedPts];
  
  (* Compute angles of each point relative to centroid *)
  angles = ArcTan[#[[1]] - centroid[[1]], #[[2]] - centroid[[2]]] & /@ projectedPts;
  
  (* Sort the 3D points based on the angles *)
  sortedPts = pts[[Ordering[angles]]];
  
  If[clockwise, Reverse[sortedPts], sortedPts]
]

(* Example usage *)
pts3D = {{0, 0, 0}, {1, 0, 0}, {1, 1, 1}, {0, 1, 1}};
OrderedPts = OrderPointsClockwise3D[pts3D]

(* To get them in counterclockwise order *)
OrderedPtsCCW = OrderPointsClockwise3D[pts3D, False]