tincore1.cpp

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

			if (BFH->GetData(&fc))
				continue;

			// 计算圆心和半径
			CalcCircum(pt1, pt2, pt3, cen);		rad = EuLen2D(pt3, cen);
			// 检查不包含闭合点和2次边
			if (EuLen2D(opt, cen) >= rad &&	SearchCellDON(BFH, uidx, ppts, ddim, pid, cen, rad))
			{
				pid[2] = nid[n];	cid = cin;
				SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt3, orn, rad, pid, cid, cen);
				return 1;
			}
		}
	}

	return 0;
}

// 检查单元中是否存在被圆包含的闭合点或2次边
inline long HaveDone(CTssHash *BFH, IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_SNT32 *pid, TSS_FLT64 *cen, TSS_FLT64 rad)
{
	TSS_SNT32 n, cnt, sum, *nid;
	TSS_FLT64 *opt;	TIN_FACE fa, fc;

	nid = cell->pid;	cnt = cell->cnt;	sum = cell->sum;
	// 查找闭合点
	for (n = cnt; n < sum; n++)
	{
		opt = ppts + ddim * nid[n];
		if (EuLen2D(opt, cen) < rad)
			return 1;
	}
	// 查找2次边
	for (n = 0; n < cnt; n++)
	{
		opt = ppts + ddim * nid[n];
		if (EuLen2D(opt, cen) < rad)
		{
			SetFace(&fa, pid[0], nid[n]);
			if (BFH->GetData(&fa))
				return 1;
			SetFace(&fc, pid[1], nid[n]);
			if (BFH->GetData(&fc))
				return 1;
		}
	}

	return 0;
}

// 定义内旋算法优化开关
#define OPTI_IN

// 搜索是否包含闭合点或2次边
inline long SearchCellDON(CTssHash *BFH, IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim,
						  TSS_SNT32 *pid, TSS_FLT64 *cen, TSS_FLT64 rad)
{
#ifdef OPTI_IN
	TSS_SNT32 i, k, c[4], r[4];
	IDX_CELL *cell, *cidx = uidx->idx;
	TSS_SNT32 col = uidx->num[0], row = uidx->num[1];

	// 计算搜索边界
	CalcSearchBound(uidx->bnd, uidx->spn, col, row, cen, sqrt(rad), c[1], c[2], r[1], r[2]);
	if (c[2] < c[1] || r[2] < r[1])	// 数值过大造成混乱
		return 0;

	// 采用内旋算法优化
	if (c[2] - c[1] >= r[2] - r[1])
	{
		// c[2] - c[1] >= r[2] - r[1]
		for (k = c[1]; k < c[2]; k++)
		{
			cell = cidx + r[1] * col + k;
			if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
				return 0;
		}
		// 循环处理
		while (r[1] < r[2])
		{
			for (i = r[1]; i < r[2]; i++)
			{
				cell = cidx + i * col + c[2];
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[1]++;
			for (k = c[2]; k > c[1]; k--)
			{
				cell = cidx + r[2] * col + k;
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		c[2]--;
			if (r[1] == r[2])	{	k = c[1];	break;	}
			for (i = r[2]; i > r[1]; i--)
			{
				cell = cidx + i * col + c[1];
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[2]--;
			for (k = c[1]; k < c[2]; k++)
			{
				cell = cidx + r[1] * col + k;
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		c[1]++;
			if (r[1] == r[2])	{	k = c[2];	break;	}
		}
		// 最后一个
		cell = cidx + r[1] * col + k;
		if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
			return 0;
	}
	else
	{
		// c[2] - c[1] < r[2] - r[1]
		for (i = r[1]; i < r[2]; i++)
		{
			cell = cidx + i * col + c[2];
			if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
				return 0;
		}
		// 循环处理
		while (c[1] < c[2])
		{
			for (k = c[2]; k > c[1]; k--)
			{
				cell = cidx + r[2] * col + k;
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		c[2]--;
			for (i = r[2]; i > r[1]; i--)
			{
				cell = cidx + i * col + c[1];
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[2]--;
			if (c[1] == c[2])	{	i = r[1];	break;	}
			for (k = c[1]; k < c[2]; k++)
			{
				cell = cidx + r[1] * col + k;
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		c[1]++;
			for (i = r[1]; i < r[2]; i++)
			{
				cell = cidx + i * col + c[2];
				if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[1]++;
			if (c[1] == c[2])	{	i = r[2];	break;	}
		}
		// 最后一个
		cell = cidx + i * col + c[1];
		if (HaveDone(BFH, cell, ppts, ddim, pid, cen, rad))
			return 0;
	}
#else
	TSS_FLT64 *opt;
	IDX_CELL *cell, *cidx = uidx->idx;
	TSS_INT32 col = uidx->num[0], row = uidx->num[1];
	TSS_INT32 i, k, n, c[4], r[4], cid, *pid, cnt, sum;

	// 计算搜索边界
	CalcSearchBound(uidx->bnd, uidx->spn, col, row, cen, sqrt(rad), c[1], c[2], r[1], r[2]);
	if (c[2] < c[1] || r[2] < r[1])	// 数值过大造成混乱
		return 0;

	for (i = r[1]; i <= r[2]; i++)
	{
		cid = i * col;
		for (k = c[1]; k <= c[2]; k++)
		{
			cell = cidx + (cid + k);	pid = cell->pid;	cnt = cell->cnt;	sum = cell->sum;
			for (n = cnt; n < sum; n++)
			{
				opt = ppts + ddim * pid[n];
				if (EuLen2D(opt, cen) < rad)
					return 0;
			}
		}
	}
#endif

	return 1;
}

// 定义外扩算法优化开关
#define OPTI_OU

// 检查圆内是否存在点
inline void SearchCellEMR(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pt1,
						  TSS_FLT64 *pt2, TSS_FLT64 *pt3, TSS_SNT32 orn, TSS_FLT64 rad,
						  TSS_SNT32 *pid, TSS_SNT32 &cid, TSS_FLT64 *cen)
{
	// 递归搜索
#ifdef	OPTI_OU
	TSS_FLT64 *pt4;
	IDX_CELL *cell, *cidx = uidx->idx;
	TSS_SNT32 i, k, n, c[8], r[8], tmp, cnt, *nid;
	TSS_SNT32 col = uidx->num[0], row = uidx->num[1];

	// 计算搜索边界
	CalcSearchBound(uidx->bnd, uidx->spn, col, row, cen, sqrt(rad), c[5], c[6], r[5], r[6]);

	// 采用外扩算法优化
	// 从距离圆心最近的单元开始
	TSS_SNT32 pos[2];	CalcGridCell(uidx, cen, pos);
	if		(pos[0] < 0)		pos[0] = 0;
	else if (pos[0] > col - 1)	pos[0] = col - 1;
	if		(pos[1] < 0)		pos[1] = 0;
	else if (pos[1] > row - 1)	pos[1] = row - 1;
	k = pos[0], i = pos[1];		tmp = i * col + k;
	cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
	for (n = 0; n < cnt; n++)
	{
		pt4 = ppts + ddim * nid[n];
		// EuLen2D(pt4, cen) < rad保证pt4不等于pt3
		// orn == IsSide(pt1, pt2, pt4)保证pt4不等于pt1或 pt2
		if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
		{
			CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
			SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
			return;
		}
	}
	if (c[6] - c[5] > 0 || r[6] - r[5] > 0)
	{
		c[1] = c[2] = c[3] = c[4] = k;	r[1] = r[2] = r[3] = r[4] = i;
		while (1)
		{
			c[1]--;	if (c[1] < c[5])	c[1] = c[5];
			c[2]++;	if (c[2] > c[6])	c[2] = c[6];
			r[1]--;	if (r[1] < r[5])	r[1] = r[5];
			r[2]++;	if (r[2] > r[6])	r[2] = r[6];
			/////////////////////////////////////////////////////////////
			if (r[3] != r[1])	// 即r[3] != r[5]
			{
				for (k = c[1] + 1; k < c[2]; k++)
				{
					tmp = r[1] * col + k;
					cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
					for (n = 0; n < cnt; n++)
					{
						pt4 = ppts + ddim * nid[n];
						if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
						{
							CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
							SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
							return;
						}
					}
				}
			}
			if (r[4] != r[2])	// 即r[4] != r[6]
			{
				for (k = c[1] + 1; k < c[2]; k++)
				{
					tmp = r[2] * col + k;
					cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
					for (n = 0; n < cnt; n++)
					{
						pt4 = ppts + ddim * nid[n];
						if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
						{
							CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
							SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
							return;
						}
					}
				}
			}
			if (c[3] != c[1])	// 即c[3] != c[5]
			{
				for (i = r[1] + 1; i < r[2]; i++)
				{
					tmp = i * col + c[1];
					cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
					for (n = 0; n < cnt; n++)
					{
						pt4 = ppts + ddim * nid[n];
						if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
						{
							CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
							SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
							return;
						}
					}
				}
			}
			if (c[4] != c[2])	// 即c[4] != c[6]
			{
				for (i = r[1] + 1; i < r[2]; i++)
				{
					tmp = i * col + c[2];
					cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
					for (n = 0; n < cnt; n++)
					{
						pt4 = ppts + ddim * nid[n];
						if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
						{
							CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
							SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
							return;
						}
					}
				}
			}
			// 处理4个角单元
			if (c[3] != c[5] || r[3] != r[5])
			{
				tmp = r[1] * col + c[1];
				cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
				for (n = 0; n < cnt; n++)
				{
					pt4 = ppts + ddim * nid[n];
					if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
					{
						CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
						SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
						return;
					}
				}
			}
			if (c[3] != c[5] || r[4] != r[6])
			{
				tmp = r[2] * col + c[1];
				cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
				for (n = 0; n < cnt; n++)
				{
					pt4 = ppts + ddim * nid[n];
					if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
					{
						CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
						SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
						return;
					}
				}
			}
			if (c[4] != c[6] || r[3] != r[5])
			{
				tmp = r[1] * col + c[2];
				cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
				for (n = 0; n < cnt; n++)
				{
					pt4 = ppts + ddim * nid[n];
					if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
					{
						CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
						SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
						return;
					}
				}
			}
			if (c[4] != c[6] || r[4] != r[6])
			{
				tmp = r[2] * col + c[2];
				cell = cidx + tmp;	cnt = cell->cnt;	nid = cell->pid;
				for (n = 0; n < cnt; n++)
				{
					pt4 = ppts + ddim * nid[n];
					if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad)
					{
						CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp;
						SearchCellEMR(uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
						return;
					}
				}
			}				
			/////////////////////////////////////////////////////////////
			
			c[3] = c[1], c[4] = c[2], r[3] = r[1], r[4] = r[2];
			if (c[3] == c[5] && c[4] == c[6] &&
				r[3] == r[5] && r[4] == r[6])
				break;
		}
	}
#else
	TSS_FLT64 *pt4;
	IDX_CELL *cell, *cidx = uidx->idx;
	TSS_SNT32 i, k, n, c[4], r[4], tmp, cnt, *nid;
	TSS_SNT32 col = uidx->num[0], row = uidx->num[1];

	// 计算搜索边界
	CalcSearchBound(uidx->bnd, uidx->spn, col, row, cen, sqrt(rad), c[1], c[2], r[1], r[2]);

	for (i = r[1]; i <= r[2]; i++)
	{
		tmp = i * col;
		for (k = c[1]; k <= c[2]; k++)
		{
			cell = cidx + (tmp + k);	cnt = cell->cnt;	nid = cell->pid;
			for (n = 0; n < cnt; n++)
			{
				pt4 = ppts + ddim * nid[n];
				if (orn == IsSide(pt1, pt2, pt4) && EuLen2D(pt4, cen) < rad) // 有点
				{
					CalcCircum(pt1, pt2, pt4, cen);		rad = EuLen2D(pt4, cen);	pid[2] = nid[n];	cid = tmp + k;
					SearchCellEMR(BFH, uidx, ppts, ddim, pt1, pt2, pt4, orn, rad, pid, cid, cen);
					return;
				}
			}
		}
	}
#endif
}

// 批量方向约束搜索:要求orn = -1 或 1
inline long SearchCellEMR(CTssHash *BFH, IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pt1,
						  TSS_FLT64 *pt2, TSS_FLT64 *opt, TSS_SNT32 orn, TSS_SNT32 *pid,
						  TSS_SNT32 &cid, TSS_FLT64 *cen, TSS_SNT32 col,
						  TSS_SNT32 *c, TSS_SNT32 *r)
{
	TSS_SNT32 i, k, cin;
	IDX_CELL *cell, *cidx = uidx->idx;

	if (r[3] != r[1])	// 即r[3] != r[5]
	{
		for (k = c[1] + 1; k < c[2]; k++)
		{
			cin = r[1] * col + k;		cell = cidx + cin;
			if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
				return 1;
		}
	}
	if (r[4] != r[2])	// 即r[4] != r[6]
	{
		for (k = c[1] + 1; k < c[2]; k++)
		{
			cin = r[2] * col + k;		cell = cidx + cin;
			if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
				return 1;
		}
	}
	if (c[3] != c[1])	// 即c[3] != c[5]
	{
		for (i = r[1] + 1; i < r[2]; i++)
		{
			cin = i * col + c[1];		cell = cidx + cin;
			if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
				return 1;
		}
	}
	if (c[4] != c[2])	// 即c[4] != c[6]
	{
		for (i = r[1] + 1; i < r[2]; i++)
		{
			cin = i * col + c[2];		cell = cidx + cin;
			if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
				return 1;
		}
	}
	// 处理4个角单元
	if (c[3] != c[5] || r[3] != r[5])
	{
		cin = r[1] * col + c[1];	cell = cidx + cin;
		if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
			return 1;
	}
	if (c[3] != c[5] || r[4] != r[6])
	{
		cin = r[2] * col + c[1];	cell = cidx + cin;
		if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
			return 1;
	}
	if (c[4] != c[6] || r[3] != r[5])
	{
		cin = r[1] * col + c[2];	cell = cidx + cin;
		if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
			return 1;
	}
	if (c[4] != c[6] || r[4] != r[6])
	{
		cin = r[2] * col + c[2];	cell = cidx + cin;
		if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin, pid, cid, cen))
			return 1;
	}

	return 0;
}