• Create Account

## Sorting vertices of a polygon in CCW or CW direction

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1pjdixit  Members

Posted 28 October 2012 - 06:18 PM

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.

Any idea how this can be achieved?

### #2khos  Members

Posted 28 October 2012 - 10:09 PM

I would loop though each edge and test for matching end points. Each match would be pushed into a collection. The order of collection should help you to build a new set of vertices ordered.

### #3MaxDZ8  Members

Posted 29 October 2012 - 12:33 AM

I would fetch the points to triangle and pull out the results. Generic triangulation is hard!

Previously "Krohm"

### #4pixalot  Members

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.

### #5Burnt_Fyr  Members

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.

### #6pjdixit  Members

Posted 30 October 2012 - 02:19 PM

Hi..thanks you everyone for getting back. Can you please send me a link to Eberle's paper you mentioned?

### #7pjdixit  Members

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!!

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.