[Solved]: Calculate winding number

Problem Detail: 

How can one calculate the winding number of a polygon given as a list of vertices in some (counter-clockwise or clockwise) order?

The complexity of the algorithm must be linear time.

Asked By : Dib

Answered By : ZeroUltimax

The winding number $w$ of a polygon has to be calculated around a certain point $P$. Since your question is ambiguous, I'll suppose you've already determined $P$.

Given a list of n vertices $v_0, v_1, ... v_{n-1},v_0 $ (notice $v_n = v_0$) given in counter-clockwise order, a simple linear way to calculate the winding number is $$ w = \frac {1}{2\pi}\sum_{i=0}^{n-1} \theta_{v_n,v_{n+1}}$$ where $\theta_{v_n,v_{n+1}}$ is the angle between $\vec{v_nP}$ and $\vec{v_{n+1}P}$, which you can obtain using dot product and arcosines.

Your second solution consists of casting a ray $R$ from $P$. The winding number of your polygon can then be calculated as the number of edges $E_+$ that cross $R$ going counter clockwise, minus the number of edges $E_-$ that cross $R$ going clockwise.

I.e.: $w = E_+ - E_-$

If you want further insight (and proof) on how to determine $E_+$ and $E_-$, I highly suggest you research the "point in polygon" problem and the "crossing number" often associated with that problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28656