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:

enter image description here

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.

• Level River St: Can input be taken as complex numbers (or a string representation of them, such as "1-i" or "1-1i" ?)
• helloworld922: yes, any type of pair is allowed.

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.

• edc65: Nice and fast. And I don't understand your math. But reduce is almost always a bad choice.
• edc65: 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 using map instead or reduce. You have my vote anyway
• Neil: @edc65 Thanks; I used reduce because I didn't realise that Math.atan2(0,0) is 0. (Well, it depends on whether one of your 0s is actually -0.) The maths is based on complex division, which is normally calculated as z / w = z * w* / |w|², but I don't care about the magnitude, so it's just multiplication by the complex conjugate. Also slightly confusingly Math.atan2 accepts (y, x) arguments.
• Wojowu: I admit I don't understand the code, but if your description is accurate, then I believe your answer is wrong. Indeed, if you inputted points from this path (I'm giving a picture for greater clarity) then the winding number is 1, while your problem would output 2.
• Neil: @Wojowu Sorry, I meant the angle between the points as measured from the origin, rather than the polygon's external angles, so for your picture, my code should indeed compute the answer as 1.

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

• ETHproductions: MATL and Jelly have pretty much tied most mathy challenges lately. I'm impressed, you've almost out-meta-golfed Dennis' language...
• Luis Mendo: @ETHproductions Thanks for your nice words! Yes, they have been tied in some recent challenges. On the other hand, I've seen quite a few problems where Jelly's byte count is about half as MATL :-D

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.

• mmj: Python 3 version: sum(map(lambda c:phase(c[1]/c[0]),zip(q,q[1:]+q[:1])))/pi/2

Answer 5

C (gcc), 111 bytes

s;r;c(p,n)float*p;{r=0;for(;--n;p+=2){s=p[3]>0?1:-1;r+=s*((p[1]>0?1:-1)-s&&(*p*p[3]-p[1]*p[2])*s>0);}return r;}

Try it online!

Input is expected to be a flattened array p of the coordinates with the first and last points being the same, along with the number of points n (counting the duplicate first and last points separately).

Explanation: Unlike the prior answers, this one is based on counting the number of intersections of the path with the positive x-axis, with orientation considered. The piece *p*p[3]-p[1]*p[2] is based on the fact that the line joining \$(a,b)\$ and \$(c,d)\$ hits the x-axis at \$\frac{ad-bc}{d-b}\$; however, in the case that \$b\$ and \$d\$ have opposite signs so that this intersection is actually on the line segment, then \$\frac{1}{d-b}\$ has the same sign as \$d\$.

(Note that in order to properly handle cases where one or more of the points are exactly on the positive x-axis, the code considers such points as equivalent to being very slightly below the x-axis.)

• ceilingcat: 104 bytes
• Daniel Schepler: I just noticed that the specification technically only allows points in \$\mathbb{Z}^2\$ as vertices so I could save two bytes with int*p instead of float*p bringing it down to 102 bytes.