tincore.cpp

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

			}
			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;
			}				
			/////////////////////////////////////////////////////////////
			
			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

	for (i = r[5]; i <= r[6]; i++)
	{
		cin = i * col;
		for (k = c[5]; k <= c[6]; k++)
		{
			cell = cidx + (cin + k);
			if (SearchCellEMR(BFH, uidx, cell, ppts, ddim, pt1, pt2, opt, orn, cin + k, pid, cid, cen))
				return 1;
		}
	}

#endif

	////////////////////////////////////////////////////////////////
	c[1] = c[5];	c[2] = c[6];		r[1] = r[5];	r[2] = r[6];
	c[3] = c[1];	c[4] = c[2];		r[3] = r[1];	r[4] = r[2];
	c[5] = 0;		c[6] = col - 1;		r[5] = 0;		r[6] = row - 1;
	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 (SearchCellEMR(BFH, uidx, ppts, ddim, pt1, pt2, opt, orn, pid, cid, cen, col, c, r))
			return 1;
		
		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])
			return 0;

		// 检测停止标志
		if (!(*stop))
			return 0;
	}

	return 0;
}

// 检查是否空圆
// 0 表示空圆, 1 表示有点
inline long SearchCellEMR(IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim,
						  TSS_SNT32 *pid, TSS_FLT64 *cen, TSS_FLT64 rad)
{
	TSS_SNT32 n, k;

	for (n = 0; n < cell->sum; n++)
	{
		k = cell->pid[n];
		if (k == pid[0] || k == pid[1])
			continue;
		// 下面可以精确处理k == pid[2]问题
		if (EuLen2D(ppts + ddim * k, cen) < rad) // 有点
			return 1;
	}

	return 0;
}

#define OPTI_OU2

// 检查是否空圆
// 1 表示空圆, 0 表示有点
inline long SearchCellEMR(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim,
						  TSS_SNT32 *pid, TSS_FLT64 *cen, TSS_FLT64 rad)
{
	TSS_SNT32 col = uidx->num[0];
	TSS_SNT32 row = uidx->num[1];
	TSS_SNT32 i, k, c[8], r[8], cid;
	IDX_CELL *cell, *cidx = uidx->idx;

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

#ifdef	OPTI_OU2

	// 采用外扩算法优化
	// 从距离圆心最近的单元开始
	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];
	cell = cidx + i * col + k;
	if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
		return 0;

	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]
			{
				cid = r[1] * col;
				for (k = c[1] + 1; k < c[2]; k++)
				{
					cell = cidx + cid + k;
					if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
						return 0;
				}
			}
			if (r[4] != r[2])	// 即r[4] != r[6]
			{
				cid = r[2] * col;
				for (k = c[1] + 1; k < c[2]; k++)
				{
					cell = cidx + cid + k;
					if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
						return 0;
				}
			}
			if (c[3] != c[1])	// 即c[3] != c[5]
			{
				for (i = r[1] + 1; i < r[2]; i++)
				{
					cell = cidx + i * col + c[1];
					if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
						return 0;
				}
			}
			if (c[4] != c[2])	// 即c[4] != c[6]
			{
				for (i = r[1] + 1; i < r[2]; i++)
				{
					cell = cidx + i * col + c[2];
					if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
						return 0;
				}
			}
			// 处理4个角单元
			if (c[3] != c[5] || r[3] != r[5])
			{
				cell = cidx + r[1] * col + c[1];
				if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}
			if (c[3] != c[5] || r[4] != r[6])
			{
				cell = cidx + r[2] * col + c[1];
				if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}
			if (c[4] != c[6] || r[3] != r[5])
			{
				cell = cidx + r[1] * col + c[2];
				if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}
			if (c[4] != c[6] || r[4] != r[6])
			{
				cell = cidx + r[2] * col + c[2];
				if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}				
			/////////////////////////////////////////////////////////////
			
			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

	// 先列后行顺序
	for (i = r[5]; i <= r[6]; i++)
	{
		cid = i * col;
		for (k = c[5]; k <= c[6]; k++)
		{
			cell = cidx + (cid + k);
			if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
				return 0;
		}
	}

#endif

	return 1;
}

// 要点:
// 1 异侧
// 2 2次边
// 3 空圆法则
// 方向约束搜索:要求orn = -1 或 1
inline long SearchCellEMR(CTssHash *BFH, IDX_GRID *uidx, IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim,
						  TSS_FLT64 *pt1, TSS_FLT64 *pt2, TSS_FLT64 *opt, TSS_SNT32 orn, TSS_SNT32 cin,
						  TSS_SNT32 *pid, TSS_SNT32 &cid, TSS_FLT64 *cen)
{
	TIN_FACE fa, fc;
	TSS_FLT64 *pt3, rad;
	TSS_SNT32 n, kid, cnt, *nid;

	cnt = cell->cnt;
	nid = cell->pid;
	for (n = 0; n < cnt; n++)
	{
		kid = nid[n];
		pt3 = ppts + ddim * kid;
		if (orn == IsSide(pt1, pt2, pt3))	// 异侧
		{ 
			// 检查是否形成2次边
			SetFace(&fa, pid[0], kid);
			if (BFH->GetData(&fa))
				continue;
			SetFace(&fc, pid[1], kid);
			if (BFH->GetData(&fc))
				continue;

			// 计算圆心和半径
			CalcCircum(pt1, pt2, pt3, cen);
			rad = EuLen2D(pt3, cen);
			pid[2] = kid;
			cid = cin;

			// 快速过滤
			if (EuLen2D(opt, cen) < rad)
				continue;

			// 空圆法则
			if (SearchCellEMR(uidx, ppts, ddim, pid, cen, rad))
				return 1;
		}
	}

	return 0;
}

// 批量方向约束搜索:要求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;
}

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

// 检查是否空圆
// 1 表示空圆, 0 表示有点
inline long SearchCellEMR_Slow(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim,
						  TSS_SNT32 *pid, TSS_FLT64 *cen, TSS_FLT64 rad)
{
	TSS_SNT32 i, k, c[4], r[4], cid;
	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;

#ifdef OPTI_IN

	// 采用内旋算法优化
	if (c[2] - c[1] >= r[2] - r[1])
	{
		// c[2] - c[1] >= r[2] - r[1]
		cid = r[1] * col;
		for (k = c[1]; k < c[2]; k++)
		{
			cell = cidx + cid + k;
			if (SearchCellEMR(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 (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[1]++;
			cid = r[2] * col;
			for (k = c[2]; k > c[1]; k--)
			{
				cell = cidx + cid + k;
				if (SearchCellEMR(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 (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[2]--;
			cid = r[1] * col;
			for (k = c[1]; k < c[2]; k++)
			{
				cell = cidx + cid + k;
				if (SearchCellEMR(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 (SearchCellEMR(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 (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
				return 0;
		}
		// 循环处理
		while (c[1] < c[2])
		{
			cid = r[2] * col;
			for (k = c[2]; k > c[1]; k--)
			{
				cell = cidx + cid + k;
				if (SearchCellEMR(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 (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
					return 0;
			}		r[2]--;
			if (c[1] == c[2])	{	i = r[1];	break;	}
			cid = r[1] * col;
			for (k = c[1]; k < c[2]; k++)
			{
				cell = cidx + cid + k;
				if (SearchCellEMR(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 (SearchCellEMR(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 (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
			return 0;
	}

#else

	// 先列后行顺序
	for (i = r[1]; i <= r[2]; i++)
	{
		cid = i * col;
		for (k = c[1]; k <= c[2]; k++)
		{
			cell = cidx + (cid + k);
			if (SearchCellEMR(cell, ppts, ddim, pid, cen, rad))
				return 0;
		}
	}

#endif

	return 1;
}