There is a task to determine the type of a shape (square or circle) in the matrix. The matrix is ​​written into a text file in the form of 15 lines of 15 characters each, the diameter of a circle or the side of a square can be from 5 to 10 characters inclusive:

000000000000000 000111111000000 000111111000000 000111111000000 000111111000000 000111111000000 000111111000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000

Please tell me if there are any methods for determining such figures. I want to do the implementation myself, I just don’t want to reinvent the wheel. I plan to write on C++ under Windows , with a minimum of third-party libraries.

  • The edge of the square is always parallel to the side of the matrix? - Zealint
  • @Zealint yes, always - Wickedwannabe
  • Then read my answer below ... - Zealint

5 answers 5

Let's fantasize :)

If the square is always standing vertically (horizontally) and the diameter of the circle is not less than 3, then such a heuristic will do.

We take the leftmost point, in which the unit, from the same points, select the highest one. Go right one by one and see: if at some point it was discovered that there is a one above and below our current position, then this is a circle. If not found, then this is a square.

This is the usual ray tracing method, only very simplified.

    You need a variation on the Huff Transformation

    The idea is that a geometric figure has parameters included in its equation. For a straight line, for example, it is a slope and height (k and b). The transformation translates the raster into the space of these parameters, after which, by the presence of condensations in the parameter space, a figure can be found and classified.

    • thanks, I will go to study - Wickedwannabe

    I understand that the figure you flooded.

    Then go line by line. When found a segment of units, see what is under it. If a segment of the same length, then the suspicion of a rectangle, if symmetrically longer, then the suspicion of an oval. Next, read the next line. Possible options

    1. The segment on the third line of the same length as the second. Then if we suspected a rectangle, then continue to scan further. If the oval is an unauthorized figure
    2. If it continues to increase, then we continue to think that the oval and count how many lines have passed to increase
    3. If it is less, then we believe that we have passed the equator and now we have to get the lines of the same length as before the equator. If it is not, then again - an unauthorized figure.

    How to distinguish a circle from a rhombus is a separate question, but you do not expect a rhombus.

      I wrote, but did not check, the algorithm is as follows: the count of "1" in the row of the matrix is ​​considered, and then unique ones are selected from them, and then, if the number of unique ones is 2, then it turns out that the square, otherwise, something else (in our case a circle)

        int **matrix; // допустим, у нас есть матрица int n, m; // n, m это размеры m - кол-во строк, n - кол-во столбцов int *tmp_m = new int[m]; // будем считать, сколько "1" в каждой строчке for(int i = 0; i < m; i++) { int tmp = 0; for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { tmp++; } } tmp_m[i] = tmp; } int *tmp_uniq = NULL; // здесь будут храниться уникальные значения из tmp_m int count_tmp_uniq = 0; // количество елементов в tmp_uniq bool is_found = false; // нашли ли элемент в tmp_uniq for (int i = 0; i < m; i++) { is_found = false; for (int j = 0; j < count_tmp_uniq; j++) { if (tmp_m[i] == tmp_uniq[j]) { is_found = true; break; } } if (!is_found) { int *tmp = new int[count_tmp_uniq + 1]; for (int j = 0; j < count_tmp_uniq; j++) { tmp[j] = tmp_uniq[j]; } tmp[count_tmp_uniq++] = tmp_m[i]; if (tmp_uniq) { delete tmp_uniq; } tmp_uniq = tmp; } } if (count_tmp_uniq == 2) { // если квадрат } else { // если не квадрат }

        The answers offered here seemed to me to be an overkill for such a simple task, and a simple solution came to mind, I will write, suddenly someone will come in handy. The essence of the solution is in simple counting of units in rows and columns and storing them in arrays with a length equal to the length of the side of the matrix. A square and a circle, like symmetrical figures, will give the same sequence for both rows and columns. Thus, analyzing the "prints" of the figures on the axes, you can determine what kind of figure. For example, the matrix from the post will give the following results for rows and columns accordingly.

         000666666000000 066666600000000