0
$\begingroup$

Given an ordered list of n points on a plane, which describe a (possibly concave, but not self intersecting) polygon, how can i determine if the points are ordered clockwise or counterclockwise? Counterclockwise is defined as the positive rotation around the plane's normal.

I'd like a solution without a 2d projection, preferably with simple algebraic operations like cross product's and dot product's.

I think if one would properly define a signed measure of the angle between an edge to the next, the sign of the sum of all those measures could have a relation to the ordering. I could be wrong about that though.

$\endgroup$
2
$\begingroup$

Take any point $P$ in your 3D-space, and if we call the given points $A_1,\ldots,A_n$, calculate the sum of the vector products $\vec{S} = \frac{1}{2}\sum_{i=1}^n{\overrightarrow{PA_i}\times\overrightarrow{PA_{i+1}}}$, where indices are taken modulo $n$. You can easily verify that the value of $\vec{S}$ does not depend on the choice of $P$.

So we can assume that $P$ lies in your plane, so each cross product from the sum has both factors as vectors in your plane, so each cross product is normal to your plane. Hence the sum is also a vector that is normal to your plane. The length of $\vec{S}$ calculates the area of your polygon. The direction of $\vec{S}$ shows you the direction of the normal around which the points $A_1,\ldots,A_n$ would be considered counter-clockwise.

This means you need to calculate $\vec{S}$ (or $2\vec{S}$, as the value of the area is not important here), with any choice of $P$ (usually you just use the origin of your coordinate system), then you need to compare $\vec{S}$ with your given plane normal $\vec{n}$: Are they pointing in the same or opposite directions? This check can be simply done with a simple dot product: Is $\vec{S} \cdot \vec{n}$ positive (same direction) or negative (opposite direction)?

$\endgroup$
  • $\begingroup$ Thank you, exactly what i was looking for! $\endgroup$ – Mario Dekena Feb 20 '17 at 10:19
  • $\begingroup$ Make sure to test the algorithm on something you know the result of. Because we are dealing with vector products, a simple change of order of multiplication will reverse the direction of the product. $\endgroup$ – Ingix Feb 20 '17 at 10:38

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.