lecture5数据结构转换

1、空间数据结构的转换学习目标：学习目标： 矢量数据结构转栅格数据的方法 栅格数据转矢量数据的步骤和方法重点：扫描线算法、图像数据矢量化栅格与矢量模式的选择与转换 栅格和矢量均有各自的特点。栅格和矢量均有各自的特点。 从点、线、面实体转化为规则单元，这从点、线、面实体转化为规则单元，这是是矢量数据栅格化矢量数据栅格化。 从栅格单元转换到几何图形的过程，称从栅格单元转换到几何图形的过程，称为为栅格数据矢量化栅格数据矢量化。栅格与矢量数据格式之间的转换点的转换点的转换简单的坐标转换，把坐标点转换成行号和列号可简单的坐标转换，把坐标点转换成行号和列号可。YXOJIyx(0,0)XminXmaxYmin其

2、行、列坐标i，j可由下式求出：11iiyiDxjDp 线（弧段）的转换曲线在数字化时输入多个点，形成折线，由于点多而密集，折线在视觉上就形成曲线。按解析几何中的两点式直线方程，根据栅格精度要求，在每两坐标之间插入一系列栅格单元，每个坐标点转换为行列坐标。 方法可以分为：数据管理和转换计算两个步骤 转换计算DDA法（数字微分分析方法） BAG（x1,y1）（xi,yj）（xi+1,yj+1）C1C2（x2,y2）（x3,y3）0121121iiiyyyyyyxxxx点的转换点的转换线（弧段）的转换线（弧段）的转换p方法：内部点扩散法、射线算法、扫描法（行扫描、方法：内部点扩散法、射线算法、扫描法

3、（行扫描、扫描线、带扫描）、边界填充法（边界代数算法，扫描线、带扫描）、边界填充法（边界代数算法，boundary algebra filling, BFA）扫描线算法扫描线算法面的转换以多边形作为栅格化的处理单元面的转换以多边形作为栅格化的处理单元扫描线算法步骤扫描线算法步骤第一步：提取面域多边形的边界坐标数据文件第一步：提取面域多边形的边界坐标数据文件第二步：边界上任选一点开始，分别按顺时针和逆时针方向将该面第二步：边界上任选一点开始，分别按顺时针和逆时针方向将该面域的所有边界点的域的所有边界点的x坐标排队：坐标排队：x1,x2,x3,xn或或xn,xn-1,xn-2,x1；第三步：根据待

4、定栅格第三步：根据待定栅格P(XP,YP)的的X坐标，判断坐标，判断XP分别落在上述两分别落在上述两组队烈的区间位置，并找组队烈的区间位置，并找P点坐在各区间位置的左右点坐在各区间位置的左右X坐标（坐标（xi-xi+1),如顺时针队列中的第一区间为如顺时针队列中的第一区间为S1,S2,Sm;逆时针队列中的逆时针队列中的区间依次为区间依次为Sm,Sm-1,S1;第四步：按线性内插算法，分别计算个区间内对应的第四步：按线性内插算法，分别计算个区间内对应的XP的的YK值值（K=1,2,3,m）11()pikiiiiixxyyyyxx扫描线算法步骤扫描线算法步骤第五步：计算顺逆时针方向的两组中间参数第

5、五步：计算顺逆时针方向的两组中间参数Ak和和Bk(对于顺对于顺时针有时针有k=k,对于逆时针有对于逆时针有k=m-k+1,),其中其中k=1,2,3,m)Ak=1 -1 Bk=1 -1 kpkpyyyykpkpyyyy第六步：若第六步：若 ，计数，计数Nk=1；否则；否则 Nk=0；并累计；并累计()2kkkCAB1kmkkNN第七步：判断：若第七步：判断：若N/2为奇数，则为奇数，则P栅格位于本域多边形栅格位于本域多边形 内，内，否则位于本域多边形外否则位于本域多边形外扫描线法例题扫描线法例题n12ii+1p1yxp3p2p4p5区间区间Sk待定点AkBkCkN/2在否S1S2S3S4S1S

6、2S3S4C1C2C3C4P1-1-1-1-1111100000nP21-1-1-1111-120021yP311-1-111-1-122222nP4111-11-1-1-120021yP51111-1-1-1-100000n2)栅格转矢量（图像数据、再生栅格数据）p将栅格数据分析的结果，通过矢量绘图装置输出 p数据压缩 p自动扫描仪获取的栅格数据加入矢量形式的数据库 图像数据矢量化：3个步骤p二值化p细化（骨架化）p追踪图像数据矢量化图像数据矢量化二值化一般情况下，栅格数据是按一般情况下，栅格数据是按0255的不同灰度值表达的不同灰度值表达的。为了简化追踪算法，需把的。为了简化追踪算法，需把

7、256个灰阶压缩为个灰阶压缩为2个灰个灰阶，即阶，即0和和1两级。为此，假设任一格网的灰度值为两级。为此，假设任一格网的灰度值为G,阈值为阈值为T，那么，根据下式就可以得到二值图（，那么，根据下式就可以得到二值图（b）。）。 TjiGTjiGjiB),(0),(1),(如果如果 （a） (b) (c) (d)栅格-矢量转换过程图像数据矢量化图像数据矢量化细化细化是消除线划横断面栅格数的差异，使得每一条线只保留代细化是消除线划横断面栅格数的差异，使得每一条线只保留代表其轴线或周围轮廓线（对多边形而言）位置的单个栅格的宽表其轴线或周围轮廓线（对多边形而言）位置的单个栅格的宽度。对于栅格线划的度。对

8、于栅格线划的“细化细化”方法，可分为方法，可分为 “剥皮法剥皮法”和和“骨架化骨架化”两大类。剥皮法的实质是剥掉等于一个栅格宽的一两大类。剥皮法的实质是剥掉等于一个栅格宽的一层，直到最后留下彼此连通的由单个栅格点组成的图形层，直到最后留下彼此连通的由单个栅格点组成的图形(c)。一。一个个33的栅格窗口，其中心栅格有八个邻域，因此组合图共有的栅格窗口，其中心栅格有八个邻域，因此组合图共有28种不同的排列格式，若将相对位置关系的差异只是转置种不同的排列格式，若将相对位置关系的差异只是转置900、1800、2700或互为镜象反射的方法进行归并，则共有或互为镜象反射的方法进行归并，则共有51种排列种排

9、列格式。显然，其中只有格式格式。显然，其中只有格式2、3、4、5、10、11、12、16、21、24、28、33、34、35、38、42、43、46和和50，可以将中心点剥，可以将中心点剥去。这样，通过最多核查去。这样，通过最多核查2568个栅格个栅格 （a） (b) (c) (d)栅格-矢量转换过程123456789101112131415161718282930313233343536242526271920212223464748495051424344453738394041图像数据矢量化图像数据矢量化跟踪 跟踪的目的是将写入数据文件的细化处理后的栅格数据，整理为跟踪的目的是将写入数据文件的细化处理后的栅格数据，整理为从结点出发的线段或闭合的线条，并以矢量形式存储于特征栅格从结点出发的线段或闭合的线条，并以矢量形式存储于特征栅格点中心的坐标点中心的坐标(d)。跟踪时，从图幅西北角开始，按顺时针或逆。跟踪时，从图幅西北角开始，按顺时针或逆时针方向，从起始点开始，根据八个邻域进行搜索，依次