4
$\begingroup$

Suppose a polygon with $n$ vertices is given $(V_1,V_2,... V_n)$.
If the $(x,y)$ coordinates of the each vertex of the polygon are given, then how can we find that the vertices $V_1,V_2,V_3$... $V_n$ are in clockwise or anticlockwise fashion? - that is, I need to find that if we are moving from $V_1,V_2,\dots V_n$, we are in clockwise or anticlockwise direction.

What I tried :
I found the center of the polygon and took the origin of the coordinate system at the center, and then calculated the angle between the $x$ axis and the vertex.

Problem :
Two vertices may be at same angle.

I need some solution which can be implemented in computer logic.

$\endgroup$
3
$\begingroup$

Everything you need is at this Wolfram Mathworld link. Just compute the area using the expression given there. If the result is positive, the points are anticlockwise; if the result is negative, the points are clockwise.

$\endgroup$
3
$\begingroup$

Quoting from http://www.faqs.org/faqs/graphics/algorithms-faq/

Subject 2.07: How do I find the orientation of a simple polygon?

Compute the signed area (Subject 2.01). The orientation is counter-clockwise if this area is positive.

A slightly faster method is based on the observation that it isn't necessary to compute the area. Find the lowest vertex (or, if there is more than one vertex with the same lowest coordinate, the rightmost of those vertices) and then take the cross product of the edges fore and aft of it. Both methods are O(n) for n vertices, but it does seem a waste to add up the total area when a single cross product (of just the right edges) suffices. Code for this is available at http://cs.smith.edu/~orourke/Code/polyorient.C (2K).

The reason that the lowest, rightmost (or any other such extreme) point works is that the internal angle at this vertex is necessarily convex, strictly less than pi (even if there are several equally-lowest points).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.