tincore.h

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

/* -*- C++ -*- */

//=============================================================================
/**
 *  @文件    TinCore.h
 *
 *  TinCore.h, 版本 0.10 2007/09/27
 *
 *  @作者 邓雪清 <[e-mail]>
 *  基于Incremental Construction算法的单线程实现
 */
//=============================================================================

#ifndef _TIN_CORE_H_
#define _TIN_CORE_H_

#include <windows.h>
#include "..\Tss_Inc\Point2D.h"
#include "..\Tss_Inc\Point3D.h"
#include "..\Tss_Inc\TssTset.h"
#include "..\Tss_API\TssHash.h"
#include "..\Tss_API\TssList.h"
typedef	struct _timeb	TSS_TIMEB;

// 网格索引结构
typedef struct tagIDX_CELL {
	TSS_SNT32	 num;	// 容量
	TSS_SNT32	 cnt;	// 计数
	TSS_SNT32	*pid;	// 数组
	TSS_SNT32	 sum;	// 总数
} IDX_CELL;

// 统一网格结构
typedef struct tagIDX_GRID {
	TSS_FLT64	 bnd[4];	// 坐标边界
	TSS_FLT64	 spn[2];	// 网格间距
	TSS_SNT32	 num[2];	// 矩阵大小
	TSS_FLT32	 dup;		// 坐标精度
	IDX_CELL	*idx;		// 单元数组
} IDX_GRID;

// 边(面)结构
typedef struct tagTIN_FACE {
	TSS_SNT32	 sid[2];	// 起点(0:pid, 1:cid)
	TSS_SNT32	 eid[2];	// 末点(0:pid, 1:cid)
	TSS_SNT32	 pid;		// 对面点
	TSS_SNT32	 tid;		// 邻接三角形
} TIN_FACE;

// 三角形结构
typedef struct tagTIN_TGON {
	TSS_SNT32	 pid[3];
	TSS_SNT32	 tid[3];
} TIN_TGON;

long GridToTin2D(POINT2D *ppts, TSS_SNT32 *pnum, TSS_SNT32 *stop,
			   TSS_SNT32 *vnum, TSS_SNT32 **vidx, TSS_TIMEB *betm, TSS_TIMEB *entm);
long DelaunayTriangulation2D(POINT3D *ppts, TSS_SNT32 *pnum, TSS_FLT32 ddup, TSS_SNT32 *stop,
							 TSS_SNT32 *vnum, TSS_SNT32 **vidx, TSS_TIMEB *betm, TSS_TIMEB *entm);

// 哈希函数
TSS_SNT32 FACE_EQLH(void const *f1, void const *f2);
TSS_UNT32 FACE_HASH(void const *f1);

// 计算网格矩阵大小
void CalcGridSize(IDX_GRID *uidx, TSS_SNT32 num, TSS_SNT32 avg);
// 计算点所处单元-数组偏移
long CalcGridCell(IDX_GRID *uidx, TSS_FLT64 *pnt);
// 计算点所处单元-坐标位置
void CalcGridCell(IDX_GRID *uidx, TSS_FLT64 *pnt, TSS_SNT32 *pos);
// 增加点到单元
void AddPid(IDX_CELL *cell, TSS_SNT32 pid);
// 从单元删除点
void DelPid(IDX_CELL *cell, TSS_SNT32 pos);
void DelPidEx(IDX_CELL *cell, TSS_SNT32 pid);

// 判断单元中是否有重合点
long IsHaveDup(IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT32 dup,
			   TSS_FLT64 *pt, TSS_SNT32 s);

// 消除重合点
void RemoveDupA(IDX_GRID *uidx, TSS_SNT32 *pnum, TSS_SNT32 ddim, TSS_FLT64 *ppts,
				TSS_SNT32 *ppid, TSS_SNT32 *stop);
// 按列处理重合点
void RemoveDupC(IDX_GRID *uidx, TSS_SNT32 *pnum, TSS_SNT32 ddim, TSS_FLT64 *ppts,
				TSS_SNT32 *ppid, TSS_SNT32 c, TSS_SNT32 r1, TSS_SNT32 r2);
// 按行处理重合点
void RemoveDupR(IDX_GRID *uidx, TSS_SNT32 *pnum, TSS_SNT32 ddim, TSS_FLT64 *ppts,
				TSS_SNT32 *ppid, TSS_SNT32 r, TSS_SNT32 c1, TSS_SNT32 c2);
// 处理边界重合点
void RemoveDupS(IDX_GRID *uidx, TSS_SNT32 *pnum, TSS_SNT32 ddim, TSS_FLT64 *ppts,
				TSS_SNT32 *ppid);
// 按矩阵处理重合点
void RemoveDupM(IDX_GRID *uidx, TSS_SNT32 *pnum, TSS_SNT32 ddim, TSS_FLT64 *ppts,
				TSS_SNT32 *ppid, TSS_SNT32 *stop, TSS_SNT32 c1, TSS_SNT32 c2,
				TSS_SNT32 r1, TSS_SNT32 r2);
// 设置边参数
void SetFace(TIN_FACE *face, TSS_SNT32 sid, TSS_SNT32 eid, TSS_SNT32 pid,
			 TSS_SNT32 tid, TSS_SNT32 sic, TSS_SNT32 eic);
// 释放CELL索引
void FreeCell(IDX_CELL *cidx, TSS_SNT32 num);

// 构建初始三角形
long MakeFirstSimplex(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_SNT32 *stop,
					  TSS_FLT64 dm2, TSS_SNT32 *pid, TSS_SNT32 *cid);
// 构建三角形网络
long MakeSimplex(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_SNT32 *ppid,
				 TSS_SNT32 *pnum, TSS_SNT32 *vnum, TSS_SNT32 *stop, TSS_SNT32 *pid,
				 TSS_SNT32 *cid, CTssList *ATL);

// 单元搜索最近点
// 同单元搜索
void SearchCellNPS(IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pnt,
				   TSS_SNT32 cin, TSS_SNT32 &pid, TSS_SNT32 &cid, TSS_FLT64 &dnp);
// 异单元搜索
void SearchCellNPD(IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pnt,
				   TSS_SNT32 cin, TSS_SNT32 &pid, TSS_SNT32 &cid, TSS_FLT64 &dnp);
// 批量异单元搜索
void SearchCellNPD(IDX_CELL *cidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pnt,
				   TSS_SNT32 &pid, TSS_SNT32 &cid, TSS_FLT64 &dnp, TSS_SNT32 col,
				   TSS_SNT32 *c, TSS_SNT32 *r);

// 计算搜索边界
void CalcSearchBound(TSS_FLT64 *bnd, TSS_FLT64 *spn, TSS_SNT32 col, TSS_SNT32 row,
					 TSS_FLT64 *pnt, TSS_FLT64 rad, TSS_SNT32 &c1, TSS_SNT32 &c2,
					 TSS_SNT32 &r1, TSS_SNT32 &r2);

// 搜索第3点:空圆法则
long SearchCellEMR(IDX_GRID *uidx, IDX_CELL *cell, TSS_FLT64 *ppts, TSS_SNT32 ddim,
				   TSS_FLT64 *pt1, TSS_FLT64 *pt2, TSS_SNT32 cin, TSS_SNT32 &pid,
				   TSS_SNT32 &cid, TSS_FLT64 *cen);
// 检查圆内是否存在点
void SearchCellEMR(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pt1,
				   TSS_FLT64 *pt2, TSS_FLT64 *pt3, TSS_FLT64 rad, TSS_SNT32 &pid,
				   TSS_SNT32 &cid, TSS_FLT64 *cen);
// 批量异单元搜索
long SearchCellEMR(IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_FLT64 *pt1,
				   TSS_FLT64 *pt2, TSS_SNT32 &pid, TSS_SNT32 &cid, TSS_FLT64 *cen,
				   TSS_SNT32 col, TSS_SNT32 *c, TSS_SNT32 *r);

// 插入边
long InsertFace(CTssHash *AFH, CTssHash *BFH, TSS_SNT32 *ppid, TIN_FACE *face);

// 搜索第3点:空圆法则
long SearchCell(CTssHash *BFH, IDX_GRID *uidx, TSS_FLT64 *ppts, TSS_SNT32 ddim, TSS_SNT32 *stop,
				TSS_SNT32 *pid,	TSS_SNT32 &cid);
// 方向约束搜索
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);
// 批量单元方向约束搜索
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);

// 判断是否共线
long IsLine(TSS_FLT64 *pt1, TSS_FLT64 *pt2, TSS_FLT64 *pt3);
// 计算同侧符号
long IsSide(TSS_FLT64 *pt1, TSS_FLT64 *pt2, TSS_FLT64 *pt3);

#endif // _TIN_CORE_H_