sorting - 如何逆时针排列点

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 点进行排序的算法有一些建议，以便我们可以重新排列点列表以创建像上一张图​​片一样的几何图形，只需在重新排列点？？？

使用建议，我们得到如下内容。

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

我在您的问题下面发表了以下评论:我认为您找不到通用的解决方案。这个答案试图对此进行一些挖掘。

Heike 的解决方案看起来很公平，但是 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}}]

     胖星       瘦星

如您所见，有多种方法在左列上提供了预期结果，而只有一种方法在右列上提供了预期结果。此外，对于右侧的集合来说，唯一有用的方法对于左侧的列来说是完全关闭的。