2 added 41 characters in body
source | link

Python 2 + PIL, no error, 313313 307 bytes

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

The algorithm works by walking along the perimeter of the polygon, and counting the number of encountered vertices (i.e.,detected as changes in direction). We start at the 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. IfWhenever 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, and update the last checkpoint to p, i.e., the current position (regardless of whether we found a vertex or not).: 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 distance traveled sincedisplacement 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 printreturn 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.

Python 2 + PIL, no error, 313 bytes

from Image import*
I=open(sys.argv[1])
w,h=I.size;D=I.getdata()
B={i%w+i/w*1j:D[i]!=D[0]for i in range(w*h)}
n=d=1;o=v=q=p=max(filter(B.get,B),key=abs)
while p!=w:
 p+=d*1j;e=2*B[p]+B[p+d]
 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

The algorithm works by walking along the perimeter of the polygon, and counting the number of encountered vertices (i.e., changes in direction). We start at the 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. If 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, and update the last checkpoint to p, i.e., the current position (regardless of whether we found a vertex or not). 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 distance traveled since the last checkpoint. 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. We continue in this fashion until we arrive back at o, the starting point, and print 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.

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

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.

1
source | link

Python 2 + PIL, no error, 313 bytes

from Image import*
I=open(sys.argv[1])
w,h=I.size;D=I.getdata()
B={i%w+i/w*1j:D[i]!=D[0]for i in range(w*h)}
n=d=1;o=v=q=p=max(filter(B.get,B),key=abs)
while p!=w:
 p+=d*1j;e=2*B[p]+B[p+d]
 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 (i.e., changes in direction). We start at the 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. If 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, and update the last checkpoint to p, i.e., the current position (regardless of whether we found a vertex or not). 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 distance traveled since the last checkpoint. 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. We continue in this fashion until we arrive back at o, the starting point, and print 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.

n = 10 n = 36 n = 7 n = 5 Circle