tri_triangulation.cpp

三角网的生成算法

		if( bCmpNbrList( p, 1, ptr2, iNbrList ) ) {
			if( !ptr2_in_trilist ) {
				int iTri = (int)TriVector->size( );
				Cp_dtri tmptri;
				tmptri.Set( iTri, ptr0, ptr1, ptr2 );

				TriVector->push_back( tmptri );

				iBlgList->Set( ptr0, iBelngCount[ptr0], iTri );
				iBelngCount[ptr0]++;
				iBlgList->Set( ptr1, iBelngCount[ptr1], iTri );
				iBelngCount[ptr1]++;
				iBlgList->Set( ptr2, iBelngCount[ptr2], iTri );
				iBelngCount[ptr2]++;
			}
			break;
		}

		/*--------------------------------------------------------------
		#### if the connecting point is found in the second step, i.e., 
		#### it is not found from the existing triangle list.....
		--------------------------------------------------------------*/
		if( !ptr2_in_trilist ) {
			/*----------------------------------------------------------
			#### create new triangle and set "ptr0", "ptr1" and "ptr2" 
			#### as the vertices.
			----------------------------------------------------------*/
			int iTri = (int)TriVector->size( );
			Cp_dtri tmptri;
			tmptri.Set( iTri, ptr0, ptr1, ptr2 );
			TriVector->push_back( tmptri );

			/*----------------------------------------------------------
			#### "億僀儞僩偑懏偡傞嶰妏宍"儕僗僩偺廋惓丅 
			#### ptr0丄ptr1丄ptr2偑懏偡傞嶰妏宍偺悢偑傂偲偮憹傗偝傟傞
			----------------------------------------------------------*/
			iBlgList->Set( ptr0, iBelngCount[ptr0], iTri );
			iBelngCount[ptr0]++;
			iBlgList->Set( ptr1, iBelngCount[ptr1], iTri );
			iBelngCount[ptr1]++;
			iBlgList->Set( ptr2, iBelngCount[ptr2], iTri );
			iBelngCount[ptr2]++;
		}

		// ---  add ptr2 to the neighbour list of p ---
	
		iNbrList->Set( p, nneib, ptr2 );
		iIncluded[ptr2] = true;
		nneib++;
		ptr1 = ptr2;
	}
	
	// --- DOne ---

PIX_EXIT:

	if( iRight ) delete[] iRight;
	if( iIncluded ) delete[] iIncluded;
	if( iPntSorted ) delete[] iPntSorted;

	return nneib;
}


bool bResetTriangleList_TRI(
		int				nInPoints,
		vector<int>		*iPntTables,
		vector<Cp_dtri>	*TriVector,
		vector<Cp_dtri>	*TriVector2 )
{
	int i, iPnt, iPtr[3];
	Cp_dtri tri;
	vector <Cp_dtri>::iterator Iter;

	/*------------------------------------------------------------------
	#### 嶰妏宍儕僗僩傪嵞峔惉偡傞
	------------------------------------------------------------------*/
	TriVector2->clear( );
	for ( Iter = TriVector->begin( ); Iter != TriVector->end( ); Iter++ ) {

		tri = *Iter;
		for( i = 0 ; i < 3 ; i++ ) {
			iPnt = tri.GetPnt(i);
			iPtr[i] = iPntTables->at( iPnt );
		}
		
		if( iPtr[0] >= nInPoints ) continue;
		if( iPtr[1] >= nInPoints ) continue;
		if( iPtr[2] >= nInPoints ) continue;

		tri.Set( iPtr[0], iPtr[1], iPtr[2] );  

		TriVector2->push_back( tri );
	}

	return true;
}


//======================================================================
// 
//
bool bCreateTriangleVector_TRI(	
		int				ntri,
		vector<Cp_dtri> *TriVector,
		vector<Cp_dtri> *TriList )
{	
	bool bRetCode = false;
	int i;

	/*------------------------------------------------------------------
	**** TRIANGLE( S )
	------------------------------------------------------------------*/
Cp_dtri tri;

	TriList->clear( );
	for ( i = 0; i < ntri; i++ ) {
		tri = TriVector->at( i );
		TriList->push_back( tri );
	}

	bRetCode = true;
	return bRetCode;
}


//======================================================================
// 
// iNbrList[i][j]	
// j-th point which is currently connected to point "i". Note that this
// the sequential number of point, not a point ID. Also it is important
// that points are added to this list as it is found and it is not
// sorted by any numerical nor geometrical conditions. 
// The first point in the list is always "i" itself.
//	 	
//	 				example )   12       13
//	 	       				     *     /
//	 	     				      \  /
//	 	    				    14 *--------* 25
//	 	     				      /               
//	 	    				     /      * 19
//	 	  				        /
//	 	 				       * 20
// in this example, number of points connected to point 14 is three. 
// points connected to "14" are 12, 25 and 20.
// **** nneib[14] = 4
// **** iNbrList[14][0] = 12
// **** iNbrList[14][1] = 14
// **** iNbrList[14][2] = 25
// **** iNbrList[14][3] = 20
//
bool bCmpNbrList(
		int		row,
		int		col,
		int		value,
		CDT_Matrix<int>	*iNbrList )
{
	int data = iNbrList->Get( row, col );
	return( data == value ); 
}


//======================================================================
// 
//
bool bInitBelongList_TRI(
		int				npoints,
		CDT_Matrix<int>	*iBlgList )
{
	int n = 0;
	for ( int i = 0; i < npoints; i++ ) {
		for( int j = 0; j < npoints; j++ ) {
			iBlgList->Set( i, j, n );
		}
	}

	return true;
}


//======================================================================
// bSortByDistance
// sort list of the points according to the distance from one of the point
//
bool bSortByDistance(
		int				iCenter,		// [i] point# to be centered
		vector<Cp_dbl2>	*PntList,		// [i] input point vector
		int				*iPntSorted )	// [o] sorted vector, must be assigned a same size as PntList
{
	bool bRetCode = false;
	int i, iSize;
	Cp_dbl2 Pnt, Cen;
	double dX, dY, dDist;

	double *dDistList = NULL;

	iSize = (int)PntList->size( );
	if( 0 > iCenter || iCenter >= iSize ) {
		goto PIX_EXIT;
	}

	dDistList = new double[iSize];
	if( NULL == dDistList ) goto PIX_EXIT;

	Cen = PntList->at( iCenter );
	for( i = 0 ; i < iSize ; i++ ) {
		Pnt = PntList->at( i );
		dX = Cen.x - Pnt.x;
		dY = Cen.y - Pnt.y;
		dDist = dX * dX + dY * dY;
		iPntSorted[i] = i;
		dDistList[i] = sqrt( dDist );
	}
	
	DoubleArrayQsort( dDistList, iSize, iPntSorted );

	// --- Done ---
	
	bRetCode = true;

PIX_EXIT:

	if( dDistList ) delete[] dDistList;

	return bRetCode;
}


bool bBoxSortPoint_TRI( vector<Cp_dbl2>* PntList, int* iBoxSorted )
{
	int oPoints = (int)PntList->size( );
	return bBoxSortPoint_TRI( oPoints, PntList, iBoxSorted );
}

bool bBoxSortPoint_TRI( int oPoints, vector<Cp_dbl2>* PntList, int* iBoxSorted )
{
	bool bRetCode = false;
	int iLoc, iCol, iRow, i, j, k, iRowCount, iColCount;
	double dBoxSize, dXSize, dYSize;
	Cp_dbl2	ep, p_min, p_max;
	int *iColBelong = NULL;
	int *iRowBelong = NULL;
	int *iBelong = NULL;

	PixMiniMax( oPoints, PntList, &p_min, &p_max );
	dXSize = p_max.x - p_min.x;
	dYSize = p_max.y - p_min.y;

	dBoxSize = min( dXSize, dYSize ) / STANDARD_BOX_COUNT;

	iColCount = (int)floor( dXSize / dBoxSize );
	iRowCount = (int)floor( dYSize / dBoxSize );
	

	iColBelong = new int[oPoints];
	if( !iColBelong ) goto PIX_EXIT;

	iRowBelong = new int[oPoints];
	if( !iRowBelong ) goto PIX_EXIT;

	iBelong = new int[oPoints];
	if( !iBelong ) goto PIX_EXIT;

	for( k = 0 ; k < oPoints ; k++ ) {
		ep = PntList->at( k );
		iCol = (int)floor( ( ep.x - p_min.x ) / dBoxSize );
		iRow = (int)floor( ( ep.y - p_min.y ) / dBoxSize );
		iColBelong[k] = iCol;
		iRowBelong[k] = iRow;
		iBelong[k] = -1;
	}

	iLoc = 0;
	for( i = 0 ; i <= iRowCount ; i++ ) {
		for( j = 0 ; j <= iColCount ; j++ ) {
			for( k = 0 ; k < oPoints ; k++ ) {
				iCol = iColBelong[k];
				if( iCol != j ) continue;
				iRow = iRowBelong[k];
				if( iRow != i ) continue;
				iBelong[k] = iLoc;
				iBoxSorted[iLoc++] = k;
			}
		}
	}

	
	for( k = 0 ; k < oPoints ; k++ ) {
		if( 0 > iBelong[k] ) {
			i = -1;
		}
	}


	// --- Done ---
	
	bRetCode = true;

PIX_EXIT:

	if( iColBelong ) delete[] iColBelong;
	if( iRowBelong ) delete[] iRowBelong;
	if( iBelong ) delete[] iBelong;

	return bRetCode;
}


//----------------------------------------------------------------------
//
//
int iListConvex_TRI(
		int				iPtr,			// [i] point number on converx hull
		int				opoints,		// [i] number of original points
		vector<Cp_dbl2>	*Pnt2List,		// [i] list of points
		vector<int>		*Cnv2List,		// [i/o] 
		int				*iNbrCount,		// [i/o] 
		CDT_Matrix<int>	*iNbrList,		// [i/o] 
		int				*iBlgCount,		// [i/o] 
		CDT_Matrix<int>	*iBlgList,		// [i/o] 
		vector<Cp_dtri> *TriVector )	// [i/o] 
{
	short sFound, sPseudoFound;
	int iRot, iPrev, iCur, i, j, nNbr, iNbr, jNbr, nCnv, iCnv, iCnvNext, iNext;
	int iTri, nTri;
	double dAngle, dMinAngle;
	Cp_dbl2 Ptr0, Ptr1, Ptr2;
	Cp_dtri tri;
	vector<int> Chain;
	vector<Cp_dbl2>	Ply2List;
	vector<Cp_dtri> Tri2List;

	// --- get points and the next ---

	nCnv = (int)Cnv2List->size( );
	iCnv = Cnv2List->at( iPtr );
	iCnvNext = ( iPtr == nCnv-1) ? Cnv2List->at( 0 ) :  Cnv2List->at( iPtr+1 );

	Ptr0 = Pnt2List->at( iCnv );
	Ptr1 = Pnt2List->at( iCnvNext );
	
	// --- if two points on the convex hull are already connected, leave ---
	sFound = false;
	nNbr = iNbrCount[iCnv];
	for( i = 1 ; !sFound && i < nNbr ; i++ ) { 
		iNbr = iNbrList->Get( iCnv, i );
		if( iNbr == iCnvNext ) {
			sFound = true;
		}
	}
	
	if( sFound ) goto PIX_EXIT;

	// --- find the point to be connected to the iCnv ---
	
	Chain.clear( );
	Chain.push_back( iCnv );
	
	nNbr = iNbrCount[iCnv];
	iNext = -1;
	for( i = 1 ; i < nNbr ; i++ ) {
		iNbr = iNbrList->Get( iCnv, i );
		
		// --- check if this point is connected to the pseudo points ---
		sPseudoFound = false;
		for( j = 1 ; !sPseudoFound && j < iNbrCount[iNbr] ; j++ ) {
			jNbr = iNbrList->Get( iNbr, j );
			if( jNbr >= opoints ) sPseudoFound = true;
		}
		if( !sPseudoFound ) continue;

		Ptr2 = Pnt2List->at( iNbr );
		dAngle = get_3angle( &Ptr1, &Ptr0, &Ptr2 );
		//if( PIE / 2.0 < dAngle ) continue;
		if( 0 > iNext ) {
			dMinAngle = dAngle;
			iNext = iNbr;
		} else if( dMinAngle > dAngle ) {
			dMinAngle = dAngle;
			iNext = iNbr;
		}
	}

	if( 0 > iNext ) goto PIX_EXIT;
	Chain.push_back( iNext );

	// --- follow the chain until the next point on the hull is found ---
	
	sFound = false;
	iPrev = iCnv;
	while( !sFound ) {
		iCur = iNext;
		Ptr0 = Pnt2List->at( iPrev );
		Ptr1 = Pnt2List->at( iCur );
		nNbr = iNbrCount[iCur];
		iNext = -1;
		for( i = 1 ; !sFound && i < nNbr ; i++ ) {
			iNbr = iNbrList->Get( iCur, i );
			if( iNbr >= opoints ) continue;
			if( iNbr == iPrev ) continue;
			if( iNbr == iCnvNext ) {
				// --- the node is connected to the next point in the hull ---
				Chain.push_back( iCnvNext );
				sFound = true;
				continue;
			}

			// --- check if iNbr is connected to the pseudo points ---
			sPseudoFound = false;
			for( j = 1 ; !sPseudoFound && j < iNbrCount[iNbr] ; j++ ) {
				jNbr = iNbrList->Get( iNbr, j );
				if( jNbr >= opoints ) sPseudoFound = true;
			}
			if( !sPseudoFound ) continue;
	
			Ptr2 = Pnt2List->at( iNbr );
			dAngle = get_3angle( &Ptr0, &Ptr1, &Ptr2 );
			//if( PIE < dAngle ) continue;
			if( 0 > iNext ) {
				dMinAngle = dAngle;
				iNext = iNbr;
			} else if( dMinAngle > dAngle ) {
				dMinAngle = dAngle;
				iNext = iNbr;
			}
		}

		if( sFound ) continue;
	
		if( 0 > iNext ) goto PIX_EXIT;
		Chain.push_back( iNext );
		iPrev = iCur;
	}

	// --- construct polygon ---
	nNbr = (int)Chain.size( );

	if( 3 > nNbr ) goto PIX_EXIT;
	if( 3 == nNbr ) {
		tri.Set( (int)TriVector->size( ), (int)Chain.at( 0 ), (int)Chain.at( 1 ), (int)Chain.at( 2 ) );
		TriVector->push_back( tri );
		goto PIX_EXIT;
	}

	Ply2List.clear( );
	for( i = 0 ; i < nNbr ; i++ ) {
		iNbr = Chain.at( i );
		Ptr0 = Pnt2List->at( iNbr );
		Ptr0.SetID( iNbr );
		Ply2List.push_back( Ptr0 );
	}

	// --- triangulate the polygon ---
	Tri2List.clear( );
	iRot = iPolygonRotDirection( &Ply2List );
	if( !bPolygonSwapRotation( &Ply2List, true ) ) goto PIX_EXIT;
	StartPolygonTri_TRI( &Ply2List, &Tri2List );

	// --- add to triangle lists ---
	
	nTri = (int)Tri2List.size( );
	for( i = 0 ; i < nTri ; i++ ) {
		iTri = (int)TriVector->size( );
		tri = Tri2List.at( i );
		tri.SetID( iTri );
		TriVector->push_back( tri );
	}

	// --- Done ---
PIX_EXIT:

	Chain.clear( );
	Tri2List.clear( );
	return 0;
}