tri_triangulation.cpp

三角网的生成算法

#include "tricommon.h"


#define FPARAM_PITCH 		( 10.0 ) // angle in degree
#define DISTANCE_PITCH 		( 5.0 )
#define PSEUDO_POINT_COUNT 	( 12 )
#define STANDARD_BOX_COUNT	( 10 )


/**********************************************************************/
/**********************************************************************/
/*** FILE I/O related to Triangulation ********************************/
/**********************************************************************/
/**********************************************************************/

int iPsuedoPointCount_TRI( void ) { return PSEUDO_POINT_COUNT; }

bool bSaveNodeFile_TRI( char* szNodeFile, vector<Cp_dbl2> pnt )
{
	int i;
	bool bRetCode = false;
	FILE *fp = NULL;

	// --- open file ---
	
	fp = fopen( szNodeFile, "w" );
	if( NULL == fp ) {
		goto PIX_EXIT;
	}

	for( i = 0 ; i < (int)pnt.size( ) ; i++ ) {
		Cp_dbl2 ep = pnt[i];
		fprintf( fp, "%f,%f,%f\n", ep.x, ep.y, 0.0 );
	}
	
	// --- Done ---

	bRetCode = true;
	
PIX_EXIT:	
	if( fp ) fclose( fp );
	return bRetCode;
}


bool bSaveNodeFile_TRI( char* szNodeFile, vector<Cp_dbl3> pnt )
{
	int i;
	bool bRetCode = false;
	FILE *fp = NULL;

	// --- open file ---
	
	fp = fopen( szNodeFile, "w" );
	if( NULL == fp ) {
		goto PIX_EXIT;
	}

	for( i = 0 ; i < (int)pnt.size( ) ; i++ ) {
		Cp_dbl3 ep = pnt[i];
		fprintf( fp, "%f,%f,%f\n", ep.GetX( ), ep.GetY( ), ep.GetZ( ) );
	}
	
	// --- Done ---

	bRetCode = true;
	
PIX_EXIT:
	
	if( fp ) fclose( fp );

	return bRetCode;
}


bool bLoadNodeFile_TRI(char* szNodeFile, vector<Cp_dbl2> *Pnt2List )
{	
	bool bRetCode = false;
	bool bRet;
	vector<Cp_dbl3> Pnt3List;

	bRet = bLoadNodeFile_TRI( szNodeFile, &Pnt3List );
	if( !bRet ) goto PIX_EXIT;

	ConvertPntList( &Pnt3List, Pnt2List );
	
	// --- Done ---
	bRetCode = true;
	
PIX_EXIT:

	Pnt3List.clear( );
	return bRetCode;
}

bool bLoadNodeFile_TRI( char* szNodeFile, vector<Cp_dbl3> *pnt )
{	
	bool bRetCode = false;
	char szBuff[STANDARD_BUFFER_SIZE];
	char szBuffX[STANDARD_BUFFER_SIZE], szBuffY[STANDARD_BUFFER_SIZE];
	char szBuffZ[STANDARD_BUFFER_SIZE];
	char *pStr[DELIMITOUT_SIZE];
	int k;
	short sStatus;
	double dX, dY, dZ;
	FILE *fp = NULL;
	
	// --- start debugging ---
	
	fp = fopen( szNodeFile, "r" );
	if( NULL == fp ) goto PIX_EXIT;

	k = 0;
	sStatus = true;
	pnt->clear( );	
	while( sStatus ) {
		if( 0 >= fgets( szBuff, STANDARD_BUFFER_SIZE, fp ) ) {
			sStatus = false;
			continue;
		}

		chr_translate( szBuff, '\n', '\0' );
		
		int iCount = iDelimitStr_PIX( szBuff, pStr, ',', DELIMITOUT_SIZE );
		if( 2 == iCount ) {
			strcpy( szBuffX, pStr[0] );
			strcpy( szBuffY, pStr[1] );	
			dX = atof( szBuffX );
			dY = atof( szBuffY );
			dZ = 0.0;
		} else if( 3 <= iCount ) {
			strcpy( szBuffX, pStr[0] );
			strcpy( szBuffY, pStr[1] );
			strcpy( szBuffZ, pStr[2] );		
			dX = atof( szBuffX );
			dY = atof( szBuffY );
			dZ = atof( szBuffZ );
		} else {
			continue;
		}

		Cp_dbl3 ep( k++, dX, dY, dZ );
		pnt->push_back( ep );
	}

	// --- Done ---

	bRetCode = true;
	
PIX_EXIT:
	
	if( fp ) fclose( fp );

	return bRetCode;
}


bool bLoadTriFile_TRI( char *szTriFile, vector<Cp_dtri> *TriList )
{
	bool bRetCode = false;
	char szBuff[STANDARD_BUFFER_SIZE];
	char szBuffX[STANDARD_BUFFER_SIZE], szBuffY[STANDARD_BUFFER_SIZE];
	char szBuffZ[STANDARD_BUFFER_SIZE];
	char *pStr[DELIMITOUT_SIZE];
	Cp_dtri et;
	int k;
	short sStatus;
	FILE *fp = NULL;
	
	// --- start debugging ---
	
	fp = fopen( szTriFile, "r" );
	if( NULL == fp ) goto PIX_EXIT;

	k = 0;
	sStatus = true;
	TriList->clear( );	
	while( sStatus ) {
		if( 0 >= fgets( szBuff, STANDARD_BUFFER_SIZE, fp ) ) {
			sStatus = false;
			continue;
		}

		chr_translate( szBuff, '\n', '\0' );
		
		int iCount = iDelimitStr_PIX( szBuff, pStr, ',', DELIMITOUT_SIZE );
		if( 3 != iCount ) continue;
		
		strcpy( szBuffX, pStr[0] );
		strcpy( szBuffY, pStr[1] );
		strcpy( szBuffZ, pStr[2] );

		int iP0 = atoi( szBuffX );
		int iP1 = atoi( szBuffY );
		int iP2 = atoi( szBuffZ );

		et.Set( k++, iP0, iP1, iP2 );
		TriList->push_back( et );
	}

	// --- Done ---

	bRetCode = true;
	
PIX_EXIT:
	
	if( fp ) fclose( fp );

	return bRetCode;
}


bool bSaveTriFile_TRI( char* szTriFile, vector<Cp_dtri> *TriList )
{
	bool bRetCode = false;
	FILE *fp = NULL;
	int i, nTri;

	// --- open file ---
	
	fp = fopen( szTriFile, "w" );
	if( NULL == fp ) {
		goto PIX_EXIT;
	}

	nTri = (int)TriList->size( );
	for( i = 0 ; i < nTri ; i++ ) {
		Cp_dtri tri = TriList->at( i );
		fprintf( fp, "%d,%d,%d\n", tri.GetPnt(0), tri.GetPnt(1), tri.GetPnt(2) );
	}
	
	// --- Done ---

	bRetCode = true;
	
PIX_EXIT:
	
	if( fp ) fclose( fp );

	return bRetCode;
}




/**********************************************************************/
/**********************************************************************/
/*** Triangulate Polygon **********************************************/
/**********************************************************************/
/**********************************************************************/

//----------------------------------------------------------------------
// check the positional relationship of three 2-D points
// 
// Returns:
// -1: error
// 0: point p2 is on the line connecting p0 and p1
// 1: point p2 is in the left hand side of the line p0 -> p1
// 2: point p2 is in the right hand side of the line p0 -> p1
// Notes:
//
int iPointsRelation_TRI( 
		Cp_dbl2 *p0,
		Cp_dbl2 *p1,
		Cp_dbl2 *p2 )
{
	double dDet;
	dDet = p0->x * p1->y - p0->y * p1->x +
			p0->y * p2->x - p0->x * p2->y +
			p1->x * p2->y - p2->x * p1->y;
	
	if( dDet > 0.0 ) {
		return 1; // left
	} else if( dDet < 0.0 ) {
		return 2; // right
	} else {
		return 0; // on the line
	}
}	

int iPointsRelation_TRI( 
		vector<Cp_dbl2> *Pnt2List,
		int				i0,
		int				i1,
		int				i2 )
{
	int nPoints = (int)Pnt2List->size( );
	if( 0 > i0 || nPoints <= i0 ) return -1;
	if( 0 > i1 || nPoints <= i1 ) return -1;
	if( 0 > i2 || nPoints <= i2 ) return -1;
	Cp_dbl2 *p0 = &Pnt2List->at( i0 );
	Cp_dbl2 *p1 = &Pnt2List->at( i1 );
	Cp_dbl2 *p2 = &Pnt2List->at( i2 );
	return iPointsRelation_TRI( p0, p1, p2 );
}

//----------------------------------------------------------------------
// check if two segment intersect properly
// 
// Returns:
// true or false
//
bool bCheckPropIntersection_TRI( 
		Cp_dbl2	*p0,
		Cp_dbl2	*p1,
		Cp_dbl2	*p2,
		Cp_dbl2	*p3 )
{
	int iPos012 = iPointsRelation_TRI( p0, p1, p2 );
	if( 0 == iPos012 ) return false;

	int iPos013 = iPointsRelation_TRI( p0, p1, p3 );
	if( 0 == iPos013 ) return false;
	
	int iPos230 = iPointsRelation_TRI( p2, p3, p0 );
	if( 0 == iPos230 ) return false;
	
	int iPos231 = iPointsRelation_TRI( p2, p3, p1 );
	if( 0 == iPos231 ) return false;

	int iXor0 = ( 1 != iPos012 ) ^ ( 1 != iPos013 );
	if( !iXor0 ) return false;

	int iXor1 = ( 1 != iPos230 ) ^ ( 1 != iPos231 );
	return iXor1 ? true : false;
}

//----------------------------------------------------------------------
// check if the given point is strictly on the segment defined by two 
// other points
// 
// Returns:
// true or false
//
bool bBetweenSegments_TRI( 
		Cp_dbl2	*p0,	// [i] segment starting point
		Cp_dbl2	*p1,	// [i] segment another point
		Cp_dbl2	*p2 )	// [i] point to check
{
	int iPos = iPointsRelation_TRI( p0, p1, p2 );
	if( 0 != iPos ) return false;

	if( p0->x != p1->x ) {
		double dMinX = min( p0->x, p1->x );
		if( p2->x < dMinX ) return false;
		double dMaxX = max( p0->x, p1->x );
		return( p2->x > dMaxX ) ? false : true;
	} else {
		// p0->p1 is vertical!
		double dMinY = min( p0->y, p1->y );
		if( p2->y < dMinY ) return false;
		double dMaxY = max( p0->y, p1->y );
		return( p2->y > dMaxY ) ? false : true;
	}
}

//----------------------------------------------------------------------
// check if two segment intersect anyway
// 
// Returns:
// true or false
//
bool bCheckIntersection_TRI( 
		Cp_dbl2	*p0,
		Cp_dbl2	*p1,
		Cp_dbl2	*p2,
		Cp_dbl2	*p3 )
{
	if( bCheckPropIntersection_TRI( p0, p1, p2, p3 ) ) return true;

	if( bBetweenSegments_TRI( p0, p1, p2 ) ) return true;
	if( bBetweenSegments_TRI( p0, p1, p3 ) ) return true;
	if( bBetweenSegments_TRI( p2, p3, p0 ) ) return true;
	if( bBetweenSegments_TRI( p2, p3, p1 ) ) return true;

	return false;
}

bool bCheckIntersection_TRI( 
		vector<Cp_dbl2> *Pnt2List, 
		int				i0,
		int				i1,
		int				i2,
		int				i3 )
{
	if( 0 > i0 ) return false;
	if( 0 > i1 ) return false;
	if( 0 > i2 ) return false;
	if( 0 > i3 ) return false;
	int nPoints = (int)Pnt2List->size( );
	if( nPoints <= i0 ) return false;
	if( nPoints <= i1 ) return false;
	if( nPoints <= i2 ) return false;
	if( nPoints <= i3 ) return false;
	
	Cp_dbl2	*p0 = &Pnt2List->at( i0 );
	Cp_dbl2	*p1 = &Pnt2List->at( i1 );
	Cp_dbl2	*p2 = &Pnt2List->at( i2 );
	Cp_dbl2	*p3 = &Pnt2List->at( i3 );
	return( bCheckPropIntersection_TRI( p0, p1, p2, p3 ) );
}

//----------------------------------------------------------------------
// 
// 
// Returns:
// true or false
//
// Notes:
// polygon must be counter-clockwise
//
bool bCheckDiagonalie_TRI( vector<Cp_dbl2> *Pnt2List, int i, int j )
{
	int k, nPoints;
	if( 0 > i || 0 > j ) return false;
	nPoints = (int)Pnt2List->size( );
	if( nPoints <= i || nPoints <= j ) return false;

	for( k = 0 ; k < nPoints ; k++ ) {
		if( k == i ) continue;
		if( k == j ) continue;
		int k1 = ( k + 1 ) % nPoints;
		if( k1 == i ) continue;
		if( k1 == j ) continue;
		if( bCheckIntersection_TRI( Pnt2List, i, j, k, k1 ) ) return false;
	}

	return true;
}

//----------------------------------------------------------------------
// check if segment connecting two vertices of the polygon is strictly 
// in the polygon
// 
// Returns:
// true or false
//
// Notes:
// polygon must be counter-clockwise
//
bool bCheckCone_TRI( vector<Cp_dbl2> *Pnt2List, int i, int j )
{
	int iPos, nPoints;
	if( 0 > i || 0 > j ) return false;
	nPoints = (int)Pnt2List->size( );
	if( nPoints <= i || nPoints <= j ) return false;

	int i1 = ( i + 1 ) % nPoints;
	int in1 = ( i + nPoints - 1 ) % nPoints;

	iPos = iPointsRelation_TRI( Pnt2List, in1, i, i1 );
	if( iPos = 0 || iPos == 1 ) {
		int iPos0 = iPointsRelation_TRI( Pnt2List, i, j, in1 );
		if( 1 != iPos0 ) return false;
		int iPos1 = iPointsRelation_TRI( Pnt2List, j, i, i1 );
		return 1 == iPos1;
	} else {
		int iPos0 = iPointsRelation_TRI( Pnt2List, i, j, i1 );
		int iPos1 = iPointsRelation_TRI( Pnt2List, j, i, in1 );
		return !( 1 == iPos0 && 1 == iPos1 );
	}
}

//----------------------------------------------------------------------
// 
// 
// Returns:
// true or false
//
// Notes:
// polygon must be counter-clockwise
//
bool bCheckDiagonal_TRI( vector<Cp_dbl2> *Pnt2List, int i, int j )
{
	if( 0 > i || 0 > j ) return false;
	int nPoints = (int)Pnt2List->size( );