sortingpolygonccw

Sorting vertices of a polygon in CCW or CW direction


I have a set of edges and vertices defining a polygon (not necessarily convex). The vertices and edges are in random order and I want to sort/order the vertices of this polygon in clockwise (or anti-clock wise) direction.

Any idea how this can be achieved?


Solution

  • I think this is a simplified version of Königsberg Bridge Problem essentially.

    if there's no any case that more than two edges are connected at a single node, you can build an adjacent list and "travel" through all the nodes.

    If there's case that >2 edges are connected at a node, ... hum i think there will be more than one possible order. Just refer to the solution of Königsberg Bridge Problem.

    for v,u in edges:
      adjacent[v].append(u)
      adjacent[u].append(v)
    
    order=[]
    
    start = v0 #start from an arbitrary node
    
    def draw(now,last):
      if now==start and len(order)>0:
        return
      order.append(now)
      for i in adjacent[now]:
        if i != last:
          draw(i,now)
    
    draw(start,NULL)