生長區域算法的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。