Jak zamówić punkty przeciwnie do ruchu wskazówek zegara

Question

Pozwala wziąć punkty.

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

Teraz są w określonej kolejności (dla mnie jest chorobą!), Które mogą być widoczne, jeśli spojrzymy na 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}}] 

Ale musimy zamówić je jak zdjęcie poniżej.

Czy ktoś ma jakieś sugestie dla algorytmu sortowania takich 2D punkty w kierunku przeciwnym do ruchu wskazówek zegara tak, że możemy zmienić listę punktów, aby utworzyć geometrię jak ostatni pic tylko za pomocą ListLinePlot po przegrupowaniu zwrotnica????

Korzystając z sugestii otrzymujemy coś takiego.

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

Właśnie przeczytałem w komentarzu do nikie's answer, że to, czego naprawdę chcesz, to algorytm dla płata.Więc jestem delegowania inny (niepowiązanych) odpowiedź na ten problem:

wydaje się łatwiejsze niż ogólnego problemu, ponieważ jest to „prawie wypukły”. Myślę, że następujący algorytm zmniejszyć ryzyko, że FindShortestTour natury ma na ostrym wierzchołkiem:

1. znaleźć ConvexHull (co stanowi górne i atakują powierzchni)
2. Usuń ze zbioru punktów w wypukły kadłub
3. Przeprowadzić FindShortestTour z pozostałymi punktami
4. Dołącz obie krzywe w najbliższej końcowych
5. Voilà

Jak to:

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

Dlaczego nie można po prostu sortować punkty ?:

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

Należy pamiętać, że wielokąt w ostatniej działce jest wklęsła, a więc punkty są nie zamówione zgodnie z ruchem wskazówek zegara!

Answer 3

Może mógłbyś zrobić coś z FindShortestTour. Na przykład

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

produkuje coś podobnego

Answer 4

napisałem następujący komentarz poniżej zapytanie: I don't think you'll find a general solution. Ta odpowiedź próbuje trochę na tym poprzestać.

Rozwiązanie Heike wydaje się być w porządku, ale FindShortestTour opiera się na metrycznych właściwościach zestawu, podczas gdy twoje wymagania są prawdopodobnie bardziej ze strony topologicznej.

Oto porównanie dwóch punktów zbiorów i metod dostępnych 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 Gwiazda         Slim Gwiazda

Jak widać kilka metod dostarcza oczekiwany wynik w lewej kolumnie, natomiast tylko jeden robi to po prawej. Co więcej, jedyna użyteczna metoda dla zestawu po prawej stronie jest całkowicie wyłączona dla kolumny po lewej stronie.

Answer 5

Oto funkcja Pythona, który nakazuje punktów lewo. To twierdzenie Grahama o skanowaniu. Napisałem to, ponieważ źle zrozumiałem pracę domową. Jednak potrzebuje optymalizacji.

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