grid_skeletonize.cpp

这是一个GPS相关的程序

	do
	{
		DataObject_Update(pResult, 0, 1, true);

		nChanges	= 0;

		for(i=0; i<8; i++)
		{
			nChanges	+= Standard_Step(i, pPrev, pNext);

			pTemp		= pPrev;
			pPrev		= pNext;
			pNext		= pTemp;
		}
	}
	while( nChanges > 0 && Process_Get_Okay(true) );

	//-----------------------------------------------------
	if( pNext == pResult )
	{
		delete(pPrev);
	}
	else
	{
		pResult->Assign(pNext);

		delete(pNext);
	}
}

//---------------------------------------------------------
int CGrid_Skeletonize::Standard_Step(int iDir, CSG_Grid *pPrev, CSG_Grid *pNext)
{
	bool	z[8], bRemove;

	int		x, y, nNeighbours, nChanges;

	pNext->Assign();

	nChanges	= 0;

	for(y=0; y<Get_NY() && Process_Get_Okay(false); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			if( pPrev->asByte(x, y) )
			{
				bRemove		= false;
				nNeighbours	= Get_Neighbours(x, y, pPrev, z);

				if( nNeighbours > 1 && nNeighbours < 6 )
				{
					bRemove	= Standard_Check(iDir, z);
				}

				if( bRemove )
				{
					nChanges++;
				}
				else
				{
					pNext->Set_Value(x, y, 1);
				}
			}
		}
	}

	return( nChanges );
}

//---------------------------------------------------------
inline bool CGrid_Skeletonize::Standard_Check(int iDir, bool z[8])
{
	bool	bRemove;

	switch( iDir )
	{
	default:
		bRemove	= false;
		break;

	case 0:
		bRemove	=	!z[7] && !z[0] && !z[1]
				&&	 z[3] &&  z[4] &&  z[5];
		break;

	case 1:
		bRemove	=	!z[0] && !z[1] && !z[2]
				&&	 z[4]      &&      z[6];
		break;

	case 2:
		bRemove	=	!z[1] && !z[2] && !z[3]
				&&	 z[5] &&  z[6] &&  z[7];
		break;

	case 3:
		bRemove	=	!z[2] && !z[3] && !z[4]
				&&	 z[6]      &&      z[0];
		break;

	case 4:
		bRemove	=	!z[3] && !z[4] && !z[5]
				&&	 z[7] &&  z[0] &&  z[1];
		break;

	case 5:
		bRemove	=	!z[4] && !z[5] && !z[6]
				&&	 z[0]      &&      z[2];
		break;

	case 6:
		bRemove	=	!z[5] && !z[6] && !z[7]
				&&	 z[1] &&  z[2] &&  z[3];
		break;

	case 7:
		bRemove	=	!z[6] && !z[7] && !z[0]
				&&	 z[2]      &&      z[4];
		break;
	}

	return( bRemove );
}


///////////////////////////////////////////////////////////
//														 //
//						Hilditch						 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
void CGrid_Skeletonize::Hilditch_Execute(void)
{
	int		nChanges;

	CSG_Grid	*pPrev, *pNext, *pTemp, *pNC_Gaps;

	//-----------------------------------------------------
	pPrev		= pResult;
	pNext		= SG_Create_Grid(pPrev);
	pNC_Gaps	= SG_Create_Grid(pPrev, GRID_TYPE_Char);

	//-----------------------------------------------------
	do
	{
		DataObject_Update(pResult, 0, 1, true);

		nChanges	= Hilditch_Step(pPrev, pNext, pNC_Gaps);

		pTemp		= pPrev;
		pPrev		= pNext;
		pNext		= pTemp;
	}
	while( nChanges > 0 && Process_Get_Okay(true) );

	//-----------------------------------------------------
	delete(pNC_Gaps);

	if( pNext == pResult )
	{
		delete(pPrev);
	}
	else
	{
		pResult->Assign(pNext);

		delete(pNext);
	}
}

//---------------------------------------------------------
int CGrid_Skeletonize::Hilditch_Step(CSG_Grid *pPrev, CSG_Grid *pNext, CSG_Grid *pNC_Gaps)
{
	bool	z[8], bPrev, bRemove;

	int		x, y, i, nChanges, nNeighbours;

	//-----------------------------------------------------
	for(y=0; y<Get_NY() && Process_Get_Okay(false); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			nChanges	= 0;

			if( pPrev->asByte(x, y) && Get_Neighbours(x, y, pPrev, z) > 0 )
			{
				for(i=0, bPrev=z[7]; i<8; i++)
				{
					if( bPrev == false && z[i] == true )
					{
						nChanges++;
					}

					bPrev	= z[i];
				}
			}

			pNC_Gaps->Set_Value(x, y, nChanges);
		}
	}

	//-----------------------------------------------------
	pNext->Assign();

	nChanges	= 0;

	for(y=0; y<Get_NY() && Process_Get_Okay(false); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			if( pPrev->asByte(x, y) )
			{
				bRemove		= false;
				nNeighbours	= Get_Neighbours(x, y, pPrev, z);

				//-----------------------------------------
				if( 2 <= nNeighbours && nNeighbours <= 6 && pNC_Gaps->asByte(x, y) == 1 )
				{
					bRemove	=	Hilditch_Check(pNC_Gaps, x, y, 0, z)
							||	Hilditch_Check(pNC_Gaps, x, y, 2, z)
							||	Hilditch_Check(pNC_Gaps, x, y, 4, z)
							||	Hilditch_Check(pNC_Gaps, x, y, 6, z)
							;
				}

				//-----------------------------------------
				if( bRemove )
				{
					nChanges++;
				}
				else
				{
					pNext->Set_Value(x, y, true);
				}
			}
		}
	}

	//-----------------------------------------------------
	return( nChanges );
}

//---------------------------------------------------------
inline bool CGrid_Skeletonize::Hilditch_Check(CSG_Grid *pNC_Gaps, int x, int y, int i0, bool z[8])
{
	int		ix, iy, i2, i4, i6;

	i2		= (i0 + 2) % 8;
	i4		= (i0 + 4) % 8;
	i6		= (i0 + 6) % 8;

	if( z[i0] || z[i2] || z[i6] )
	{
		ix		= Get_System()->Get_xTo(i0, x);
		iy		= Get_System()->Get_yTo(i0, y);

		if( pNC_Gaps->is_InGrid(ix, iy) && pNC_Gaps->asByte(ix, iy) == 1 )
		{
			return( false );
		}
	}

	if( z[i0] || z[i2] || z[i4] )
	{
		ix		= Get_System()->Get_xTo(i2, x);
		iy		= Get_System()->Get_yTo(i2, y);

		if( pNC_Gaps->is_InGrid(ix, iy) && pNC_Gaps->asByte(ix, iy) == 1 )
		{
			return( false );
		}
	}

	return( true );
}


///////////////////////////////////////////////////////////
//														 //
//					Channel Detection					 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
void CGrid_Skeletonize::SK_Execute(void)
{
	int		x, y, i, ix, iy, n,
			Convergence, NB[8];

	double	z, iz;

	CSG_Grid	*pInput;

	//-----------------------------------------------------
	Convergence	= Parameters("CONVERGENCE")->asInt();
	pInput		= Parameters("INPUT")->asGrid();

	pResult->Assign();


	//-----------------------------------------------------
	// 1.) Find definitive channel points...

	for(y=0; y<Get_NY() && Set_Progress(y); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			z	= pInput->asDouble(x, y);
			n	= 0;

			for(i=0; i<8; i++)
			{
				ix	= Get_System()->Get_xTo(i, x);
				iy	= Get_System()->Get_yTo(i, y);

				if( pInput->is_InGrid(ix, iy) && z < pInput->asDouble(ix, iy) )
				{
					n++;
				}
			}

			if( Convergence > n )
			{
				pResult->Set_Value(x, y, 2);
			}
		}
	}


	//-----------------------------------------------------
	// 2.) Find channels...

	for(n=0; n<Get_NCells() && Set_Progress_NCells(n); n++)
	{	
		pInput->Get_Sorted(n, x, y);	// Von oben nach unten...

		z	= pInput->asDouble(x, y);

		for(i=0; i<8; i++)
		{
			ix	= Get_System()->Get_xTo(i,x);
			iy	= Get_System()->Get_yTo(i,y);

			if( !pInput->is_InGrid(ix, iy) )
			{
				NB[i]	= skNE;
			}
			else
			{
				iz	= pInput->asDouble(ix, iy);

				if( iz < z )
				{
					NB[i]	= skNE;
				}
				else if( iz > z && pResult->asByte(ix, iy) )
				{
					NB[i]	= skJA;
				}
				else
				{
					NB[i]	= 0;
				}
			}
		}

		if( SK_Connectivity(NB) )
		{
			pResult->Set_Value(x, y, 1);
		}
	}


	//-----------------------------------------------------
	/*/ 3.) Filter...

	Lock_Create();

	for(y=0; y<Get_NY() && Set_Progress(y); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			SK_Filter(x, y);
		}
	}

	for(y=0; y<Get_NY() && Set_Progress(y); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			if( Lock_Get(x, y) )
			{
				pResult->Set_Value(x, y, 0);
			}
		}
	}

	Lock_Destroy();/**/
}

//---------------------------------------------------------
int CGrid_Skeletonize::SK_Connectivity(int NB[8])
{
	int		i;

	for(i=0; i<8; i+=2)
	{
		if( !NB[i] )
		{
			if( !NB[(i+2)%8] )	// Diagonal Connection
			{
			/*
				if( ( NB[(i+1)%8]	)
				&&	( NB[(i+3)%8] || NB[(i+4)%8] || NB[(i+5)%8] || NB[(i+6)%8] || NB[(i+7)%8] ) )
					return(1);
				*/

				///*
				if( ( NB[(i+1)%8]==skNE	)
				&&	( NB[(i+3)%8]==skJA || NB[(i+4)%8]==skJA || NB[(i+5)%8]==skJA || NB[(i+6)%8]==skJA || NB[(i+7)%8]==skJA ) )
					return(1);

				if( ( NB[(i+1)%8]==skJA	)
				&&	( NB[(i+3)%8]==skNE || NB[(i+4)%8]==skNE || NB[(i+5)%8]==skNE || NB[(i+6)%8]==skNE || NB[(i+7)%8]==skNE ) )
					return(1);
				//*/
			}

			//---Orthogonal-Connection---------------------------------
			if(!NB[(i+4)%8])
			{	/*
				if(	( NB[(i+1)%8] || NB[(i+2)%8] || NB[(i+3)%8] )
				&&	( NB[(i+5)%8] || NB[(i+6)%8] || NB[(i+7)%8] ) )
					return(1);
				*/

				///*
				if(	( NB[(i+1)%8]==skJA || NB[(i+2)%8]==skJA || NB[(i+3)%8]==skJA )
				&&	( NB[(i+5)%8]==skNE || NB[(i+6)%8]==skNE || NB[(i+7)%8]==skNE ) )
					return(1);

				if(	( NB[(i+1)%8]==skNE || NB[(i+2)%8]==skNE || NB[(i+3)%8]==skNE )
				&&	( NB[(i+5)%8]==skJA || NB[(i+6)%8]==skJA || NB[(i+7)%8]==skJA ) )
					return(1);
				//*/
			}
		}
	}

	return( 0 );
}

//---------------------------------------------------------
bool CGrid_Skeletonize::SK_Filter(int x, int y)
{
	bool	z[8];

	if( !pResult->asByte(x, y) && Get_Neighbours(x, y, pResult, z) == 4 )
	{
		if( z[0] && z[2] && z[4] && z[6] )
		{
			Lock_Set(Get_System()->Get_xTo(0, x), Get_System()->Get_yTo(0, y));
			Lock_Set(Get_System()->Get_xTo(2, x), Get_System()->Get_yTo(2, y));
			Lock_Set(Get_System()->Get_xTo(4, x), Get_System()->Get_yTo(4, y));
			Lock_Set(Get_System()->Get_xTo(6, x), Get_System()->Get_yTo(6, y));

			return( true );
		}
	}

	return( false );
}