17
\$\begingroup\$

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:

enter image description here

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

enter image description hereenter image description here

n=36

enter image description hereenter image description here

n = 7

enter image description hereenter image description here

n=5

enter image description hereenter image description here

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

enter image description here

\$\endgroup\$
  • \$\begingroup\$ I see many angles in your test cases that are greater than 170°. For example, all the "non-point" angles (the ones closer to the center) in your star. \$\endgroup\$ – Doorknob Nov 29 '15 at 22:23
  • \$\begingroup\$ @Doorknob It's the smaller angle that should be less than 170°. \$\endgroup\$ – lirtosiast Nov 29 '15 at 22:25
  • \$\begingroup\$ Yes, but they are again greater than 190°. The point of this restriction is to eliminate examples where the two adjecent sides are difficult to tell apart. \$\endgroup\$ – flawr Nov 29 '15 at 22:25
  • 2
    \$\begingroup\$ Which color is the interior of the polygon? \$\endgroup\$ – feersum Nov 30 '15 at 0:12
  • 1
    \$\begingroup\$ 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 :-) \$\endgroup\$ – Luis Mendo Nov 30 '15 at 19:04
12
\$\begingroup\$

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.

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

\$\endgroup\$
  • \$\begingroup\$ Thank you for this detailed explanation! I love your illustrations! \$\endgroup\$ – flawr Nov 30 '15 at 20:28
  • \$\begingroup\$ If there's an edge to the east of o, wouldn't the other end be even farther from the origin? \$\endgroup\$ – aditsu Nov 30 '15 at 23:25
  • 1
    \$\begingroup\$ @aditsu I think the terminology might be a little confusing here. We talk about the sides of the polygon, in the geometric sense, and the edges of the (set of pixels comprising the) polygon, as a raster graphic. o is the farthest foreground pixel from the origin, so the pixel to its east must be a background pixel, hence we say that there's an edge to the east of o. \$\endgroup\$ – Ell Nov 30 '15 at 23:42

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.