如何逆时针点顺序点

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.这个答案试图挖掘一点.

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

     胖星苗条之星

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

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

我刚刚在对nikie 的回答的评论中读到，您真正想要的是机翼的算法。所以，我发布了这个问题的另一个（不相关的）答案：

\n\n

\n\n

看起来比一般问题更容易，因为它“几乎是凸的”。我认为以下算法降低了 FindShortestTour 在锐角顶点固有的风险：

\n\n

\n

\n
1. 找到ConvexHull（占上表面和攻击面的）
\n
2. 从集合中删除凸包中的点
\n
3. FindShortestTour对剩余点 执行 a
\n
4. 在最近的端点连接两条曲线
\n
5. 瞧\xc3\xa0
\n

\n

\n\n

像这样：

\n\n

pt1 = Union@pt;\n<< ComputationalGeometry`\nconvexhull = ConvexHull[pt1, AllPoints -> True];\npt2 = pt1[[convexhull]];\npt3 = Complement[pt1, pt2];\npt4 = pt3[[(FindShortestTour@pt3)[[2]]]];\nIf[Norm[Last@pt4 - First@pt2] > Norm[Last@pt4 - Last@pt2], pt4 = Reverse@pt4];\npt5 = Join[pt4, pt2, {pt4[[1]]}];\nGraphics[{Arrowheads[.02], Arrow@Partition[pt5, 2, 1], \n          Red, PointSize[Medium], Point@pt1}]\n

\n\n

\n