Cómo pedir puntos en sentido contrario a las agujas del reloj

Question

Permite tomar puntos.

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

Ahora están en cierto orden (para mí es un desorden!) Que puede ser visto si nos fijamos en el 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}}] 

pero tenemos que pedirlos como la imagen de abajo

¿Alguien tiene alguna sugerencia para un algoritmo para ordenar dichos puntos 2D en sentido contrario a las agujas del reloj para que podamos reordenar la lista de puntos para crear una geometría como la última pic sólo mediante el uso ListLinePlot en el reordenado ¿¿¿¿puntos????

Al utilizar la sugerencia obtenemos algo como lo siguiente.

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

Acabo de leer en un comentario al nikie's answer que lo que realmente quiere es el algoritmo para un perfil aerodinámico.Por lo tanto, estoy publicando otra respuesta (relación) a este problema:

parece más fácil que el problema general, ya que es "casi convexa". Creo que el siguiente algoritmo reducir los riesgos que FindShortestTour tiene inherentemente en el vértice agudo:

1. Encuentra la ConvexHull (que da cuenta de las superficies superior e ataque)
2. eliminar del conjunto de los puntos en el convexo casco
3. Realizar una FindShortestTour con los puntos restantes
4. unir las dos curvas en los extremos más cercanos
5. Voilà

De esta manera:

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

¿Por qué no acaba de ordenar los puntos ?:

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

Tenga en cuenta que el polígono en su última trama es cóncava, por lo que los puntos son ¡No ordenado en sentido horario!

Answer 3

Quizás podría hacer algo con FindShortestTour. Por ejemplo

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

produce algo así como

Answer 4

he publicado el siguiente comentario a continuación su pregunta: I don't think you'll find a general solution. Esta respuesta intenta cavar un poco sobre eso.

La solución de Heike parece justa, pero FindShortestTour se basa en las propiedades métricas del conjunto, mientras que su requisito es probablemente más en el aspecto topológico.

Aquí es una comparación de dos conjuntos de puntos y los métodos disponibles para 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}}] 

      grasa estrella         Delgado Estrella

Como se puede ver , varios métodos entregan el resultado esperado en la columna de la izquierda, mientras solo uno lo hace en el correcto. Además, el único método útil para el conjunto de la derecha está completamente desactivado para la columna de la izquierda.

Answer 5

Aquí es una función de Python que ordena puntos hacia la izquierda. Es el teorema de Graham's Scan. Lo escribí porque malentendí una tarea. Sin embargo, necesita optimización.

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