Определение геометрической фигуры в матрице

#cpp #геометрия

Имеется задача определить тип фигуры (квадрат или круг) в матрице. Матрица записана
в текстовый файл в виде 15 строк по 15 символов, диаметр круга или сторона квадрата
может быть от 5 до 10 символов включительно:

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


Пожалуйста подскажите, есть ли какие то методы определения таких фигур. Реализацию
я хочу сделать сам, мне только не хочется изобретать велосипед. Писать планирую на
C++ под Windows, с минимумом сторонних библиотек.
    

Ответы

Ответ 1

Давайте фантазировать :)

Если квадрат всегда стоит вертикально (горизонтально) и диаметр круга не будет меньше
3-х, то подойдёт такая эвристика.

Берём самую левую точку, в которой единица, из таких одинаковых точек выбираем самую
верхнюю. Идём вправо по единичкам и смотрим: если в какой-то момент обнаружилось, что
сверху и снизу от нашей текущей позиции стоит единица, то значит это круг. Если не
обнаружилось, значит это квадрат.

Это обычный метод трассировки луча, только очень упрощённый.


Ответ 2

Вам нужна вариация на тему Преобразования Хаффа

Идея состоит в том, что у геометрической фигуры есть параметры, входящие в ее уравнение.
Для прямой, например, это наклон и высота (k и b). Преобразование переводит растр в
пространство этих параметров, после чего, по наличию сгущений в пространстве параметров
можно отыскать и классифицировать фигуру.


Ответ 3

Я так понимаю, что фигура у Вас залита.

Тогда идете построчно. Когда обнаружили отрезок из единиц смотрите, что находится
под ним. Если отрезок такой же длины, то подозрение на прямоугольник, если симметрично
длиннее, то подозрение на овал. Далее считываете следующую строчку. Возможны варианты


Отрезок на третьей строчке такой же длины, как и на второй. Тогда если мы подозревали
прямоугольник, то продолжаем сканировать дальше. Если овал - то несанкционированная фигура
Если продолжает увеличиваться, то продолжаем думать, что овал и считаем сколько строк
прошли для увеличения
Если меньше, то считаем, что мы прошли экватор и теперь мы должны получить строки
такой же длины, какие были до экватора. Если это не так, то опять - несанкционированная
фигура


Как отличить круг от ромба - вопрос отдельный, но ромба у Вас не ожидается.


Ответ 4

Написал, но не проверял, алгоритм таков: считается кол-во "1" в строке матрицы, а
потом из них выбираются уникальные, а потом, если кол-во уникальных равно 2, то получается,
что квадрат, иначе - что-то другое (в нашем случае круг)

  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 {
    // если не квадрат
  }


Ответ 5

Предложенные здесь ответы показались мне оверкиллом для такой простой задачи, и на
ум пришло простое решение, напишу, вдруг кому пригодится.
Суть решения в простом подсчете единиц в рядах и стобцах и сохранении их в массивах
длиной, равной длине стороны матрицы. Квадрат и круг, как симметричные фигуры, дадут
одинаковые последовательности как для рядов так и для столбцов. Таким образом анализируя
«отпечатки» фигур на осях, можно определить, что это за фигура. Для примера, матрица
из поста даст следующие результаты для рядов и столбцов соответствующе.

000666666000000
066666600000000