Given a binary image (one that contains only 0 and 1) with width of W and height of H your task is to describe what is in the image. There are 4 types of shapes in the image: line, equilateral triangle, square and regular pentagon. They can have any size and can be rotated.
Input
The first line of the input containts two integer numbers: H and W.The following H lines contain W charaters from set {0, 1} witout spaces. The lines are separated by a newline character.
Output
Your program should output the description of the image:2 number_of_lines
3 number_of_triangles
4 number_of_squares
5 number_of_pentagons
Constraints
- 512 <= H <= 1024
- 512 <= W <= 1024
- Side of each figure > 70 (euclidian length).
- The figures don't overlap and they don't touch the sides of the image.
- It is impossible to draw a perfect line. Thus, the edges of the shapes are usually not straight.
- The shapes are solid (there are no zeroes inside them)
Sample
| Input | Output |
|---|---|
| >>Link to Input<< | 2 0 3 1 4 1 5 1 |
Official solution (Adrian Soucup)
This problem uses the following idea: Because all polygons are regular, the type of the polygon can be detected using the ratio of the maximum Euclidian distance between the center of mass and the boundary and the minimum Euclidian distance between the center of mass and boundary of each figure.
This ratio is equal to 1/cos(pi/N), where N is the number of sides of the regular polygon. The algorithm is as follows:
- Find connected components;
- Compute the center of mass for each figure as: (xc, yc) = 1/tsum of (xi,yi), where (xi,yi) are all pixels (pixel coordinates) of a connected component;
- Compute the maximum and minimum distance between this point (xc,yc) and the boundary of the figure. Then, the ratio can be used to detect the type of the figure. A pixel is on the boundary when it has at least 1 neighbor with value of 0.
In case of lines this ratio will be > 2, for triangles this ratio will be 2, for squares sqrt2 and everything else will be considered a pentagon.
For maximizing precision, the algorithm uses the square of the Euclidian distance and the square of ratio and uses the middle of the interval as decision boundary. If r is the ratio then:
- r2 > 15 → line
- r2 ∈ (3, 15] → triangle
- r2 ∈ (1.76, 3] → square
- r2 ≤ 1.76 → pentagon
Complexity: O(W*H) where W is the width and H is the height of the image.
Alternative solution (Gabriel Robert Inelus)
In order to solve this problem, we can use a Convex Hull algorithm which has the capacity of treating colinear points. We use a fill algorithm to get the boundaries of each shape and to insert them into a vector of pairs (x, y) which represents the coordinates of the points. Then we use Andrew's Modification convex hull algorithm which will give us the convex hull of the geometric shape. We have to take care of the precision, because a straight line is not actually straight on its pixelated representation. Thus, we should consider any 3 points which create a triangle with the absolute value of the area less than EPS as 3 colinear points, and elimninate the middle one.
Note that we have to carefully choose EPS in order to correctly eliminate the almost colinear points. EPS ∈ [47,54] can be succesfully used, however I let the proof for this EPS as homework for the curious reader.
The solution can be easily obtained from the (correct) convex hull by counting the number of edges with more than 70 units. Some others edges may apear due to precision errors thus, we have to sort them by size and delete the small ones which are obvious precision errors.
The complexity is O(H*W) due to the fact that there are few boundary points on each shape.
