生长区域算法的php实现

在photoshop中我们常用的一个功能就是选择区域，用魔法棒选择工具点击图片上的一个点就会选中跟该点颜色一样的连续或非连续区域。这是怎么做到的呢？下面是我用php实生的区域生长算法。

<?php

/**
 * 找到生长区域
 *
 * @param array $arr  数据数组
 * @param array $seed 种子点
 * @return array
 */
function getGrowRegion($arr, $seed, $mode=4)
{
    $seed_value = $seed['value'];
    $queue = array();
    $label = array();
    if ($arr[$seed['y']][$seed['x']] == $seed_value)
    {
        $queue[] = $seed;
        $label[$seed['y']][$seed['x']] = 1;// 标记
    }

    // 判断该点4或8个方向上的值,如果未被标记就标记，并加入到队列中
    switch ($mode)
    {
    	case 4:
    	default:
    	    $directions = array(
        	    array(-1, 0),
        	    array(1, 0),
        	    array(0, -1),
        	    array(0, 1)
    	    );
    	    break;

    	case 8:
    	    $directions = array(
        	    array(-1, 0),
        	    array(1, 0),
        	    array(0, -1),
        	    array(0, 1),
        	    array(-1, -1),
        	    array(-1, 1),
        	    array(1, -1),
        	    array(1, 1),
    	    );
    	    break;
    }

    while(!empty($queue))
    {
        $current = array_shift($queue);
        foreach ($directions as $key => $val)
        {
            $y_idx = $current['y'] + $val[0];
            $x_idx = $current['x'] + $val[1];
            if (isset($arr[$y_idx][$x_idx]) && $arr[$y_idx][$x_idx] == $seed_value && !isset($label[$y_idx][$x_idx]))
            {
                $label[$y_idx][$x_idx] = 1;
                $queue[] = array('y' => $y_idx, 'x' => $x_idx);
            }
        }
    }
    return $label;
}

// 生长区域测试
$str = <<<EOT
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000011100000000000000
000000000000011100000000000000
000000000000011110000000000000
000000000000111110000000000000
000000000000110111000000000000
000000000000110111000000000000
000000000001110011000000000000
000000000001111111100000000000
000000000011111111100000000000
000000000011111111110000000000
000000000011000001110000000000
000000000111000000110000000000
000000000111000000111000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
EOT;

$data = preg_split('/[\r\n]+/', $str);// 切分成行数组

// 处理成二维坐标数组
$arr = array();
foreach ($data as $y => $val)
{
    $x_len = strlen($val);
    for ($x = 0; $x < $x_len; $x++)
    {
        $arr[$y][$x] = $val{$x};
    }
}

// 设置种子点，这里取左上角，value是要匹配的值
// 这里的意思就是以左上角为起点，所有值为0的点全部作为要匹配的区域
$seed = array('y' => 0, 'x' => 0, 'value' => '0');
$result = getGrowRegion($arr, $seed);

// 输出反转之后的字符串
foreach ($arr as $y => $rows)
{
    foreach ($rows as $x => $val)
    {
        if (isset($result[$y][$x]))
        {
            echo $result[$y][$x];
        }
        else
        {
            echo $val==1? 0 : 2;// 非生长点
        }
    }
    echo "\n";
}

运行后的输出结果如下：

111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111100011111111111111
111111111111100011111111111111
111111111111100001111111111111
111111111111000001111111111111
111111111111002000111111111111
111111111111002000111111111111
111111111110002200111111111111
111111111110000000011111111111
111111111100000000011111111111
111111111100000000001111111111
111111111100111110001111111111
111111111000111111001111111111
111111111000111111000111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111

可以看到原来为0的点全换成了1，但图形中间的点不受影响，我将其标记成了2。