Jump to content

  • Log In with Google      Sign In   
  • 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.

  • You cannot reply to this topic
6 replies to this topic

#1 pjdixit   Members   -  Reputation: 108

Like
0Likes
Like

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.
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?



Sponsor:

#2 khos   Members   -  Reputation: 196

Like
1Likes
Like

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.

#3 Krohm   Crossbones+   -  Reputation: 3014

Like
0Likes
Like

Posted 29 October 2012 - 12:33 AM

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

#4 pixalot   Members   -  Reputation: 145

Like
2Likes
Like

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 Burnt_Fyr   Members   -  Reputation: 1212

Like
1Likes
Like

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.

#6 pjdixit   Members   -  Reputation: 108

Like
0Likes
Like

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?

#7 pjdixit   Members   -  Reputation: 108

Like
0Likes
Like

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.



PARTNERS