title: Sorting a polygon vertices clockwise
body: <p>I am working on a project that involves conversion of polygon into trapezoids. I am using a version of seidel.py as featured <a href="https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/" rel="nofollow noreferrer">here</a>. This software essentially takes in coordinates of a polygon, and performs trapezoidal decomposition on it using an algorithm that finds the intersections of vertical lines eminating from the vertices building up the original polygon. </p>
  
  <p>You can find my version of this here: <a href="https://github.com/ssohin/poly2trap.git" rel="nofollow noreferrer">Poly2Trap</a>
  for Python 3.6.7.</p>
  
  <p><strong>What I'm trying to achieve is:</strong> </p>
  
  <ul>
  <li>Input polygon</li>
  <li>decompose polygon using seidel.py</li>
  <li>extract decomposed polygon's newly added vertices</li>
  <li>Create new vertex list by adding new vertices created during triangulation to the original vertex list</li>
  <li>Draw a polygon with the new vertex list</li>
  </ul>
  
  <p><strong>What's happening:</strong></p>
  
  <ul>
  <li>The decomposition method works and outputs a list of trapezoids. These trapezoids each have three or four vertices, some of which are already defined in the original polygon. </li>
  <li>After I get the list of all trapezoids, I combine all into a list of vertices (all trapezoids and original polygon) and remove duplicates.</li>
  <li>At this point, I am left with a set of distinct vertices which I want to portray as a polygon again.</li>
  <li>To achieve this, I am using <a href="https://stackoverflow.com/questions/44025403/how-to-use-matplotlib-path-to-draw-polygon">angular sort</a> method which takes the centroid of the polygon and sorts the vertices by calculating angles from the vertex to the centroid. </li>
  <li>When I plot and compare, the resultant polygon isn't as expected. </li>
  </ul>
  
  <p><strong>What I need your help with is:</strong>
  If you know of any other method to sort vertices of a complex polygon because I think that's where I am lacking. </p>
  
  <p>Here are my results:</p>
  
  <ul>
  <li><a href="https://i.stack.imgur.com/piWRV.png" rel="nofollow noreferrer">Output: Decomposed polygon into trapezoids of the seidel.py</a></li>
  <li><a href="https://i.stack.imgur.com/qvXcs.png" rel="nofollow noreferrer">The results after sort and plot show that the sort fails</a></li>
  </ul>
  
  <p>Additional info:</p>
  
  <p>I want to work with complex polygons with vertices in the range of a few hundred in the future and that is why I am avoiding the use of convex hull.</p>
  
  <p>Here, a point is a tuple with x and y coordinates. and all the vertices of the polygon are stored in a list of tuples. </p>
  
  <pre><code>poly_coords = [(x,y),]
  </code></pre>
  
  <p>Minimal, Complete, and Verifiable example:
  poly2trap.py</p>
  
  <pre><code>import numpy as np
  import matplotlib.pyplot as plt
  
  original_poly_coords = [(235.04275999999999, 739.07534999999996),
  (218.13066000000001, 719.73902999999996),
  (218.15215000000001, 709.96821),
  (218.17362, 700.19740000000002),
  (243.15215000000001, 685.27858000000003),
  (268.13065, 670.35974999999996),
  (268.13065, 660.81429000000003),
  (268.13065, 651.26882999999998),
  (314.55921999999998, 651.26882999999998),
  (360.98779000000002, 651.26882999999998),
  (360.98683999999997, 666.44740000000002),
  (360.98046561000007, 669.27438118000009),
  (360.96234088000011,672.68539864000013),
  (360.93345946999995, 676.58895225999993),
  (360.89481504000003, 680.89354191999996),
  (360.84740125000002, 685.50766749999991),
  (360.79221175999999, 690.33982888000003),
  (360.73024022999999, 695.29852593999999),
  (360.66248032000004, 700.29225856000005),
  (360.58992569000003, 705.22952662000012),
  (360.51357000000002, 710.01882999999998),
  (360.04131999999998, 738.41168000000005),
  (310.51454999999999, 738.41168000000005),
  (260.98779999999999, 738.41168000000005),
  (260.98779999999999, 748.41168000000005),
  (260.98779999999999, 758.41168000000005),
  (256.47133000000002, 758.41168000000005),
  (251.95484999999999, 758.41168000000005),
  (235.04275999999999, 739.07534999999996)
  ]
  
  #After performing triangulation
  coords_after_triangulation = [(257.22974168, 758.41168), (361.63905883, 651.2688300000154), 
  (360.98046561000007, 669.2743811800001), (361.22358883000004, 651.26883), (361.29515521662, 651.26883),
  (243.15215, 685.27858), (243.83742858, 685.27858), (361.36277257856005, 651.26883), 
  (361.42553875594,651.26883), (361.48255158887997, 651.26883), (361.53290891750004, 651.26883),
  (261.72621168, 738.41168), (251.95485, 758.41168), (261.72621168, 738.4116799999902),
  (361.53290891750004, 685.5076675000018), (361.42553875594, 695.2985259399975),
  (361.42553875594, 695.2985259400011), (315.21048883, 651.26883), (360.98684, 666.4474),
  (360.84740125, 685.5076674999999), (361.57570858192, 680.8935419200061),
  (360.9623408800001, 672.6853986400001), (361.57570858192, 680.8935419199988), 
  (361.48255158887997, 690.3398288800017), (361.64973999118007, 662.6631410694681), 
  (311.25296168, 738.41168), (268.80100975, 738.41168), (315.21048883, 738.41168), 
  (218.13066, 719.73903), (218.86211821, 719.7524137325041), (218.8738174, 719.7657746356965),
  (268.13065, 660.81429), (268.79146429, 660.8142900000094), (218.85039903, 719.73903), 
  (218.85039903, 719.739029999997), (360.98779, 651.26883), (360.77973168, 651.26883), 
  (218.17362, 700.1974), (218.8738174, 700.1974000000046), (218.8738174, 700.1974), 
  (314.55922, 651.26883), (243.83742858, 739.07535), (361.63905883, 671.7505493924255), 
  (360.93345946999995, 676.5889522599999), (360.04132, 738.41168), 
  (360.73024023, 695.29852594), (360.77973168, 738.4116800000011), 
  (360.77973168, 738.41168), (360.51357, 710.01883), (261.72621168, 674.5878176386889), 
  (361.65328739999995, 666.4474000000046), (361.36277257856005, 700.292258559999), 
  (218.15215, 709.96821), (218.86211821, 709.9682099999918), (218.86211821, 709.9682100000209), 
  (268.13065, 670.35975), (268.80100975, 670.3597500000615), (268.80100975, 670.35975), 
  (361.22358883000004, 710.0188300000009), (361.29515521662, 705.2295266200017), 
  (361.57570858192, 651.26883), (361.6100484222599, 651.26883), 
  (361.6350262786401, 651.26883), (360.89481504, 680.89354192), 
  (260.9878, 748.41168), (361.63905883, 651.26883), (311.25296168, 651.26883), 
  (252.71326168, 679.9741709800953), (361.6350262786401, 672.6853986399947), 
  (310.51455, 738.41168), (235.04276, 739.07535), (235.78183535, 739.07535), 
  (243.83742858, 748.2751425044893), (235.78183535, 690.0927851454428), (257.22974168, 677.2750150833695), 
  (360.79221176, 690.33982888), (260.9878, 758.41168), (360.58992569000003, 705.2295266200001), 
  (261.73621168, 748.4116799999902), (252.71326168, 758.41168), (268.13065, 651.26883), 
  (360.66248032000004, 700.29225856), (261.74621168, 758.4116799999902), (261.74621168, 758.41168), 
  (268.79146429, 651.26883), (268.80100975, 651.26883), (268.78191883, 651.2688300000154), 
  (268.78191883, 651.26883), (361.6100484222599, 676.5889522599973), (261.73621168, 758.41168), 
  (261.72621168, 758.41168), (256.47133, 758.41168), (361.64973999118007, 669.2743811799883), 
  (361.64973999118007, 669.2743811800028), (260.9878, 738.41168),(257.22974168, 758.41168)]
  
  
  def ccw_sort(p):
      """Sort given polygon points in CCW order"""
      p = np.array(p)
      mean = np.mean(p,axis=0)
      d = p-mean
      s = np.arctan2(d[:,0], d[:,1])
      return p[np.argsort(s),:]
  
  #sort poly after triangulation
  sorted_poly_coords = ccw_sort(coords_after_triangulation)
  
  #plot
  #How it should look like:
  fig,ax = plt.subplots()    
  xa = [i[0] for i in original_poly_coords[:]]
  ya = [i[1] for i in original_poly_coords[:]]
  ax.plot(xa,ya, color = 'b')
  
  #How it looks like:
  fig,bx = plt.subplots()
  xb = [i[0] for i in sorted_poly_coords[:]]
  yb = [i[1] for i in sorted_poly_coords[:]]
  bx.plot(xb,yb, color='r')
  
  plt.show()
  
  </code></pre>
  
  <p>Any help is appreciated.</p>