• Advertisement
Sign in to follow this  

Sorting vertices of a polygon in CCW or CW direction

This topic is 1907 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
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!

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


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

Share this post


Link to post
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!!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement