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?

**1**

# Sorting vertices of a polygon in CCW or CW direction

Started by pjdixit, Oct 28 2012 06:18 PM

6 replies to this topic

###
#1
Members - Reputation: **108**

Posted 28 October 2012 - 06:18 PM

###
#4
Members - Reputation: **145**

Posted 29 October 2012 - 03:24 AM

Just start with left-most vertex. For CW, out of the two edges that connect to it, the higher one shout point outward(start from the selected vertex), the lower one should point inward(towards the selected vertex). Once you have the direction of these two edge, walking along them to the next vertex and making sure the next edges follow the same direction should be easy.

###
#5
Members - Reputation: **1611**

Posted 30 October 2012 - 02:03 PM

for an example in code, look for Eberle's paper on clipping a mesh against a plane. It has a function Get ordered vertices that does exactly what you want, and describes the process, which is essentially the same as Khos described. Pixalot's method will work as well, but might be confusing in the realm of 3d, where left and right are not absolutes.

###
#7
Members - Reputation: **108**

Posted 30 October 2012 - 02:38 PM

for an example in code, look for Eberle's paper on clipping a mesh against a plane. It has a function Get ordered vertices that does exactly what you want, and describes the process, which is essentially the same as Khos described. Pixalot's method will work as well, but might be confusing in the realm of 3d, where left and right are not absolutes.

After googling a little bit more I found it. Here is the link in case someone else needs it : http://www.geometrictools.com/Documentation/ClipMesh.pdf. I will go through it and will get back if it solves the problem. Thank you!!