CODEWITHSUNDEEP
sortingwolfram-mathematica
PlatoManiac
PlatoManiac

Reputation: 1442

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

Upvotes: 11

Views: 7258

Answers (5)

Khrotan
Khrotan

Reputation: 1

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

Upvotes: -1

Dr. belisarius
Dr. belisarius

Reputation: 61056

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:

enter image description here

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

enter image description here

Upvotes: 4

Dr. belisarius
Dr. belisarius

Reputation: 61056

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.

Upvotes: 11

Heike
Heike

Reputation: 24440

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

Upvotes: 10

Niki
Niki

Reputation: 15868

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!

Upvotes: 9

Related Questions