Count the number of sides on a polygon

Question

Count the number of sides on a polygon

The polygon-side-counting robot has decided to travel the world without telling anyone before, but it is crucial that the process of polygon counting is not stopped for too long. So you have following task: Given a black and white image of a polygon, your program/functoin should return the number of sides.

The program will be fed to an old punch card computer, and as punchcards are very expensive nowadays, you better try to make your program as short as possible.

The edges are at least 10 pixels long, and the angles formed by two adjecent edges is at least 10° but no more than 170° (or again greater than 190°). The polygon is completely contained within the image, and the polygon as well as it's complement is connected (there are no isolated islands) so this input would not be valid:

Scoring

This is codegolf, that means the shortest submission in bytes wins, your submission has to find the correct number of edges for every test case. (And the submission should work for other cases as well, optimization for just those test cases is not allowed.)

If you want to submit a solution that does not find the correct number each time, you can submit that too, but it will be ranked behind all the submissions that perform better.

Please include the total number in your submission title. (The total error the sum of the absolute differences between the real number of sides and the each output).

Test cases

n=10

n=36

n = 7

n=5

This is not a test case, just out of curiosity: How many edges do you get for this input?

Answer 1

Python 2 + PIL, no error, 313 307 bytes

from Image import*
I=open(sys.argv[1])
w,h=I.size;D=I.getdata()
B={i%w+i/w*1j for i in range(w*h)if D[i]!=D[0]}
n=d=1;o=v=q=p=max(B,key=abs)
while p-w:
 p+=d*1j;e=2*({p}<B)+({p+d}<B)
 if e!=2:e%=2;d*=1j-e*2j;p-=d/1j**e
 if abs(p-q)>5:
    t=(q-v)*(p-q).conjugate();q=p;w=o
    if.98*abs(t)>t.real:n+=1;v=p
print n

Takes an image file name on the command line, and prints the result to STDOUT.

Gives the correct result for all tests, and n = 28 for the circle.

Explanation

The algorithm works by walking along the perimeter of the polygon, and counting the number of encountered vertices (detected as changes in direction). We start at the pixel farthest away from the origin, o, which is guaranteed to be a vertex, and therefore, to be adjacent to an edge (i.e., a boundary between a foreground pixel and a background pixel). We keep track of our position, p, the most recent vertex, v, and the most recent "checkpoint", q, all of which are initially equal to o. We also keep track of the direction of the edge, d, relative to the current pixel; d initially points east, which is a safe direction, since we know there's an edge to the east of o, or else it wouldn't be farthest from the origin. We move along the edge, in a direction perpendicular to d, such that d points to our left, i.e., in a clockwise direction. Whenever we "fall off the edge", i.e., in any situation where p is outside the polygon, or where the pixel to our left (i.e., in the direction of d) is inside the polygon, we adjust p and d accordingly before resuming.

Every time the distance between p and the last checkpoint, q, gets bigger than 5, we try to determine whether we passed over a vertex between q and p: We compare the angle between vq (i.e., the vector from v to q), which is the general direction of the side of the polygon we were walking along when we reached the last checkpoint, and qp, the displacement between the last checkpoint and the current position. If the angle is greater than about 10°, we conclude that we're walking along a different side of the polygon, increase the vertex count, and set v, the current vertex, to p. At each checkpoint, regardless of whether we detected a vertex or not, we update q, the last checkpoint, to p. We continue in this fashion until we arrive back at o, the starting point, and return the number of vertices found (note that the vertex count is initially 1, since the starting point, o, is itself a vertex.)

The images below show the detected vertices. Note that taking p, the current position at each checkpoint, as the position of the new vertex is not optimal, since the real vertex is probably somewhere between the last checkpoint, q, and p, along the perimeter. As you can see, all the vertices other than the first one (generally, the bottom-right vertex) are a little off. Fixing this would cost more bytes, but this seems to be working well enough as it is. That being said, it's a little hard not to overfit with only four test cases.