Compute the winding number

Question

The winding number is the integer number of net counterclockwise revolutions an observer must have made to follow a given closed path. Note that any clockwise revolutions count negative towards the winding number. The path is allowed to self intersect.

Some examples (shamelessly taken from Wikipedia) are given below:

Your goal is to compute the winding number for a given path.

Input

The observer is assumed be at the origin (0,0).

The input is a finite sequence of points (pair-like of integer numbers) from any desired input source which describes the piece-wise linear path. You may flatten this into a 1D sequence of integer numbers if desired, and may also swizzle the input to take all x coordinates before all y coordinates/vise-versa. You may also take the input as a complex number a+b i. The path may self intersect and may contain zero-length segments. The first point is the start of the path and is assumed to lie somewhere on the positive x axis.

No part of the path will intersect the origin. The path will always be closed (i.e. the first and lost point are the same). Your code may either imply the last point or require it to be included.

For example, depending on your preference both inputs specify the same square:

implied end point

1,0
1,1
-1,1
-1,-1
1,-1

explicit end point

1,0
1,1
-1,1
-1,-1
1,-1
1,0

Output

The output is a single integer for the winding number. This may be to any source (return value, stdout, file, etc.).

Examples

All examples have the end point explicitly defined and are given as x,y pairs. Incidentally, you should be able to also directly feed these examples into any codes assuming implicitly defined end points and the outputs should be the same.

1. Basic test

1,0
1,1
-1,1
-1,-1
1,-1
1,0

Output

1

2. Repeated point test

1,0
1,0
1,1
1,1
-1,1
-1,1
-1,-1
-1,-1
1,-1
1,-1
1,0

Output

1

3. Clockwise test

1,0
1,-1
-1,-1
-1,1
1,1
1,0

Output

-1

4. Outside test

1,0
1,1
2,1
1,0

Output

0

5. Mixed winding

1,0
1,1
-1,1
-1,-1
1,-1
1,0
1,-1
-1,-1
-1,1
1,1
1,0
1,1
-1,1
-1,-1
1,-1
1,0
1,1
-1,1
-1,-1
1,-1
1,0

Output

2

Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any builtin functions so long as they were not specifically designed to compute the winding number.

Answer 1

ES6, 83 bytes

a=>a.map(([x,y])=>r+=Math.atan2(y*b-x*c,y*c+x*b,b=x,c=y),b=c=r=0)&&r/Math.PI/2

Takes as input an array of pairs of points which are interpreted as complex numbers. Rather than converting each point into an angle, the points are divided by the previous point, which Math.atan2 then converts into an angle between -π and π, thus automatically determining which way the path is winding. The sum of the angles is then 2π times the winding number.

Since Math.atan2 doesn't care about the scale of its arguments I don't actually perform the full division z / w = (z * w*) / (w * w*) instead I just multiply each point by the complex conjugate of the previous point.

Edit: Saved 4 bytes thanks to @edc65.

Answer 2

MATL, 11 bytes

X/Z/0)2/YP/

Input is a sequence of complex numbers including the end point.

Try it online!

Explanation

Most of the work is done by the Z/ function (unwrap), which unwraps angles in radians by changing absolute jumps greater than or equal to pi to their 2*pi complement.

X/       % compute angle of each complex number
Z/       % unwrap angles
0)       % pick last value. Total change of angle will be a multiple of 2*pi because 
         % the path is closed. Total change of angle coincides with last unwrapped
         % angle because the first angle is always 0
2/       % divide by 2
YP/      % divide by pi

Answer 3

Jelly, 11 bytes

æAI÷ØPæ%1SH

This takes input as a list of y-coordinates and a list of x-coordinates.

Try it here.

Answer 4

Python, 111

Longest answer so far. My motivations are 1) learn python and 2) possibly port this to pyth.

from cmath import *
q=input()
print reduce(lambda x,y:x+y,map(lambda (x,y):phase(x/y)/pi/2,zip(q[1:]+q[:1],q)))

Input is given as a list of complex numbers.

Ideone.

I think the approach is similar to the ES6 answer.

When 2 complex numbers are multiplied, the argument or phase of the product is the sum of the argument or phase of the two numbers. Thus when a complex number is divided by another, then the phase of the quotient is the difference between the phases of the numerator and denominator. Thus we can calculate the angle traversed through for each point and the next point. Sum these angles and divide by 2π gives the required winding number.