如何逆时针排序点的顺序

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

但我们需要按照下面的图像顺序排序。

是否有人对一种算法进行建议，以便可以逆时针方向对这些二维点进行排序，以便我们可以重新排列点列表，仅通过在重新排列的点上使用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]

换行

- PlatoManiac

---

“顺时针”需要一个中心和空间方向...问题在于中心... - Dr. belisarius

谢谢@belisarius，我会尽力遵循建议。顺便问一下，您认为使用FindShortestTour的答案适用于一般的凸包点群吗？ - PlatoManiac

不，但我认为你不会找到一个_通用_的解决方案。 - Dr. belisarius

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

肥星   瘦星

如您所见，左列中有几种方法可以得到预期的结果，而右列则只有一种。此外，对于左侧的列来说，唯一有用的方法在右侧的集合上完全无效。

- Dr. belisarius

Answer 2

也许你可以使用 FindShortestTour 做些什么。例如：

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

产生类似于

- Heike

Answer 3

为什么不直接对点进行排序呢？

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

请注意，您最后一个图形中的多边形是凸面的，因此点没有按顺时针顺序排列！

- Niki

---

排序后，它仍然不是我想要的形式。它不像我帖子中的最后一张图片。但还是谢谢你的回答。 - PlatoManiac

@PlatoManiac：这就是我在最后一句话中试图告诉你的：你展示的图形不是顺时针的。你想要什么样的排序方式？你需要这个做什么？ - Niki

看这个简单的方法，只需取最右边的点，然后将其余的点按逆时针方向排序并回到最右边的点。这样就形成了一个闭合的环路，从最右边的点开始，以同一点结束。我需要对这些点进行排序，以便形成一个二维翼型。http://enda1312.files.wordpress.com/2011/03/airfoil.gif - PlatoManiac

你想要的多边形是凹多边形，具有拐点，在某些点上是顺时针方向，而在其他点上是逆时针方向。 - Niki

你说得很对。实际上，似乎并不存在一般的解决方案来解决这个问题。有时候你的解决方案可能有效，有时候则不行。 - PlatoManiac

Answer 4

我刚刚在nikie的回答的评论中读到，你真正想要的是一个翼型算法。 因此，我将为这个问题发布另一个（不相关的）答案：

似乎比一般问题更容易，因为它“几乎是凸的”。 我认为以下算法可以减少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}]

- Dr. belisarius

Answer 5

这是一个Python函数，用于逆时针排序点。它使用了Graham扫描定理。我写这个函数是因为我误解了一项作业。虽然需要优化，但已经可以使用了。

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

- Khrotan