1
$\begingroup$

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.

$\endgroup$
  • 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. Jul 23 '14 at 3:46
4
$\begingroup$

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.

$\endgroup$

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.