Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to order points anti clockwise

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

enter image description here

But we need to order them like the picture below.

enter image description here

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]

enter image description here

BR

like image 574
PlatoManiac Avatar asked Oct 06 '11 11:10

PlatoManiac


People also ask

How do you read anti-clockwise?

Clockwise, involves a turn to the right as it follows the hands of a clock and anti-clockwise involves a turn to the left, against the direction of a clock's hands.

Is counter clockwise in or out?

If something is moving counterclockwise, it is moving in the opposite direction to the direction in which the hands of a clock move. Rotate the head clockwise and counterclockwise.

How do you tell which way is clockwise?

Which way is clockwise? Clockwise involves a turn to the right as it follows the hands of a clock. Think about an analogue clock. Starting from the top, a hand moving clockwise would move to the right-hand side.


2 Answers

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

enter image description here

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.

like image 120
Dr. belisarius Avatar answered Sep 18 '22 12:09

Dr. belisarius


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

plot of shortest tour

like image 40
Heike Avatar answered Sep 17 '22 12:09

Heike