分水岭算法求解析
void CWaterShedDoc::FloodVincent(MyImageGraPt *imiarr, INT *graddarr, INT minh, INT maxh, INT *flagarr, INT &outrgnumber)
{
const INT INIT = -2;
const INT MASK = -1;
const INT WATERSHED = 0;
INT h = 0;
INT imagelen = imageWidth * imageHeight;
for (INT i=0; i<imagelen; i++)
{
flagarr[i] = INIT;
}
//memset(flagarr, INIT, sizeof(INT)*imagelen);
INT* imd = new INT[imagelen];//距离数组，直接存取；
for (i=0; i<imagelen; i++)
{
imd[i] = 0;
}
//memset(imd, 0, sizeof(INT)*imagelen);
std::queue <int> myqueue;
INT curlabel = 0;//各盆地标记；
for (h=minh; h<=maxh; h++)
{
INT stpos = graddarr[h];
INT edpos = graddarr[h+1];
for (INT ini=stpos; ini<edpos; ini++)
{
INT x = imiarr[ini].x;
INT y = imiarr[ini].y;
INT ipos = y*imageWidth + x;
flagarr[ipos] = MASK;
//以下检查该点邻域是否已标记属于某区或分水岭，若是，则将该点加入fifo;
INT left = ipos - 1;
if (x-1>=0)
{
if (flagarr[left]>=0)
{
imd[ipos] = 1;
myqueue.push(ipos);//点位置压入fifo;
continue;
}
}
INT right = ipos + 1;
if (x+1<imageWidth)
{
if (flagarr[right]>=0)
{
imd[ipos] = 1;
myqueue.push(ipos);//点位置压入fifo;
continue;
}
}
INT up = ipos - imageWidth;
if (y-1>=0)
{
if (flagarr[up]>=0)
{
imd[ipos] = 1;
myqueue.push(ipos);//点位置压入fifo;
continue;
}
}
INT down = ipos + imageWidth;
if (y+1<imageHeight)
{
if (flagarr[down]>=0)
{
imd[ipos] = 1;
myqueue.push(ipos);//点位置压入fifo;
continue;
}
}
}
//以下根据先进先出队列扩展现有盆地；
INT curdist = 1; myqueue.push(-99);//特殊标记；
while (TRUE)
{
INT p = myqueue.front();
myqueue.pop();
if (p == -99)
{
if ( myqueue.empty() )
{
break;
}else
{
myqueue.push(-99);
curdist = curdist + 1;
p = myqueue.front();
myqueue.pop();
}
}
//以下找p的邻域；
INT y = (INT) (p/imageWidth);
INT x = p - y*imageWidth;
INT left = p - 1;
if (x-1>=0)
{
if ( ( (imd[left]<curdist) && flagarr[left]>0)
|| (flagarr[left]==0) )
{
if ( flagarr[left]>0 )
{
//ppei属于某区域（不是分水岭）；
if ( (flagarr[p]==MASK)
|| (flagarr[p]==WATERSHED) )
{
//将其设为邻点所属区域；
flagarr[p] = flagarr[left];
}else if (flagarr[p]!=flagarr[left])
{
//原来赋的区与现在赋的区不同，设为分水岭；
//flagarr[p] = WATERSHED;
}
}else if (flagarr[p]==MASK)//ppei为分岭；
{
flagarr[p] = WATERSHED;
}
}else if ( (flagarr[left]==MASK) && (imd[left]==0) )
//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
{
imd[left] = curdist + 1; myqueue.push(left);
}
}
INT right = p + 1;
if (x+1<imageWidth)
{
if ( ( (imd[right]<curdist) && flagarr[right]>0)
|| (flagarr[right]==0) )
{
if ( flagarr[right]>0 )
{
//ppei属于某区域（不是分水岭）；
if ( (flagarr[p]==MASK)
|| (flagarr[p]==WATERSHED) )
{
//将其设为邻点所属区域；
flagarr[p] = flagarr[right];
}else if (flagarr[p]!=flagarr[right])
{
//原来赋的区与现在赋的区不同，设为分水岭；
//flagarr[p] = WATERSHED;
}
}else if (flagarr[p]==MASK)//ppei为分岭；
{
flagarr[p] = WATERSHED;
}
}else if ( (flagarr[right]==MASK) && (imd[right]==0) )
//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
{
imd[right] = curdist + 1; myqueue.push(right);
}
}
INT up = p - imageWidth;
if (y-1>=0)
{
if ( ( (imd[up]<curdist) && flagarr[up]>0)
|| (flagarr[up]==0) )
{
if ( flagarr[up]>0 )
{
//ppei属于某区域（不是分水岭）；
if ( (flagarr[p]==MASK)
|| (flagarr[p]==WATERSHED) )
{
//将其设为邻点所属区域；
flagarr[p] = flagarr[up];
}else if (flagarr[p]!=flagarr[up])
{
//原来赋的区与现在赋的区不同，设为分水岭；
//flagarr[p] = WATERSHED;
}
}else if (flagarr[p]==MASK)//ppei为分岭；
{
flagarr[p] = WATERSHED;
}
}else if ( (flagarr[up]==MASK) && (imd[up]==0) )
//ppei中已MASK的点，但尚未标记（即不属某区也不是分水岭）;
{
imd[up] = curdist + 1; myqueue.push(up);
}
}
INT down = p + imageWidth;
if (y+1<imageHeight)
{
if ( ( (imd[down]<curdist) && flagarr[down]>0)
|| (flagarr[down]==0) )
{
if ( flagarr[down]>0 )
{
//ppei属于某区域（不是分水岭）；
if ( (flagarr[p]==MASK)
|| (flagarr[p]==WATERSHED) )
{
//将其设为邻点所属区域；
flagarr[p] = flagarr[down];
}else if (flagarr[p]!=flagarr[down])
{
//原来赋的区与现在赋的区不同，设为分水岭；
//flagarr[p] = WATERSHED;
}
}else if (flagarr[p]==MASK)//ppei为分岭；
{
flagarr[p] = WATERSHED;
}
}else if ( (flagarr[down]==MASK) && (imd[down]==0) )
//ppei中已MASK的点，但尚未标记（既不属某区也不是分水岭）;
{
imd[down] = curdist + 1; myqueue.push(down);
}
}
}//以上现有盆地的扩展；
