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.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ What research have you done? We expect you to do research on your own before asking. And why are you confident that it can be done in linear time? I recommend that you edit the question to explain. $\endgroup$– D.W. ♦Commented Jul 23, 2014 at 3:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
