php - 遍历二维 bool 数组，只留下最大的连续 "2D blob of ones"

Question

好吧，这个问题措辞有点尴尬，但我希望这能解决问题。

我有这个示例二维数组。

$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)

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

但我想做的是“分析”数组并只留下 1 个连续的形状(“单元格”最多的那个)，在这个例子中，结果将是:

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

我最初的方法是:

1. 为每个 ↓↓ 单元格分配一个唯一的数字(可以是完全随机的，也可以是当前迭代数):

   01      02    03
       04050607  08
     0910  11      
     1213      14  
   15      16171819
     2021  22  23  
                 24
   

2. 多次遍历数组:每次迭代，每个 ↓↓ 单元格都假定其相邻单元格中最大的唯一编号。循环将无限期地继续下去，直到在当前状态和先前状态之间没有检测到变化。最后一次迭代后，结果将是这样的:

   01      21    08
       21212121  08
     2121  21      
     2121      24  
   21      24242424
     2121  24  24  
                 24
   

   现在一切都归结为计算出现次数最多的值。然后，再次迭代，将所有值不是最受欢迎的单元格变为 0，得到我想要的结果。

但是，我觉得对于这样一个简单的任务来说，这是一种相当迂回且计算量很大的方法，必须有更好的方法。任何想法将不胜感激，干杯!

加分点:将所有 blob 分成一个二维数组，按单元格数排序，这样我们也可以用最小的 blob 做一些事情

Answer 1

总是很有趣，这些问题。之前做过，所以我会在这里转储我的代码，也许你可以使用其中的一些。这基本上通过查看一个单元格及其周围的 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;
    }

Here's a fiddle