title: Sorting a list of xy-coordinates in python
body: <p>I have a long list of xy coordinates like the following:</p>
  
  <pre><code>&gt;&gt;&gt; data = [(x1,y1),(x2,y2),(x3,y3),...]
  </code></pre>
  
  <p>Every pair of coordinates represents a point of a contour in an image and I would like to sort them like they are arranged along the contour (shortest path). The shape of the contour is very complex (it's the shape of a country), that's why a <a href="http://tomswitzer.net/2010/03/graham-scan/" rel="nofollow noreferrer">ConvexHull</a>
   won't work. </p>
  
  <p>I tried out this code, but it is not precise enough:</p>
  
  <pre><code>&gt;&gt;&gt; import math
  &gt;&gt;&gt; import matplotlib.patches as patches
  &gt;&gt;&gt; import pylab
  
  &gt;&gt;&gt; pp=[(1,1),(2,3),(3,4)]
  
  # compute centroid
  &gt;&gt;&gt; cent=(sum([p[0] for p in pp])/len(pp),sum([p[1] for p in pp])/len(pp))
  # sort by polar angle
  &gt;&gt;&gt; pp.sort(key=lambda p: math.atan2(p[1]-cent[1],p[0]-cent[0]))
  # plot points
  &gt;&gt;&gt; pylab.scatter([p[0] for p in pp],[p[1] for p in pp])
  # plot polyline
  
  &gt;&gt;&gt; pylab.gca().add_patch(patches.Polygon(pp,closed=False,fill=False))
  &gt;&gt;&gt; pylab.grid()
  &gt;&gt;&gt; pylab.show()
  </code></pre>
  
  <p>I already tried like suggested in <a href="https://stackoverflow.com/questions/18280420/rearrange-a-list-of-points-to-reach-the-shortest-distance-between-them">this case</a> 
  but it did not work out well, because my list of coordinates is too long. </p>
  
  <p>As the points are very close to each other the solution to <a href="https://stackoverflow.com/questions/37742358/sorting-points-to-form-a-continuous-line">this question</a>
  might seem too complicated for my case.</p>
  
  <p><a href="https://i.stack.imgur.com/7nLgu.png" rel="nofollow noreferrer">This might illustrate my problem</a></p>