9
$\begingroup$

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}} 
$\endgroup$
5
  • 2
    $\begingroup$ FindCurvePath? $\endgroup$
    – Michael E2
    Commented Aug 26, 2014 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 14:48
  • $\begingroup$ Are all 3D points coplanar? Then projection is the way to go. $\endgroup$
    – Yves Klett
    Commented Aug 26, 2014 at 16:58
  • $\begingroup$ The 3D points are NOT coplanar. I have in mind triangulating a surface with curvature. $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 17:00
  • $\begingroup$ 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}} $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 17:13

6 Answers 6

8
$\begingroup$

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

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.

$\endgroup$
8
  • 3
    $\begingroup$ We're going to have to start calling you the Mesh Master. ;) +1 $\endgroup$
    – Michael E2
    Commented Aug 26, 2014 at 15:11
  • $\begingroup$ @MichaelE2 Thanks. I think I like that name :) $\endgroup$
    – RunnyKine
    Commented Aug 26, 2014 at 15:13
  • $\begingroup$ 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! $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 15:30
  • 2
    $\begingroup$ Can we stop down-voting without giving reasons? That'll help a lot. Thanks $\endgroup$
    – RunnyKine
    Commented Aug 26, 2014 at 15:34
  • $\begingroup$ 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. $\endgroup$
    – Michael E2
    Commented Aug 26, 2014 at 15:41
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks @Daniel Lichtblau. It was the extraction, the pts part that I didn't know how to do! $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 15:31
1
$\begingroup$

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", "π", "+", "[]"}
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Tim
    Commented Aug 26, 2014 at 15:31
  • $\begingroup$ @Tim It will always work if your Graph is a ring, if a vertex is inside the ring then Find*Cycle won't work. $\endgroup$
    – Öskå
    Commented Aug 26, 2014 at 15:59
1
$\begingroup$

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_, 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]
$\endgroup$
0
$\begingroup$

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.

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