Выполните итерацию по 2d массиву логических значений и оставьте только самый большой смежный 2D-объект из двоичных объектов.

Question

Выполните итерацию по 2d массиву логических значений и оставьте только самый большой смежный 2D-объект из двоичных объектов.

Итак, вопрос несколько неловко сформулирован, но я надеюсь, что это прояснит ситуацию.

У меня есть этот образец 2d массив.

$array = array(
array(1, 0, 0, 0, 1, 0, 0, 1),
array(0, 0, 1, 1, 1, 1, 0, 1),
array(0, 1, 1, 0, 1, 0, 0, 0),
array(0, 1, 1, 0, 0, 0, 1, 0),
array(1, 0, 0, 0, 1, 1, 1, 1),
array(0, 1, 1, 0, 1, 0, 1, 0),
array(0, 0, 0, 0, 0, 0, 0, 1)
);

Когда повторяется по строкам (и заканчивается каждой строкой с \ n), и для каждой строки, затем повторяется по столбцу, это будет отображать что-то вроде этого: (░░ = 0, ▓▓ = 1)

    ▓▓░░░░░░▓▓░░░░▓▓
░░░░▓▓▓▓▓▓▓▓░░▓▓
░░▓▓▓▓░░▓▓░░░░░░
░░▓▓▓▓░░░░░░▓▓░░
▓▓░░░░░░▓▓▓▓▓▓▓▓
░░▓▓▓▓░░▓▓░░▓▓░░
░░░░░░░░░░░░░░▓▓

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

    ░░░░░░░░▓▓░░░░░░
░░░░▓▓▓▓▓▓▓▓░░░░
░░▓▓▓▓░░▓▓░░░░░░
░░▓▓▓▓░░░░░░░░░░
▓▓░░░░░░░░░░░░░░
░░▓▓▓▓░░░░░░░░░░
░░░░░░░░░░░░░░░░

Мой первоначальный подход состоял в том, чтобы:

Присвойте каждой ▓▓ ячейке уникальный номер (будь то абсолютно случайный или текущий номер итерации):
```
01      02    03
04050607  08
0910  11
1213      14
15      16171819
2021  22  23
24
```
Итерация по массиву МНОГИЕ раз: каждая итерация, каждая ячейка принимает наибольшее уникальное число среди своих соседей. Цикл будет продолжаться бесконечно, пока не будет обнаружено никаких изменений между текущим состоянием и предыдущим состоянием. После последней итерации результат будет следующим:
```
01      21    08
21212121  08
2121  21
2121      24
21      24242424
2121  24  24
24
```
Теперь все сводится к подсчету значения, которое встречается чаще всего. Затем, повторяя еще раз, чтобы повернуть все ячейки, значение которых не является самой популярной, в 0, получая желаемый результат.

Тем не менее, я чувствую, что это довольно обходной и вычислительно сложный подход для такой простой задачи, и должен быть лучший путь. Любые идеи будут с благодарностью, ура!

Бонусные точки: разделите все капли на массив двумерных массивов, упорядоченных по количеству ячеек, чтобы мы могли сделать что-то и с самым маленьким шариком, тоже

4

2d algorithm arrays cellular-automata php

Решение

Другие решения

Я могу думать только о нескольких незначительных улучшениях:

Держите связанный список не пустых полей. На шаге 2 вам не нужно трогать n² matrix-elements, вам нужно только касаться тех, что в вашем связанном списке. Который может быть намного меньше в зависимости от того, насколько редка ваша матрица.
Вам нужно только сравнить направо, вправо-вниз, влево-вниз и вниз. В противном случае другие направления уже проверены из прежней строки / столбца. Что я имею в виду: когда я больше своего правого соседа, я уже могу изменить номер правого соседа. (то же самое для вниз и вправо). Это вдвое меньше сравнений.

1

Если размер вашего массива не велик и память не будет проблемой, возможно, рекурсивное решение будет быстрее. Я нашел алгоритм C ++, который делает это здесь:
https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/

0

Источник

Accepted Answer

Всегда весело, эти проблемы. И сделано раньше, поэтому я дам свой код здесь, может быть, вы можете использовать некоторые из них. Это в основном следует за каждой формой, глядя на ячейку и окружающие ее 8 ячеек, и, если они соединяются, переходят в соединительную ячейку, смотрят снова и так далее …

<?php
$shape_nr=1;
$ln_max=count($array);
$cl_max=count($array[0]);
$done=[];

//LOOP ALL CELLS, GIVE 1's unique number
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;
$array[$ln][$cl] = ++$shape_nr;
}}

//DETECT SHAPES
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;

$shape_nr=$array[$ln][$cl];
if(in_array($shape_nr,$done))continue;

look_around($ln,$cl,$ln_max,$cl_max,$shape_nr,$array);
//SET SHAPE_NR to DONE, no need to look at that number again
$done[]=$shape_nr;
}}

//LOOP THE ARRAY and COUNT SHAPENUMBERS
$res=array();
for($ln=0;$ln<$ln_max;++$ln){
for($cl=0;$cl<$cl_max;++$cl){
if($array[$ln][$cl]===0)continue;
if(!isset($res[$array[$ln][$cl]]))$res[$array[$ln][$cl]]=1;
else $res[$array[$ln][$cl]]++;
}}

//get largest shape
$max = max($res);
$shape_value_max = array_search ($max, $res);

//get smallest shape
$min = min($res);
$shape_value_min = array_search ($min, $res);

// recursive function: detect connecting cells
function look_around($ln,$cl,$ln_max,$cl_max,$nr,&$array){
//create mini array
$mini=mini($ln,$cl,$ln_max,$cl_max);
if($mini===false)return false;

//loop surrounding cells
foreach($mini as $v){
if($array[$v[0]][$v[1]]===0){continue;}
if($array[$v[0]][$v[1]]!==$nr){
// set shape_nr of connecting cell
$array[$v[0]][$v[1]]=$nr;

// follow the shape
look_around($v[0],$v[1],$ln_max,$cl_max,$nr,$array);
}
}
return $nr;
}

// CREATE ARRAY WITH THE 9 SURROUNDING CELLS
function mini($ln,$cl,$ln_max,$cl_max){
$look=[];
$mini=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
foreach($mini as $v){
if( $ln + $v[0] >= 0 &&
$ln + $v[0] < $ln_max &&
$cl + $v[1] >= 0 &&
$cl + $v[1] < $cl_max
){
$look[]=[$ln + $v[0], $cl + $v[1]];
}
}

if(count($look)===0){return false;}
return $look;
}

Вот скрипка

1