patternMinor
Calculate winding number
Viewed 0 times
numberwindingcalculate
Problem
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.
a list of vertices in some (counter-clockwise or clockwise) order?
The complexity of the algorithm must be linear time.
Solution
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_i,v_{i+1}}$$ where $\theta_{v_i,v_{i+1}}$ is the angle between $\vec{v_iP}$ and $\vec{v_{i+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.
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_i,v_{i+1}}$$ where $\theta_{v_i,v_{i+1}}$ is the angle between $\vec{v_iP}$ and $\vec{v_{i+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.
Context
StackExchange Computer Science Q#28656, answer score: 4
Revisions (0)
No revisions yet.