How to order points anti clockwise

Question

Lets take thess points.

pt={{-4.65371,0.1},{-4.68489,0.103169},{-4.78341,0.104834},{-4.83897,0.100757},
{-4.92102,0.0949725},{-4.93456,0.100181},{-4.89166,0.122666},{-4.78298,0.129514}, 
{-4.72723,0.121442},{-4.68355,0.11023},{-4.65371,0.1},{-4.66924,0.10173}, 
{-4.93059,0.0966989},{-4.93259,0.105094},{-4.91074,0.116966},{-4.90635,0.094878}, 
{-4.66846,0.105327},{-4.92647,0.0956182},{-4.93433,0.102498},{-4.9333,0.0982262},
{-4.66257,0.10102}};

Now they are in certain order (for me is a disorder!) which can be seen if we look at the ListLinePLot

picUnorder=ListLinePlot[pt,Frame-> True,Mesh-> All,MeshStyle-> PointSize[Large]];
SeepicUnorder=ListLinePlot[pt,Frame-> True,Mesh-> All,MeshStyle-> 
PointSize[Large]]/.Line[rest_]:>{Arrowheads[Table[0.02,{i,0,1,.02}]],Arrow[rest]};
GraphicsGrid[{{picUnorder,SeepicUnorder}}]

But we need to order them like the picture below.

Does anybody has some suggestion for a algorithm to sort such 2D points in counter clockwise direction so that we can rearrange the list of points to create a geometry like the last pic just by using ListLinePlot on the rearranged points????

Using the suggestion we get something like the following.

center=Mean[pt];
pts=SortBy[pt,Function[p,{x,y}=p-center;ArcTan[x,y]]];
Show[ListPlot[pt],ListLinePlot[pts,Mesh-> All,MeshStyle->
PointSize[Large]],Frame-> True]

BR

Answer 1

I've just read in a comment to nikie's answer that what you really want is the algorithm for an airfoil. So, I am posting another (unrelated) answer to this problem:

Seems easier than the general problem, because it is "almost convex". I think the following algorithm reduce the risks that FindShortestTour inherently has at the acute vertex:

1. Find the ConvexHull (that accounts for the upper and attack surfaces)
2. Remove from the set the points in the convex hull
3. Perform a FindShortestTour with the remaining points
4. Join both curves at the nearest endpoints
5. Voilà

Like this:

pt1 = Union@pt;
<< ComputationalGeometry`
convexhull = ConvexHull[pt1, AllPoints -> True];
pt2 = pt1[[convexhull]];
pt3 = Complement[pt1, pt2];
pt4 = pt3[[(FindShortestTour@pt3)[[2]]]];
If[Norm[Last@pt4 - First@pt2] > Norm[Last@pt4 - Last@pt2], pt4 = Reverse@pt4];
pt5 = Join[pt4, pt2, {pt4[[1]]}];
Graphics[{Arrowheads[.02], Arrow@Partition[pt5, 2, 1], 
          Red, PointSize[Medium], Point@pt1}]

Answer 2

Why don't you just sort the points?:

center = Mean[pt];
pts = SortBy[pt, Function[p, {x, y} = p - center; ArcTan[x, y]]]
Show[ListPlot[pt], ListPlot[pts, Joined -> True]]

Note that the polygon in your last plot is concave, so the points are not ordered clockwise!

Answer 3

Maybe you could do something with FindShortestTour. For example

ptsorted = pt[[FindShortestTour[pt][[2]]]];
ListPlot[ptsorted, Joined -> True, Frame -> True, PlotMarkers -> Automatic]

produces something like

Answer 4

I posted the following comment below your question: I don't think you'll find a general solution. This answer tries to dig a little on that.

Heike's solution seems fair, but FindShortestTour is based on the metric properties of the set, while your requirement is probably more on the topological side.

Here is a comparison on two points sets and the methods available to FindShortestTour:

pl[method_, k_] :=
  Module[{ptsorted, pt,s},
   little[x_] := {{1, 0}, {2, 1}, {1, 2}, {0, 1}}/x - (1/x) + 2;
   pt = Join[{{0, 0}, {4, 4}, {4, 0}, {0, 4}}, little[k]];
   ptsorted = Join[s = pt[[FindShortestTour[pt,Method->method][[2]]]], {s[[1]]}];
   ListPlot[ptsorted, Joined -> True, Frame -> True, 
                      PlotMarkers -> Automatic, 
                      PlotRange -> {{-1, 5}, {-1, 5}}, 
                      Axes -> False, AspectRatio -> 1, PlotLabel -> method]];
GraphicsGrid@
 Table[pl[i, j],
       {i, {"AllTours", "CCA", "Greedy", "GreedyCycle", 
            "IntegerLinearProgramming", "OrOpt", "OrZweig", "RemoveCrossings",
            "SpaceFillingCurve", "SimulatedAnnealing", "TwoOpt"}}, 
       {j, {1, 1.8}}]

     Fat Star         Slim Star

As you can see, several methods deliver the expected result on the left column, while only one does it on the right one. Moreover, the only useful method for the set on the right is completely off for the column on the left.

Answer 5

Here's a python function which orders points counterclockwise. It Graham's Scan theorem. I've written it because I misunderstood a homework. It needs optimizing,though.

def order(a):
from math import atan2
arctangents=[]
arctangentsandpoints=[]
arctangentsoriginalsandpoints=[]
arctangentoriginals=[]
centerx=0
centery=0
sortedlist=[]
firstpoint=[]
k=len(a)
for i in a:
    x,y=i[0],i[1]
    centerx+=float(x)/float(k)
    centery+=float(y)/float(k)
for i in a:
    x,y=i[0],i[1]
    arctangentsandpoints+=[[i,atan2(y-centery,x-centerx)]]
    arctangents+=[atan2(y-centery,x-centerx)]
    arctangentsoriginalsandpoints+=[[i,atan2(y,x)]]
    arctangentoriginals+=[atan2(y,x)]
arctangents=sorted(arctangents)
arctangentoriginals=sorted(arctangentoriginals)
for i in arctangents:
    for c in arctangentsandpoints:
        if i==c[1]:
            sortedlist+=[c[0]]
for i in arctangentsoriginalsandpoints:
    if arctangentoriginals[0]==i[1]:
        firstpoint=i[0]
z=sortedlist.index(firstpoint)
m=sortedlist[:z]
sortedlist=sortedlist[z:]
sortedlist.extend(m)
return sortedlist