По заданному 2D массиву найдите в нем регионы

Question

Предположим, у нас есть следующий 2d массив:

2 1 2 2 1 1 
2 2 1 2 1 1 
2 1 3 2 1 1 
2 2 2 1 3 3 
2 2 1 1 3 3 
2 2 1 1 3 3 

Теперь я хочу найти смежные области в приведенном выше.Два местоположения принадлежат непрерывному региону, если между ними есть путь и их значения одинаковы.Более того, все узлы в пути также должны иметь одинаковое значение.Например, мы можем разделить вышеперечисленное на следующие 5 регионов:

A B A A D D 
A A B A D D 
A B C A D D 
A A A D E E
A A D D E E 
A A D D E E 

Вам разрешено идти по всем 8 направлениям.Я ищу реализацию в Java.Может кто-нибудь, пожалуйста, помогите мне с этим.Интерфейс выглядит примерно так:

VectorFeature returnComp(int matrix[][])

, где VectorFeature может быть следующим:

class VectorFeature{
  string region
  int numberForRegion
  int numOfElements

}

Я знаю идею о том, как это реализовать, но я ищу быстрое сообщение об ошибкебесплатная реализация в JAVA!

Answer 1

Вот что нужно сделать.

Первые превращают ваш двумерный массив в (в основном) 8-градусный график со следующим правилом:

e (i, j), если color_i = color_j для всех i, для всех j в 8 соседях.i

Представьте эти ребра в виде матрицы смежности A

Затем возьмите следующее поэлементное ИЛИ произведение

C = I ИЛИ ИЛИ A ^ 2 ИЛИ A ^ 3 ИЛИ... A ^ k

Где C - это или-произведение, которое имеет 1 в i, j, если есть путь от i до j на любом из шагов 0-k.

Теперь, наконец, возьмем мудрый элемент и-произведение

R = C AND C_transpose

Строка i из R имеет столбец в j, если i и j принадлежат одному и тому жесоставная часть.Тогда у вас есть ваши регионы, поскольку единственные пути, которые это будут представлять, - это пути, которые вы изначально представляли в своем 2D-массиве.И никакие края не пойдут между регионами.Но этот матричный продукт требует некоторого времени для вычисления, поэтому нам нужна альтернатива:

По причинам, которые я не буду касаться сходимости суммы вышеуказанной последовательности As, мыможно выбрать настраиваемый параметр альфа, чтобы эти ряды сходились, и мы можем найти приближение к R на

R '= обратное (I - альфа * A)

Это будет иметь тот же шаблонненулевые элементы, как в R, но гораздо проще вычислить.(Обратите внимание, что в то время как в R у вас будут 1 и 0, в R 'у вас будут 0 и не 0 (с плавающей точкой), поэтому вы все равно можете считывать регионы)

Вы можете сделать этона Яве.Но почему бы не использовать matlab?

Этот ответ был почти дословно (но не взят) из великой книги: Алгоритмы графов на языке линейной алгебры.Дж. Кепнер и Дж. Гилберт.

Answer 2

Вы можете сделать хуже, чем начинать с Википедии: Маркировка подключенных компонентов .