Обнаружение фигур в "растровом изображении"

Итак, подготовив себя к следующему, то есть экстремальному соревнованию, я пережил некоторые прошлые проблемы. Я нашел тот, который действительно беспокоит меня, так как я не могу понять, что делать. Возможно, я мог бы использовать его с помощью кода с кодом Bruteforce 300 строк, но я думаю, что это не то, что кто-то должен делать на таких соревнованиях, поэтому мне нужна ваша помощь!

Обнаружение фигур в растровом изображении

Заявление о проблемах: при анализе изображений обычно анализируется растровое изображение и наблюдаются фигуры, присутствующие в нем. Для этой проблемы создайте алгоритм для обнаружения фигур в заданном растровом изображении. Формы, присутствующие на карте, должны быть от квадрата, прямоугольника, треугольника и параллелограмма.

В растровом изображении каждый пиксель представлен как бит, 1 - представляющий черный, а 0 - белый. Ожидается, что участники обнаружат фигуры, выделенные черным цветом. Входные данные Первая строка будет содержать размер битовой карты в пикселях, представленных как (строка, столбец).

например. 6,8 это означает битовую карту из 6 строк и 8 столбцов. Следующая строка будет содержать ряд десятичных цифр от 0 до 255, разделенных пробелами. Каждая цифра будет представлять собой набор из 8 двоичных битов в растровом изображении. IE. 55 представляет двоичный шаблон 00110111.

Примечание. В растровом изображении может быть несколько фигур, а фигуры NO должны пересекаться. Однако могут быть формы, вложенные друг в друга без какого-либо пересечения.

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

Примечание. В конце вывода нет ни строки, ни пробела. Если какая-либо форма повторяется, вывод должен содержать столько повторений, сколько в растровом изображении. то есть. Если есть 2 квадрата и один треугольник, выход должен быть квадратным, квадратным, треугольным

Пример набора 1

Вход:

6 8

0 126 66 66 126 0

Выход: Прямоугольник

Пример Set 2

Вход:

6 16

0 0 120 120 72 144 73 32 123 192 0 0

Выход: параллелограмм, квадрат

Я написал этот код, чтобы я мог визуализировать растровое изображение и иметь 2 списка (растровое изображение в строках и столбцах)...

rows,cols=(int(i) for i in raw_input().split())
nums=[int(n) for n in raw_input().split()]
mr=[]
for i in range(0,len(nums),cols/8):
    row=''
    for j in range(i,i+cols/8):
        b=bin(nums[j])[2:]
        b='0'*(8-len(b))+b
        row+=b
    mr.append(row)
mc=[''.join([mr[i][j] for i in range(rows)]) for j in range(cols)]

Спасибо за ваше время... Пожалуйста, ответьте, если вы можете в Python, С++ или Ruby, так как это языки, которые я могу понять или даже алгоритмически...

Ответы

Ответ 1

Мой подход будет примерно таким:

  • Найдите первый черный пиксель (либо самый левый, либо самый верхний).
  • Проведите черный путь вправо и вниз (то есть, петля, пока не нажмете белый пиксель).

  • 3 случая:

    • Пути имеют одинаковую длину: квадрат или треугольник. Проверьте пиксель справа от нижнего пикселя, чтобы решить (черный: квадрат, белый: треугольник).
    • Пути имеют разную длину: прямоугольник или треугольник (? или всегда должны быть 45 градусов?). Проверьте пиксель справа от нижнего пикселя, чтобы решить (черный: прямоугольник, белый: треугольник).
    • Один из путей не существует: треугольник или параллелограмм. Предполагая, что путь вниз существовал: проверьте пиксель справа от нижнего пикселя, чтобы решить (черный: треугольник, белый: параллелограмм).

  • Удалите фигуру и повторите.

Вы просматриваете каждый пиксель только постоянное количество раз (не совсем уверен в этой константе), поэтому это должно выполняться со временем, линейным по количеству пикселей.