Followers 0

# Sorting vertices of a polygon in CCW or CW direction

## 6 posts in this topic

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?

0

##### Share on other sites
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.
1

##### Share on other sites
I would fetch the points to [url="http://www.cs.cmu.edu/~quake/triangle.html"]triangle[/url] and pull out the results. Generic triangulation is hard!
0

##### Share on other sites
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.
2

##### Share on other sites
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.
1

##### Share on other sites
Hi..thanks you everyone for getting back. Can you please send me a link to Eberle's paper you mentioned?
0

##### Share on other sites
[quote name='Burnt_Fyr' timestamp='1351627382' post='4995551']
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.
[/quote]

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

## Create an account

Register a new account

Followers 0

• 19
• 14
• 23
• 11
• 28