grid_skeletonize.cpp

这是一个GPS相关的程序

///////////////////////////////////////////////////////////
//                                                       //
//                         SAGA                          //
//                                                       //
//      System for Automated Geoscientific Analyses      //
//                                                       //
//                    Module Library:                    //
//                  Grid_Discretisation                  //
//                                                       //
//-------------------------------------------------------//
//                                                       //
//                 Grid_Skeletonize.cpp                  //
//                                                       //
//                 Copyright (C) 2003 by                 //
//                      Olaf Conrad                      //
//                                                       //
//-------------------------------------------------------//
//                                                       //
// This file is part of 'SAGA - System for Automated     //
// Geoscientific Analyses'. SAGA is free software; you   //
// can redistribute it and/or modify it under the terms  //
// of the GNU General Public License as published by the //
// Free Software Foundation; version 2 of the License.   //
//                                                       //
// SAGA is distributed in the hope that it will be       //
// useful, but WITHOUT ANY WARRANTY; without even the    //
// implied warranty of MERCHANTABILITY or FITNESS FOR A  //
// PARTICULAR PURPOSE. See the GNU General Public        //
// License for more details.                             //
//                                                       //
// You should have received a copy of the GNU General    //
// Public License along with this program; if not,       //
// write to the Free Software Foundation, Inc.,          //
// 59 Temple Place - Suite 330, Boston, MA 02111-1307,   //
// USA.                                                  //
//                                                       //
//-------------------------------------------------------//
//                                                       //
//    e-mail:     [e-mail]                   //
//                                                       //
//    contact:    Olaf Conrad                            //
//                Institute of Geography                 //
//                University of Goettingen               //
//                Goldschmidtstr. 5                      //
//                37077 Goettingen                       //
//                Germany                                //
//                                                       //
///////////////////////////////////////////////////////////

//---------------------------------------------------------


///////////////////////////////////////////////////////////
//														 //
//														 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
#include "Grid_Skeletonize.h"

//---------------------------------------------------------
#define	skNE			1
#define skJA			2

#define SEGMENT_END		1
#define SEGMENT_NODE	2
#define SEGMENT_LOCKED	3


///////////////////////////////////////////////////////////
//														 //
//														 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
CGrid_Skeletonize::CGrid_Skeletonize(void)
{
	Set_Name		(_TL("Grid Skeletonization"));

	Set_Author		(_TL("Copyrights (c) 2002 by Olaf Conrad"));

	Set_Description	(_TW(
		"Simple skeletonisation methods for grids.\n"
	));

	Parameters.Add_Grid(
		NULL, "INPUT"			, _TL("Grid"),
		_TL(""),
		PARAMETER_INPUT
	);

	Parameters.Add_Grid(
		NULL, "RESULT"			, _TL("Skeleton"),
		_TL(""),
		PARAMETER_OUTPUT, true, GRID_TYPE_Char
	);

	Parameters.Add_Shapes(
		NULL, "VECTOR"			, _TL("Skeleton"),
		_TL(""), PARAMETER_OUTPUT_OPTIONAL
	);

	Parameters.Add_Choice(
		NULL, "METHOD"			, _TL("Method"),
		_TL(""),

		CSG_String::Format(SG_T("%s|%s|%s|"),
			_TL("Standard"),
			_TL("Hilditch's Algorithm"),
			_TL("Channel Skeleton")
		), 0
	);

	Parameters.Add_Choice(
		NULL, "INIT_METHOD"		, _TL("Initialisation"),
		_TL(""),

		CSG_String::Format(SG_T("%s|%s|"),
			_TL("Less than"),
			_TL("Greater than") 
		),1
	);

	Parameters.Add_Value(
		NULL, "INIT_THRESHOLD"	, _TL("Threshold (Init.)"),
		_TL(""),
		PARAMETER_TYPE_Double
	);

	Parameters.Add_Value(
		NULL, "CONVERGENCE"		, _TL("Convergence"),
		_TL(""),
		PARAMETER_TYPE_Int, 3
	);
}

//---------------------------------------------------------
CGrid_Skeletonize::~CGrid_Skeletonize(void)
{}


///////////////////////////////////////////////////////////
//														 //
//														 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
bool CGrid_Skeletonize::On_Execute(void)
{
	int			n, Initiation;
	double		Threshold;
	CSG_Grid	*pInput;

	//-----------------------------------------------------
	pInput		= Parameters("INPUT")			->asGrid();
	pResult		= Parameters("RESULT")			->asGrid();

	Initiation	= Parameters("INIT_METHOD")		->asInt();
	Threshold	= Parameters("INIT_THRESHOLD")	->asDouble();

	DataObject_Set_Colors(pResult, 3, SG_COLORS_BLACK_WHITE, true);
	pResult->Assign(0.0);

	//-----------------------------------------------------
	for(n=0; n<Get_NCells(); n++)
	{
		switch( Initiation )
		{
		case 0: default:
			if( pInput->asDouble(n) < Threshold )
			{
				pResult->Set_Value(n, 1);
			}
			break;

		case 1:
			if( pInput->asDouble(n) > Threshold )
			{
				pResult->Set_Value(n, 1);
			}
			break;
		}
	}

	//-----------------------------------------------------
	switch( Parameters("METHOD")->asInt() )
	{
	case 0:	default:
		Standard_Execute();
		break;

	case 1:
		Hilditch_Execute();
		break;

	case 2:
		SK_Execute();
		break;
	}

	//-------------------------------------------------
	if( Parameters("VECTOR")->asShapes() )
	{
		Vectorize(Parameters("VECTOR")->asShapes());
	}

	if( 1 )
	{
		for(n=0; n<Get_NCells(); n++)
		{
			switch( Initiation )
			{
			case 0: default:
				if( pInput->asDouble(n) < Threshold )
				{
					pResult->Add_Value(n, 1);
				}
				break;

			case 1:
				if( pInput->asDouble(n) > Threshold )
				{
					pResult->Add_Value(n, 1);
				}
				break;
			}
		}
	}

	//-----------------------------------------------------
	return( true );
}


///////////////////////////////////////////////////////////
//														 //
//						Helpers							 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
int CGrid_Skeletonize::Get_Neighbours(int x, int y, CSG_Grid *pGrid, bool Neighbours[8])
{
	int		i, ix, iy, nNeighbours;

	nNeighbours	= 0;

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

		if( pGrid->is_InGrid(ix, iy) && pGrid->asByte(ix, iy) )
		{
			Neighbours[i]	= true;

			nNeighbours++;
		}
		else
		{
			Neighbours[i]	= false;
		}
	}

	return( nNeighbours );
}


///////////////////////////////////////////////////////////
//														 //
//					Vectorization						 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
int CGrid_Skeletonize::Vectorize(CSG_Shapes *pShapes)
{
	bool	z[8], bPrev;

	int		x, y, i, ix, iy, n, nSegments;

	double	xMin, yMin, dx, dy;

	CSG_Shape	*pShape;

	//-----------------------------------------------------
	pShapes->Create(SHAPE_TYPE_Line, _TL("Skeleton"));
	pShapes->Get_Table().Add_Field("ID", TABLE_FIELDTYPE_Int);

	Lock_Create();

	//-----------------------------------------------------
	for(y=0; y<Get_NY() && Process_Get_Okay(false); y++)
	{
		for(x=0; x<Get_NX(); x++)
		{
			if( pResult->asByte(x, y) )
			{
				n	= Get_Neighbours(x, y, pResult, z);
				
				if( n == 1 )
				{
					Lock_Set(x, y, SEGMENT_END);
				}
				else if( n > 1 )
				{
					n	= 0;

					for(i=0, bPrev=z[7]; i<8; i++)
					{
						if( bPrev == false && z[i] == true )
						{
							n++;
						}

						bPrev	= z[i];
					}

					if( n > 2 )
					{
						Lock_Set(x, y, SEGMENT_NODE);
					}
				}
			}
		}
	}

	//-----------------------------------------------------
	nSegments	= 0;

	for(y=0; y<Get_NY() && Process_Get_Okay(false); y++)
	{
		dx			= pResult->Get_Cellsize();
		xMin		= pResult->Get_XMin();// + 0.5 * dx;
		dy			= pResult->Get_Cellsize();
		yMin		= pResult->Get_YMin();// + 0.5 * dy;

		for(x=0; x<Get_NX(); x++)
		{
			if( Lock_Get(x, y) == SEGMENT_NODE || Lock_Get(x, y) == SEGMENT_END )
			{
				Lock_Set(x, y, SEGMENT_LOCKED);

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

					if( pResult->is_InGrid(ix, iy) && pResult->asByte(ix, iy) && !Lock_Get(ix, iy) )
					{
						pShape	= pShapes->Add_Shape();
						pShape->Get_Record()->Set_Value(0, ++nSegments);
						pShape->Add_Point(xMin + dx * (double)x, yMin + dy * (double)y);

						Vectorize_Trace(ix, iy, pShape);
					}
				}
			}
		}
	}

	//-----------------------------------------------------
	Lock_Destroy();

	Message_Dlg(CSG_String::Format(SG_T("%d %s\n"), nSegments, _TL("segments identified")), Get_Name());

	return( nSegments );
}

//---------------------------------------------------------
bool CGrid_Skeletonize::Vectorize_Trace(int x, int y, CSG_Shape *pShape)
{
	bool	bContinue;

	int		i, ix, iy, iNext;

	double	xMin, yMin, dx, dy;

	//-----------------------------------------------------
	dx			= pResult->Get_Cellsize();
	xMin		= pResult->Get_XMin();// + 0.5 * dx;
	dy			= pResult->Get_Cellsize();
	yMin		= pResult->Get_YMin();// + 0.5 * dy;

	bContinue	= true;

	do
	{
		pShape->Add_Point(xMin + dx * (double)x, yMin + dy * (double)y);

		if( Lock_Get(x, y) == SEGMENT_NODE || Lock_Get(x, y) == SEGMENT_END )
		{
			bContinue	= false;
		}
		else
		{
			Lock_Set(x, y, SEGMENT_LOCKED);

			iNext	= -1;

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

				if( pResult->is_InGrid(ix, iy) && pResult->asByte(ix, iy) && Lock_Get(ix, iy) != SEGMENT_LOCKED )
				{
					iNext	= i;

					if( Lock_Get(ix, iy) == SEGMENT_NODE )
					{
						break;
					}
				}
			}

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

					if( pResult->is_InGrid(ix, iy) && pResult->asByte(ix, iy) && Lock_Get(ix, iy) != SEGMENT_LOCKED )
					{
						iNext	= i;

						if( Lock_Get(ix, iy) == SEGMENT_NODE )
						{
							break;
						}
					}
				}
			}

			if( iNext < 0 )
			{
				bContinue	= false;
			}
			else
			{
				x	+= Get_System()->Get_xTo(iNext);
				y	+= Get_System()->Get_yTo(iNext);
			}
		}
	}
	while( bContinue );

	//-----------------------------------------------------
	return( true );
}


///////////////////////////////////////////////////////////
//														 //
//						Standard						 //
//														 //
///////////////////////////////////////////////////////////

//---------------------------------------------------------
void CGrid_Skeletonize::Standard_Execute(void)
{
	int		i, nChanges;

	CSG_Grid	*pPrev, *pNext, *pTemp;

	//-----------------------------------------------------
	pPrev		= pResult;
	pNext		= SG_Create_Grid(pPrev);

	//-----------------------------------------------------