triangulate.cpp

这是书上的代码

   }

   dx = x2 - *xc;
   dy = y2 - *yc;
   rsqr = dx*dx + dy*dy;
   *r = sqrt(rsqr);

   dx = xp - *xc;
   dy = yp - *yc;
   drsqr = dx*dx + dy*dy;

   return((drsqr <= rsqr) ? TRUE : FALSE);
}



void CTriangulate::QSortVertexByX() //X增大排序
{
	qsort((void *)pv_, (size_t)nv_, sizeof(XYZ), compare);
}


///////////////////////////////////////////////////////////////////////
/*
   用成员变量m_szFileName指定的文件初始化pv_和nv_.
   成功返回true，否则返回false
*/
bool CTriangulate::Initial(char *szFileName) 
{
	strcpy(szFileName_, szFileName); // 初始化成员变量，该文件保存了顶点信息

	char *buf = NULL;

	if ( this->szFileName_ == NULL ) return false;

	// 使用内存映像文件来读取文件数据
	HANDLE hFile = CreateFile( szFileName_,
							   GENERIC_READ,
							   FILE_SHARE_READ,
							   NULL, //security attributes
							   OPEN_EXISTING,
							   FILE_FLAG_SEQUENTIAL_SCAN,
							   NULL);	//template file
	if ( hFile == INVALID_HANDLE_VALUE) return false; //因错误返回
	HANDLE hFileMapping = CreateFileMapping(hFile, 
											NULL,  // Security attributes
											PAGE_READONLY, 
											0,   //内存映射的最大大小，这位64位中的高位
											0, //64位中的低位，0为匹配文件的实际长度
											NULL); //给内存映射命名
	if ( hFileMapping == NULL ) return false;	

	LPVOID pMem =  MapViewOfFile(hFileMapping,
								  FILE_MAP_READ,
								  0, //视图在映射文件的起始位置,64位中的高位
								  0, // 64位中的低位，这是从文件头开始映射
								  0); //映射长度
	if (pMem == NULL) return false;

	buf = (char *)pMem;


	////////////////////////////////////////////////////////////////
	// TODO: Add your process in here
	//
	char linebuf[1024];
	char *pos;
	XYZ *pTemp;
	long MAXVERTEX = 1000;
	//pv_  = (XYZ *)malloc( MAXVERTEX * sizeof(XYZ) );
	if ((pv_ = new XYZ[MAXVERTEX]) == NULL ) 	return false;

	istrstream is(buf, GetFileSize(hFile, NULL));
	while ( ! is.eof() )
	{
		is.getline(linebuf, 1024);
		pos = strchr(linebuf, '#'); // 符号#后为注释
		if ( pos != NULL ) *pos = '\0'; //remove comment
		if ( sscanf(linebuf, "%le %le %le", &pv_[nv_].x, &pv_[nv_].y, &pv_[nv_].z ) != 3)
			continue; // error! continue to read next line
		else
		{
			nv_++;
			if ( nv_ >= MAXVERTEX)
			{
				if ((pTemp = new XYZ[MAXVERTEX + 1000]) == NULL ) return false;
				memcpy(pTemp, pv_, sizeof(XYZ) * MAXVERTEX);
				delete []pv_;
				pv_ = pTemp;
				MAXVERTEX += 1000;
			}
		}
	}
	//
	// end your process
	//////////////////////////////////////////////////////////////////


	CloseHandle(hFile);
	CloseHandle(hFileMapping);
	UnmapViewOfFile(pMem);


	// set RBvertex_ and LTvertex_
	LTvertex_ = pv_[0];
	RBvertex_ = LTvertex_;
	for ( int i = 1; i < nv_; i++ )
	{
		if ( pv_[i].x > LTvertex_.x ) LTvertex_.x = pv_[i].x;
		if ( pv_[i].x < RBvertex_.x ) RBvertex_.x = pv_[i].x;
		if ( pv_[i].y > LTvertex_.y ) LTvertex_.y = pv_[i].y;
		if ( pv_[i].y < RBvertex_.y ) RBvertex_.y = pv_[i].y;
		if ( pv_[i].z > LTvertex_.z ) LTvertex_.z = pv_[i].z;
		if ( pv_[i].z < RBvertex_.z ) RBvertex_.z = pv_[i].z;
	}
	return true; //正常返回为0
}


//////////////////////////////////////////////////////////////////////
/*
   根据nv_和pv_创建三角形，创建的三角形保存在ptri_中
   三角形的个数保存在ntri_中；
   其中需要调用三角形的剖分算法Triangulate()

   注意：
       有很多种三角剖分算法，Triangulate()是一种增量算法。
*/
bool CTriangulate::CreateTriangle()
{
	SortAndRemoveRepeatPoints();	// 根据x的大小对pv_进行排序,并且删掉重复的点
									// Triangulate()函数需要已经排序过的pv_
	AfxMessageBox("排序和删除重复点结束。",0,0);

	if ((ptri_ = new TRIANGLE[4 * nv_]) == NULL)
		return false; //三角形的最多个数是顶点个数的4倍
	Triangulate(nv_, pv_, &ntri_, ptri_);
	
	AfxMessageBox("三角剖分结束。",0,0);

	MeshedTris();
	AfxMessageBox("建立三角形之间的关系结束。",0,0);

	return true;
}





XYZ CTriangulate::GetLTvertex()	// 获得散点的xyz的最大值
{
	return LTvertex_;
}

XYZ CTriangulate::GetRBvertex() // 获得散点的xyz的最小值
{
	return RBvertex_;
}



// 为TRIANGLE的T1，T2，T3设定值。即建立三角形的邻接关系
void CTriangulate::MeshedTris() //对各个独立的三角形建立网络联系
{
	int i, j;

	for (i = 0; i < ntri_; i++) // remove 不规范的点, need it?
	{
		if (ptri_[i].p1 == ptri_[i].p2 || ptri_[i].p1 == ptri_[i].p3 || ptri_[i].p2 == ptri_[i].p3 )
		{
			ptri_[i] = ptri_[ntri_ - 1];
			ntri_--;
		}
	}

	for (i = 0; i < ntri_; i++)
	{
		if (ptri_[i].t3 == NEIGHBOR_UNKNOWN)
			for ( j = i + 1; j < ntri_; j++)
			{
				if (   (ptri_[i].p1 == ptri_[j].p1 || ptri_[i].p1 == ptri_[j].p2 || ptri_[i].p1 == ptri_[j].p3 )
					&& (ptri_[i].p2 == ptri_[j].p1 || ptri_[i].p2 == ptri_[j].p2 || ptri_[i].p2 == ptri_[j].p3 ) )
				{
					ptri_[i].t3 = j; // 设置第i个三角形的边p1p2的邻接三角形

					// 由于两个邻接三角形是相互邻接的，所以同时设置“邻接三角形j”的邻接三角形为i
					if ( ptri_[j].p1 + ptri_[j].p2 == ptri_[i].p1 + ptri_[i].p2 ) 
						ptri_[j].t3 = i; 
					else if ( ptri_[j].p1 + ptri_[j].p3 == ptri_[i].p1 + ptri_[i].p2 ) 
						ptri_[j].t2 = i;
					else //( ptri_[j].p3 + ptri_[j].p2 == ptri_[i].p1 + ptri_[i].p2 ) 
						ptri_[j].t1 = i;

					break;
				}					
			}
		if (ptri_[i].t2 == NEIGHBOR_UNKNOWN)
			for ( j = i + 1; j < ntri_; j++)
			{
				if (   (ptri_[i].p1 == ptri_[j].p1 || ptri_[i].p1 == ptri_[j].p2 || ptri_[i].p1 == ptri_[j].p3 )
					&& (ptri_[i].p3 == ptri_[j].p1 || ptri_[i].p3 == ptri_[j].p2 || ptri_[i].p3 == ptri_[j].p3 ) )
				{
					ptri_[i].t2 = j; // 设置第i个三角形的边p1p2的邻接三角形

					// 由于两个邻接三角形是相互邻接的，所以同时设置“邻接三角形j”的邻接三角形为i
					if ( ptri_[j].p1 + ptri_[j].p2 == ptri_[i].p1 + ptri_[i].p3 ) 
						ptri_[j].t3 = i; 
					else if ( ptri_[j].p1 + ptri_[j].p3 == ptri_[i].p1 + ptri_[i].p3 ) 
						ptri_[j].t2 = i;
					else //if ( ptri_[j].p3 + ptri_[j].p2 == ptri_[i].p1 + ptri_[i].p3 ) 
						ptri_[j].t1 = i;

					break;
				}					
			}
		if (ptri_[i].t1 == NEIGHBOR_UNKNOWN)
			for ( j = i + 1; j < ntri_; j++)
			{
				if (   (ptri_[i].p3 == ptri_[j].p1 || ptri_[i].p3 == ptri_[j].p2 || ptri_[i].p3 == ptri_[j].p3 )
					&& (ptri_[i].p2 == ptri_[j].p1 || ptri_[i].p2 == ptri_[j].p2 || ptri_[i].p2 == ptri_[j].p3 ) )
				{
					ptri_[i].t1 = j; // 设置第i个三角形的边p1p2的邻接三角形

					// 由于两个邻接三角形是相互邻接的，所以同时设置“邻接三角形j”的邻接三角形为i
					if ( ptri_[j].p1 + ptri_[j].p2 == ptri_[i].p3 + ptri_[i].p2 ) 
						ptri_[j].t3 = i; 
					else if ( ptri_[j].p1 + ptri_[j].p3 == ptri_[i].p3 + ptri_[i].p2 ) 
						ptri_[j].t2 = i;
					else //if ( ptri_[j].p3 + ptri_[j].p2 == ptri_[i].p3 + ptri_[i].p2 ) 
						ptri_[j].t1 = i;

					break;
				}					
			}
	} // end i
}

void CTriangulate::SortAndRemoveRepeatPoints()
{
	int i, j;
	int pos(0), pos2(0);
	int readpos(0), writepos(0);

	QSortVertexByX(); // 按X增大排序

	bool *flagkilled = new bool[nv_];
	for ( i = 0; i < nv_; i++)
		flagkilled[i] = false;

	while( pos < nv_)
	{
		while( pv_[++pos2].x == pv_[pos].x );
		
		for(i = pos; i < pos2; i++)
		{
			if(flagkilled[i]) continue;
			for (j = i + 1; j < pos2; j++)
				if(pv_[j].y == pv_[i].y) 
					flagkilled[j] = true;
		}
		pos = pos2;
	}

	while(readpos < nv_)
	{
		while(flagkilled[readpos]) // skip killed points
			readpos++;
		if (writepos != readpos)
			pv_[writepos] = pv_[readpos];
		writepos++;
		readpos++;
	}

	nv_ = writepos;
	delete []flagkilled;

	//TRACE("output norepeat points: nv=%d\n", nv_);
	//for (i=0; i<nv_; i++)
	//	TRACE("%lf  %lf  %lf\n", pv_[i].x, pv_[i].y, pv_[i].z);
	//TRACE("End output\n");
}