tcston2.cpp

并行TIN生成算法, 基于DeWall算法理论实现

	return 0;
}
// 构造三角形:最大最小角原则
inline TCS_V00 ConTen2(TIN_G *G, TCS_F64 *P, TCS_S32 sid[2], TCS_S32 eid[2], CTcsBL *APL, CTcsBL *ATL, CTcsHL *ASL, CTcsHL *BSL, CTcsSL *SSL)
{
	TIN_T *T;	TIN_S *S;
	TIN_X *X1 = (TIN_X*)APL->RemoveHead();
	TIN_X *X2 = (TIN_X*)APL->RemoveHead();
	if (!X2) // 只有1点
	{
		// 增加三角形
		T = new TIN_T;
		T->pid[0] = sid[0], T->pid[1] = eid[0], T->pid[2] = X1->pid;
		ATL->AddTail(T);
		// 检测活动边
		S = new TIN_S;
		IniSide(S, sid[0], eid[0], sid[1], eid[1], X1->pid);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else	// 放入候选链表
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, sid[0], X1->pid, sid[1], X1->cid, eid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, eid[0], X1->pid, eid[1], X1->cid, sid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		// 删除归零点
		if (G->pid[sid[0]] == 0)	{	RmvPid(G->idx + sid[1], sid[0]);	G->vpn++;	}
		if (G->pid[eid[0]] == 0)	{	RmvPid(G->idx + eid[1], eid[0]);	G->vpn++;	}
		if (G->pid[X1->pid] == 0)	{	RmvPid(G->idx + X1->cid, X1->pid);	G->vpn++;	}

		delete X1;
		return;
	}

	// 首先调整sid与eid的顺序
	TCS_F64 *sp = P + 2 * sid[0];
	TCS_F64 *ep = P + 2 * eid[0];
	TCS_F64 *p1 = P + 2 * X1->pid;
	TCS_F64 *p2 = P + 2 * X2->pid;
	if (IsSide2(sp, p1, ep) != IsSide2(sp, p1, p2))
	{
		// 不同侧, 交换sid与eid
		TCS_S32 pi = sid[0];	sid[0] = eid[0];	eid[0] = pi;
		TCS_S32 ci = sid[1];	sid[1] = eid[1];	eid[1] = ci;
		sp = P + 2 * sid[0];	ep = P + 2 * eid[0];
	}

	// 循环构网
	while (X2)
	{
		// ep---------sp
		//
		//            p1
		//
		//      p2
		// 暂不局部优化
		// 增加三角形
		T = new TIN_T;
		T->pid[0] = sid[0], T->pid[1] = eid[0], T->pid[2] = X1->pid;
		ATL->AddTail(T);
		// 检测活动边
		S = new TIN_S;
		IniSide(S, sid[0], eid[0], sid[1], eid[1], X1->pid);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, sid[0], X1->pid, sid[1], X1->cid, eid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		// 增加三角形
		T = new TIN_T;
		T->pid[0] = eid[0], T->pid[1] = X1->pid, T->pid[2] = X2->pid;
		ATL->AddTail(T);
		// 检测活动边
		S = new TIN_S;
		IniSide(S, X1->pid, X2->pid, X1->cid, X2->cid, eid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, X2->pid, eid[0], X2->cid, eid[1], X1->pid);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		// 搜集公共边
		S = new TIN_S;
		IniSide(S, X1->pid, eid[0], X1->cid, eid[1], sid[0]);
		S->pid[1] = X2->pid;	BSL->PutData(S, S);
		// 删除归零点
		if (G->pid[sid[0]] == 0)	{	RmvPid(G->idx + sid[1], sid[0]);	G->vpn++;	}
		if (G->pid[eid[0]] == 0)	{	RmvPid(G->idx + eid[1], eid[0]);	G->vpn++;	}
		if (G->pid[X1->pid] == 0)	{	RmvPid(G->idx + X1->cid, X1->pid);	G->vpn++;	}
		if (G->pid[X2->pid] == 0)	{	RmvPid(G->idx + X2->cid, X2->pid);	G->vpn++;	}
		// X2变sid
		sid[0] = X2->pid, sid[1] = X2->cid;

		delete X1;	delete X2;
		X1 = (TIN_X*)APL->RemoveHead();
		X2 = (TIN_X*)APL->RemoveHead();
	}
	// 最多剩1点
	if (X1)
	{
		// 增加三角形
		T = new TIN_T;
		T->pid[0] = sid[0], T->pid[1] = eid[0], T->pid[2] = X1->pid;
		ATL->AddTail(T);
		// 检测活动边
		S = new TIN_S;
		IniSide(S, sid[0], eid[0], sid[1], eid[1], X1->pid);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, sid[0], X1->pid, sid[1], X1->cid, eid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		S = new TIN_S;
		IniSide(S, eid[0], X1->pid, eid[1], X1->cid, sid[0]);
		if (!InsSide(ASL, BSL, G, S))
			delete S;
		else
			SSL->PutData(S);
		// 删除归零点
		if (G->pid[sid[0]] == 0)	{	RmvPid(G->idx + sid[1], sid[0]);	G->vpn++;	}
		if (G->pid[eid[0]] == 0)	{	RmvPid(G->idx + eid[1], eid[0]);	G->vpn++;	}
		if (G->pid[X1->pid] == 0)	{	RmvPid(G->idx + X1->cid, X1->pid);	G->vpn++;	}

		delete X1;
	}
}

// 构造三角形墙:用于围绕X分隔线
// 从某条与分隔线相交的活动边开始, 围绕分隔线循环构造三角形, 形成三角形墙
inline TCS_V00 ConTxn2(TIN_G *G, TIN_S *S, TCS_F64 *P, TCS_F64 X, CTcsBL *ATL, CTcsHL *ASL, CTcsHL *BSL)
{
	TCS_F64 d2, ce[2];
	TCS_S32 sid[2], eid[2];
	CTcsBL *APL = new CTcsBL;
	CTcsSL *SSL = new CTcsSL;

	// 搜索共圆点
	FndEmp2(G, S, P, ce, d2, APL);
	if (APL->GetSize() == 0)	// 构造完毕
	{
		// 搜集静止边
		ASL->DetData(S);
		// 减少计数器
		G->pid[S->sid[0]]--;	G->pid[S->eid[0]]--;
		// 删除归零点
		if (G->pid[S->sid[0]] == 0)	{	RmvPid(G->idx + S->sid[1], S->sid[0]);	G->vpn++;	}
		if (G->pid[S->eid[0]] == 0)	{	RmvPid(G->idx + S->eid[1], S->eid[0]);	G->vpn++;	}
		// 收集边对象
		S->pid[1] = -1;		BSL->PutData(S, S);

		delete APL;	delete SSL;	return;
	}
	if (APL->GetSize() > 1)
		ArcPos2(APL, P, ce, d2);
	// 构造三角形
	sid[0] = S->sid[0], sid[1] = S->sid[1];
	eid[0] = S->eid[0], eid[1] = S->eid[1];
	ConTen2(G, P, sid, eid, APL, ATL, ASL, BSL, SSL);
	// 获得与分隔线相交的活动边
	S = (TIN_S*)SSL->PopData();
	while (S)
	{
		// 如果是活动边, 判断是否相交
		if (ASL->GetData(S) && LxSide2(X, P, S))
			ConTxn2(G, S, P, X, ATL, ASL, BSL);
		S = (TIN_S*)SSL->PopData();
	}

	delete APL;	delete SSL;
}
// 构造三角形墙:用于围绕Y分隔线
// 从某条与分隔线相交的活动边开始, 围绕分隔线循环构造三角形, 形成三角形墙
inline TCS_V00 ConTyn2(TIN_G *G, TIN_S *S, TCS_F64 *P, TCS_F64 Y, CTcsBL *ATL, CTcsHL *ASL, CTcsHL *BSL)
{
	TCS_F64 d2, ce[2];
	TCS_S32 sid[2], eid[2];
	CTcsBL *APL = new CTcsBL;
	CTcsSL *SSL = new CTcsSL;

	// 搜索共圆点
	FndEmp2(G, S, P, ce, d2, APL);
	if (APL->GetSize() == 0)	// 构造完毕
	{
		// 搜集静止边
		ASL->DetData(S);
		// 减少计数器
		G->pid[S->sid[0]]--;	G->pid[S->eid[0]]--;
		// 删除归零点
		if (G->pid[S->sid[0]] == 0)	{	RmvPid(G->idx + S->sid[1], S->sid[0]);	G->vpn++;	}
		if (G->pid[S->eid[0]] == 0)	{	RmvPid(G->idx + S->eid[1], S->eid[0]);	G->vpn++;	}
		// 收集边对象
		S->pid[1] = -1;		BSL->PutData(S, S);

		delete APL;	delete SSL;	return;
	}
	if (APL->GetSize() > 1)
		ArcPos2(APL, P, ce, d2);
	// 构造三角形
	sid[0] = S->sid[0], sid[1] = S->sid[1];
	eid[0] = S->eid[0], eid[1] = S->eid[1];
	ConTen2(G, P, sid, eid, APL, ATL, ASL, BSL, SSL);
	// 获得与分隔线相交的活动边
	S = (TIN_S*)SSL->PopData();
	while (S)
	{
		// 如果是活动边, 判断是否相交
		if (ASL->GetData(S) && LySide2(Y, P, S))
			ConTyn2(G, S, P, Y, ATL, ASL, BSL);
		S = (TIN_S*)SSL->PopData();
	}

	delete APL;	delete SSL;
}

// 单元编号正变换
inline TCS_S32 CnvCid2(TCS_S32 cid, TCS_S32 co1, TCS_S32 co2, TCS_S32 sc, TCS_S32 sr)
{
	TCS_S32 r = cid / co1;
	TCS_S32 c = cid - r * co1;
	return ((r - sr) * co2 + c - sc);
}
// 单元编号逆变换
inline TCS_S32 InvCid2(TCS_S32 cid, TCS_S32 co1, TCS_S32 co2, TCS_S32 sc, TCS_S32 sr)
{
	TCS_S32 r = cid / co2;
	TCS_S32 c = cid - r * co2;
	return ((r + sr) * co1 + c + sc);
}
// 构造隔离区:用于左右隔离
inline TCS_V00 ConRxn2(TIN_G *G, TIN_R *L, TIN_R *R, CTcsHL *H, TCS_F64 *P, TCS_F64 X)
{
	// 分离活动边
	TCS_F64 *sp, *ep;
	L->S = 0;	R->S = 0;
	TIN_S *S = (TIN_S*)H->RemoveHead();
	while (S)
	{
		sp = P + 2 * S->sid[0];
		ep = P + 2 * S->eid[0];
		if (sp[0] <= X && ep[0] <= X)
		{
			// cid正变换
			S->sid[1] = CnvCid2(S->sid[1], G->num[0], L->G->num[0], L->SCO[0], L->SCO[1]);
			S->eid[1] = CnvCid2(S->eid[1], G->num[0], L->G->num[0], L->SCO[0], L->SCO[1]);
			L->ASL->PutData(S, S);
			// 判断是否与下次分隔线相交
			if (L->S == 0 && LySide2(L->AXV, P, S))
				L->S = S;
		}
		else
		{
			// cid正变换
			S->sid[1] = CnvCid2(S->sid[1], G->num[0], R->G->num[0], R->SCO[0], R->SCO[1]);
			S->eid[1] = CnvCid2(S->eid[1], G->num[0], R->G->num[0], R->SCO[0], R->SCO[1]);
			R->ASL->PutData(S, S);
			// 判断是否与下次分隔线相交
			if (R->S == 0 && LySide2(R->AXV, P, S))
				R->S = S;
		}

		S = (TIN_S*)H->RemoveNext();
	}
}
// 构造隔离区:用于上下隔离
inline TCS_V00 ConRyn2(TIN_G *G, TIN_R *U, TIN_R *D, CTcsHL *H, TCS_F64 *P, TCS_F64 Y)
{
	// 分离活动边
	TCS_F64 *sp, *ep;
	U->S = 0;	D->S = 0;
	TIN_S *S = (TIN_S*)H->RemoveHead();
	while (S)
	{
		sp = P + 2 * S->sid[0];
		ep = P + 2 * S->eid[0];
		if (sp[1] <= Y && ep[1] <= Y)
		{
			// cid正变换
			S->sid[1] = CnvCid2(S->sid[1], G->num[0], D->G->num[0], D->SCO[0], D->SCO[1]);
			S->eid[1] = CnvCid2(S->eid[1], G->num[0], D->G->num[0], D->SCO[0], D->SCO[1]);
			D->ASL->PutData(S, S);
			// 判断是否与下次分隔线相交
			if (D->S == 0 && LxSide2(D->AXV, P, S))
				D->S = S;
		}
		else
		{
			// cid正变换
			S->sid[1] = CnvCid2(S->sid[1], G->num[0], U->G->num[0], U->SCO[0], U->SCO[1]);
			S->eid[1] = CnvCid2(S->eid[1], G->num[0], U->G->num[0], U->SCO[0], U->SCO[1]);
			U->ASL->PutData(S, S);
			// 判断是否与下次分隔线相交
			if (U->S == 0 && LxSide2(U->AXV, P, S))
				U->S = S;
		}

		S = (TIN_S*)H->RemoveNext();
	}
}
// 复制隔离区索引单元
inline TCS_V00 ConRen2(TIN_G *G, TIN_R *R)
{
	TIN_G *E = R->G;
	E->spn[0] = G->spn[0];
	E->spn[1] = G->spn[1];

	TCS_S32 sc = TCS_S32((E->bnd[0] - G->bnd[0]) / G->spn[0]);
	TCS_S32 ec = TCS_S32((E->bnd[2] - G->bnd[0]) / G->spn[0]);
	if (ec >= G->num[0])	ec = G->num[0] - 1;
	TCS_S32 sr = TCS_S32((E->bnd[1] - G->bnd[1]) / G->spn[1]);
	TCS_S32 er = TCS_S32((E->bnd[3] - G->bnd[1]) / G->spn[1]);
	if (er >= G->num[1])	er = G->num[1] - 1;
	R->SCO[0] = sc, R->SCO[1] = sr;

	E->num[0] = (ec - sc) + 1, E->num[1] = (er - sr) + 1;
	E->idx = new TIN_C[E->num[0] * E->num[1]];
	E->bnd[0] = G->bnd[0] + sc * G->spn[0];
	E->bnd[1] = G->bnd[1] + sr * G->spn[1];
	E->bnd[2] = G->bnd[0] + (ec + 1) * G->spn[0];
	E->bnd[3] = G->bnd[1] + (er + 1) * G->spn[1];
	// 复制索引单元
	for (long k, n, r = sr; r <= er; r++)
	{
		k = r * G->num[0];
		n = (r - sr) * E->num[0];
		for (long i, m, c = sc; c <= ec; c++)
		{
			m = k + c;
			i = n + c - sc;
			// 复制
			E->idx[i].num = G->idx[m].sum;
			E->idx[i].sum = G->idx[m].sum;
			E->idx[i].ocn = G->idx[m].ocn;
			E->idx[i].pid = new TCS_S32[E->idx[i].sum];
			::memcpy(E->idx[i].pid, G->idx[m].pid, 4 * E->idx[i].sum);
		}
	}
}
// 构造隔离区:用于左右隔离
inline TCS_V00 ConRxn2(TIN_G *G, TIN_R *L, TIN_R *R, CTcsHL *H, TCS_F64 *P, TCS_F64 X, TCS_F64 Y)
{
	TIN_G *E;
	// 左隔离区
	L->G = new TIN_G;
	L->ATL = new CTcsBL;
	L->AXI = 1;	L->AXV = Y;
	L->ASL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	L->BSL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	// 处理TIN_G
	E = L->G;	E->pid = G->pid;	E->vpn = 0;
	E->bnd[0] = G->bnd[0];	E->bnd[1] = G->bnd[1];
	E->bnd[2] = X;			E->bnd[3] = G->bnd[3];
	ConRen2(G, L);

	// 右隔离区
	R->G = new TIN_G;
	R->ATL = new CTcsBL;
	R->AXI = 1;	R->AXV = Y;
	R->ASL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	R->BSL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	// 处理TIN_G
	E = R->G;	E->pid = G->pid;	E->vpn = 0;
	E->bnd[0] = X;			E->bnd[1] = G->bnd[1];
	E->bnd[2] = G->bnd[2];	E->bnd[3] = G->bnd[3];
	ConRen2(G, R);

	// 分离活动边
	ConRxn2(G, L, R, H, P, X);
}
// 构造隔离区:用于上下隔离
inline TCS_V00 ConRyn2(TIN_G *G, TIN_R *U, TIN_R *D, CTcsHL *H, TCS_F64 *P, TCS_F64 X, TCS_F64 Y)
{
	TIN_G *E;
	// 上隔离区
	U->G = new TIN_G;
	U->ATL = new CTcsBL;
	U->AXI = 0;	U->AXV = X;
	U->ASL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	U->BSL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	// 处理TIN_G
	E = U->G;	E->pid = G->pid;	E->vpn = 0;
	E->bnd[0] = G->bnd[0];	E->bnd[1] = Y;
	E->bnd[2] = G->bnd[2];	E->bnd[3] = G->bnd[3];
	ConRen2(G, U);

	// 下隔离区
	D->G = new TIN_G;
	D->ATL = new CTcsBL;
	D->AXI = 0;	D->AXV = X;
	D->ASL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	D->BSL = new CTcsHL(128, SIDE_EQLH, SIDE_HASH);
	// 处理TIN_G
	E = D->G;	E->pid = G->pid;	E->vpn = 0;
	E->bnd[0] = G->bnd[0];	E->bnd[1] = G->bnd[1];
	E->bnd[2] = G->bnd[2];	E->bnd[3] = Y;
	ConRen2(G, D);

	// 分离活动边
	ConRyn2(G, U, D, H, P, Y);
}

// 隔离区构造三角形
TCS_V00 ConTen2(TIN_R *R, TCS_F64 *P, TCS_S32 *TE)
{
	CTcsBL APL;
	TIN_G *G = R->G;
	TCS_F64 ce[2], d2;
	CTcsHL *ASL = R->ASL;
	CTcsBL *ATL = R->ATL;
	CTcsHL *BSL = R->BSL;
	TCS_S32 sid[2], eid[2];

	TIN_S *S = (TIN_S*)ASL->GetHead();
	while (S)
	{
		FndEmp2(G, S, P, ce, d2, &APL);
		if (APL.GetSize() == 0)
		{
			// 减少计数器
			G->pid[S->sid[0]]--;	G->pid[S->eid[0]]--;
			// 删除归零点
			if (G->pid[S->sid[0]] == 0)	{	RmvPid(G->idx + S->sid[1], S->sid[0]);	G->vpn++;	}
			if (G->pid[S->eid[0]] == 0)	{	RmvPid(G->idx + S->eid[1], S->eid[0]);	G->vpn++;	}
			// 收集边对象
			S->pid[1] = -1;		ASL->DetData(S);	BSL->PutData(S, S);
			// 判断中途终止
			if (*TE == 1)
				break;
		}
		else
		{
			// 共圆点排序
			if (APL.GetSize() > 1)
				ArcPos2(&APL, P, ce, d2);
			// 构造三角形
			sid[0] = S->sid[0], sid[1] = S->sid[1];
			eid[0] = S->eid[0], eid[1] = S->eid[1];
			ConTen2(G, P, sid, eid, &APL, ATL, ASL, BSL);
			// 判断中途终止
			if (*TE == 1)
				break;
		}

		S = (TIN_S*)ASL->GetHead();
	}
}