Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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}} 
share|improve this question
2  
FindCurvePath? –  Michael E2 Aug 26 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 at 14:48
    
Are all 3D points coplanar? Then projection is the way to go. –  Yves Klett Aug 26 at 16:58
    
The 3D points are NOT coplanar. I have in mind triangulating a surface with curvature. –  Tim Aug 26 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 at 17:13

5 Answers 5

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

enter image description here

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 *)
share|improve this answer
    
Now that's unexpected, since chm draws a polygon. This also works: Cases[Normal@chm["Graphics"], _Polygon, Infinity]. (+1 btw. :) –  Michael E2 Aug 26 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. –  kguler Aug 26 at 15:35
    
Nice, I was just about to post the "FaceCoordinates" solution. –  RunnyKine Aug 26 at 16:09
    
@RunnyKine, had to try a dozen of those chm["Properties"] to finally find one that worked:) –  kguler Aug 26 at 16:12
    
Yeah, I did the same :) –  RunnyKine Aug 26 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.

share|improve this answer
2  
We're going to have to start calling you the Mesh Master. ;) +1 –  Michael E2 Aug 26 at 15:11
    
@MichaelE2 Thanks. I think I like that name :) –  RunnyKine Aug 26 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 at 15:30
1  
Can we stop down-voting without giving reasons? That'll help a lot. Thanks –  RunnyKine Aug 26 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 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]

enter image description here

Now find and plot the (ordered) outer points.

hullindices = ConvexHull[pts];
hullpts = pts[[hullindices]];
ListPlot[Append[hullpts, First[hullpts]], Joined -> True]

enter image description here

share|improve this answer
    
Thanks @Daniel Lichtblau. It was the extraction, the pts part that I didn't know how to do! –  Tim Aug 26 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[5]}, 
  Graph[UndirectedEdge @@@ Thread@{rl, RotateLeft@rl}, 
    VertexCoordinates -> (Rule @@@ 
     Thread@{rl, VertexCoordinates /. AbsoluteOptions[cg, VertexCoordinates]}),
    VertexLabels -> "Name", ImagePadding -> 10]]

Mathematica graphics

Clockwise:

First /@ First@FindHamiltonianCycle@g
{"m", "[]", "+", "π", "2"}

Counterclockwise:

First /@ First@FindEulerianCycle@g
{"m", "2", "π", "+", "[]"}
share|improve this answer
    
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 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.