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}{2pi}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
