Sorting vertices of a polygon in CCW or CW direction
Question
I really need some urgent help with this problem.
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.
please see this page for more detailed description: http://www.dixittech.com/blog/2012/10/28/sorting-vertices-of-a-polygon-in-ccw-or-cw-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)
OTHER TIPS
I'm assuming that CW/CCW direction is of no concern (guaranteeing one or the other is much more complex). This pseudo-code algorithm sort vertices either CW or CCW.
marked_edge <- any edge
first <- marked_edge.start
list <- [first]
current <- marked_edge.end
while current <> first
list <- list + [current]
new_edge <- find the edge that is not the marked_edge and has the vertex current as either start or end
if new_edge.start=current then
current <- new_edge.end
else
current <- new_edge.start
endif
marked_edge <- new_edge
endwhile