Как заказать очки против часовой стрелки

Question

Давайте возьмем эти очки.

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

Теперь они в определенном порядке (для меня это беспорядок!), Что можно увидеть, если мы посмотрим на 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}}]

Но нам нужно заказать их, как на картинке ниже.

Есть ли у кого-нибудь предложение для алгоритма сортировки таких 2D точек в направлении против часовой стрелки, чтобы мы могли изменить список точек для создания геометрии, подобной последней картинке, просто используя ListLinePlot в переставленных точках ???

Используя предложение , мы получаем что-то вроде следующего.

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

Может быть, вы могли бы что-то сделать с FindShortestTour. Например

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

производит что-то вроде

Answer 2

Я оставил следующий комментарий под вашим вопросом: I don't think you'll find a general solution.В этом ответе делается попытка немного разобраться в этом.

Решение Хайке кажется справедливым, но FindShortestTour основано на метрических свойствах набора, в то время как ваше требование, вероятно, больше связано с топологией.

Вот сравнение двух наборов точек и методов, доступных для 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

Как видите, несколько методов доставляют ожидаемый результат в левом столбце, а только один - в правом.Кроме того, единственный полезный метод для набора справа полностью отключен для столбца слева.

Answer 3

Почему бы вам просто не отсортировать точки?:

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

Обратите внимание, что полигон на вашем последнем графике является вогнутым, поэтому точки не упорядочены по часовой стрелке!

Answer 4

Я только что прочитал в комментарии к ответу Ники , что вам действительно нужен алгоритм аэродинамического профиля.Итак, я публикую другой (не связанный) ответ на эту проблему:

Кажется проще, чем общая проблема, потому что она "почти выпуклая".Я думаю, что следующий алгоритм уменьшает риски, которые FindShortestTour по своей природе имеет в острой вершине:

1. Найдите ConvexHull (который учитывает верхнюю поверхность и поверхность атаки)
2. Удалить из набора точек в выпуклой оболочке
3. Выполнить FindShortestTour с остальными точками
4. Соединить обе кривые в ближайших конечных точках
5. Вуаля

Вот так:

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 5

Вот функция python, которая упорядочивает точки против часовой стрелки.Это теорема Грэма о сканировании.Я написал это, потому что я неправильно понял домашнее задание.Однако нужно оптимизировать.

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