Как найти определенную «фигуру» в двумерном массиве?

Question

orellero @orellero

Как найти определенную «фигуру» в двумерном массиве?

Привет!
Есть двумерный массив типа такого:

var matrix = new Array(
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
);

Требуется искать определенные "фигуры" внутри массива, например найти

[0, 0],
[0, 0]

или

[0],
[0],
[0, 0, 0]

Подскажите, возможно есть какие либо готовые алгоритмы для такого поиска?

Вопрос задан более трёх лет назад
2162 просмотра

3 комментария

Подписаться 2 Оценить 3 комментария

Всем спасибо за ответы!

Средний размер поля 50x50, может доходить до 200x200
Средний размер элемента 5 клеток, максимально 9
Ищутся именно нули.
Разных фигур около 20.
Какие габариты у искомых фигур? Они вписываются в квадрат 3*3?
Mrrl: нет, не вписываются, но максимальная сторона 6 клеток

Answer 1 · 2015-03-13 19:03:05

hit or miss transform
image processing/feature extraction/template matching
feature_detection

есть нечто похожее для библиотеки aforge c#, может почерпнете какие-нибудь идеи там

можно:
-искать длинную строку из фигуры
-построить интегральное изображение и искать охватывающий прямоугольник с суммой в пределах, зависящих от фигуры(дальше можно и Хаара, или что-то специфическое: уголок - разность квадратов)
-посчитать суммы по строкам и столбцам, искать проекции

решения в лоб:
-ходим фигурой(и, возможно, маской) по массиву:
4 цикла: 2 по координатам и 2 по фигуре
-ходим базовой точкой и массивом относительных смещений и значений:
3 цикла: 2 по координатам и 1 по точкам

Как найти определенную «фигуру» в двумерном массиве?

Войдите на сайт