空间数据结构的转换

《空间数据结构的转换》由会员分享，可在线阅读，更多相关《空间数据结构的转换（54页珍藏版）》请在装配图网上搜索。

1、空间数据结构的转换空间数据结构的转换矢量数据向栅格数据转换矢量数据向栅格数据转换n在矢量表示的多边形边界内部的在矢量表示的多边形边界内部的所有栅格上赋予相应的多边形编所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。号，从而形成栅格数据阵列。（1）内部点扩散算法）内部点扩散算法n将矢量图栅格化，每个面域将矢量图栅格化，每个面域多边形选择一个种子点；多边形选择一个种子点；n判断种子点的判断种子点的8个相邻栅格是个相邻栅格是否在多边形的边界上；否在多边形的边界上；n进行新的扩散运算，进行新的扩散运算，直至所直至所有新老种子点填满该多边形有新老种子点填满该多边形并遇到边界为止。并遇到边界为止。内

2、部点扩散原理内部点扩散原理n算法程序设计比算法程序设计比较复杂；当栅格较复杂；当栅格尺寸取的不合理尺寸取的不合理时，会造成多边时，会造成多边形不连通。形不连通。多边形不连通实例多边形不连通实例（2）射线算法）射线算法 n由待定栅格向任意由待定栅格向任意方向引射线，判断方向引射线，判断该射线与某个多边该射线与某个多边形所有边界的相交形所有边界的相交总次数。总次数。射线法判断原理射线法判断原理n运算量很大运算量很大n当射线与多边性边界相切、重合时会影当射线与多边性边界相切、重合时会影响交点数的统计响交点数的统计（3）扫描算法）扫描算法 n行扫描算法行扫描算法n扫描线算法扫描线算法n带扫描算法带扫描

3、算法行扫描算法行扫描算法n每两次遇到同一多边形的边界时，其间的栅格属于该每两次遇到同一多边形的边界时，其间的栅格属于该多边形多边形行扫描原理行扫描原理扫描线算法扫描线算法 2j+1P1P3n1ii+1jP2iiiiipiyyxxxxyy111jjjjjpjyyxxxxyy112带扫描算法带扫描算法（4）复数积分算法）复数积分算法 n对整个栅格矩阵的栅格单元逐个判断其对整个栅格矩阵的栅格单元逐个判断其所属多边形的编号。所属多边形的编号。n由待判定点对每个多边形的封闭边界计由待判定点对每个多边形的封闭边界计算复数积分，若积分值为算复数积分，若积分值为2i，则赋予该，则赋予该多边形编号。多边形编号。

4、（5）边界代数算法）边界代数算法 n将覆盖该多边形的将覆盖该多边形的面域进行整体栅格面域进行整体栅格化，并对栅格阵进化，并对栅格阵进行零初始化。行零初始化。n由其边界上某一点由其边界上某一点开始顺时针方向搜开始顺时针方向搜索其边界线。索其边界线。循环循环一周，回到起点。一周，回到起点。ABDEaABDEaABDE-a-a-a-a-a-a-a-a-a-a-aA-BABDEa a a a a a aa a a a a aa aaa aa aaaa aaaaa aaaa a aa aaaaaa aaaaaaB-D-EABDEa a a a a a aa a a a a aa aaa aa aaaa

5、aaaaa aaaa a aa aaaaaa aaaaaaE-A边界代数法原理扩展边界代数法原理扩展n从某一位置开始，对图中的所有弧段逐从某一位置开始，对图中的所有弧段逐条搜索条搜索n当弧段上行时，将该弧段与左图框之间的栅当弧段上行时，将该弧段与左图框之间的栅格加上一个值格加上一个值=（该弧的左多边形编号）（该弧的左多边形编号）-（该弧的右多边形编号）（该弧的右多边形编号）n当弧段下行时，将该弧段与左图框之间内的当弧段下行时，将该弧段与左图框之间内的栅格加上一个值栅格加上一个值=（该弧的右多边形编号）（该弧的右多边形编号）-（该弧的左多边形编号）（该弧的左多边形编号）n当弧段平行栅格行行走时，

6、不做运算。当弧段平行栅格行行走时，不做运算。DBAECFGHIa=3b=4c=6弧段名称弧段名称行走性质行走性质左多边形编左多边形编码码右多边形编右多边形编码码代数运算值代数运算值AB上行上行03-3BC平行平行430CD平行平行030DE下行下行033EA平行平行030BF上行上行04-4FG平行平行040GC下行下行044HI下行下行066IH上行上行06-6DBAECFGHI-3-3-3-3-3-3-3-3-3-3-3-3-3A-BB-C-D-E-ADBAECFGHI33333 3 3 3333333 3 3 33333 3 3 3 3 333DBAECFGHI33333 3 3 333

7、3333 3 3 33333 3 3 3 3 333B-F-4-4-4-4-4-4-4-4-4DBAECFGHI33333 3 3 3333333 3 3 33333 3 3 3 3 333B-C-D-E-A44444444 4 44 44444 444 4444 444H-IDBAECFGHI33333 3 33333333 3 3 33333 3333 33366666644 4 4101010 10 10 10 6101010 10 1010 1010101010 10 101010 106 666 6666666IDBAECFGHI33333 3 3 3333333 3 3 33333

8、 3 3 3 3 333I-H44444444 4 44 44444 444 4444 444666 666栅格数据向矢量数据转换栅格数据向矢量数据转换 n多边形边界提取多边形边界提取n边界线搜索边界线搜索n拓扑关系生成拓扑关系生成n去除多余点并进行曲线圆滑去除多余点并进行曲线圆滑栅格数据向矢量数据转换栅格数据向矢量数据转换 n基于图像处理的矢量化基于图像处理的矢量化n基于窗口匹配的矢量化基于窗口匹配的矢量化 基于图像处理的矢量化算法基于图像处理的矢量化算法 n图像二值化图像二值化n对扫描获得的灰度图像进行对扫描获得的灰度图像进行0 0或或1 1的简化处理。的简化处理。n平滑平滑（图像预处理）

9、（图像预处理）000010110去毛刺模板去毛刺模板去孔洞模板去孔洞模板n细化细化 n保证细化后曲线的连通性保证细化后曲线的连通性n细化结果是原曲线的中心线细化结果是原曲线的中心线n保留线端点保留线端点 n剥皮法剥皮法:从线的边沿两侧开始，每次剥去从线的边沿两侧开始，每次剥去等于一个栅格宽度的一层，直到最后仅等于一个栅格宽度的一层，直到最后仅剩下彼此相连的两个栅格宽或恰好一个剩下彼此相连的两个栅格宽或恰好一个栅格宽的线划图形为止。栅格宽的线划图形为止。n骨架法骨架法:针对各条矢量化的栅格线，求出针对各条矢量化的栅格线，求出线上每一栅格的线上每一栅格的3 3*3 3窗口的属性码之和，窗口的属性码

10、之和，并重复赋值；每一行中最大栅格属性码并重复赋值；每一行中最大栅格属性码所在位置即为栅格线的骨架。所在位置即为栅格线的骨架。110000111000011100001100011100001100455376130132165478756623300000135420001010000000000011100000000000001000经典算法经典算法 nN(p)为为p的邻点的数值的和；的邻点的数值的和；nT(p)为像素邻点从为像素邻点从0变为变为1的次数；的次数；n 分别是像素左侧、右分别是像素左侧、右侧、下边、上边邻点的数值。侧、下边、上边邻点的数值。NSEWpppp,11111111

11、111111111111111111111111111111111n如果如果2N(p)62N(p)6并且并且T(p)=1T(p)=1并且并且 =0=0并且并且 =0=0，则标志，则标志p p点；点；n将所有被标志的栅格点赋值为将所有被标志的栅格点赋值为0 0；n如果如果2N(p)62N(p)6并且并且T(p)=1T(p)=1并且并且 =0=0并且并且 =0=0，则标志，则标志p p点；点；n将所有被标志的栅格点赋值为将所有被标志的栅格点赋值为0 0；n转到第一步。转到第一步。NSEpppSEWpppNSWpppNEWppp1111111111111111111111111111111跟踪跟踪

12、n从图幅西北角开始，用水平扫描线检测线段的从图幅西北角开始，用水平扫描线检测线段的起点；起点；n以当前点为中心，寻找属性编码相同的下一点；以当前点为中心，寻找属性编码相同的下一点；n若找到，则将所找到的点置为当前点，转第若找到，则将所找到的点置为当前点，转第（2）步；若未找到，则跟踪结束；）步；若未找到，则跟踪结束；n将全部点的坐标数据顺序写入弧段数据文件；将全部点的坐标数据顺序写入弧段数据文件；n判断是否跟踪完毕。判断是否跟踪完毕。n链式编码（弗里曼码）链式编码（弗里曼码）n用曲线出发点坐标和线的斜率来描述二用曲线出发点坐标和线的斜率来描述二值线图形。值线图形。3 3 2 2 1 14 4

13、p p 0 05 5 6 6 7 7n矢量线提取矢量线提取 n将每个点链转化为一条矢量线，每条线将每个点链转化为一条矢量线，每条线由一系列点组成。由一系列点组成。基于窗口匹配的矢量化算法基于窗口匹配的矢量化算法n通过边界提取，将边界的左右多边通过边界提取，将边界的左右多边形信息保存在边界点上，每条边界形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编别记录该边界弧段的左右多边形编号。号。aabbababaaabaabaabbbabaa边界点和节点提取边界点和节点提取 如果窗口内如果窗口内4个栅格有两个属性编码，则该个栅格有两

14、个属性编码，则该4个栅格为边界点个栅格为边界点 abcdaacdabddabadabcbabcaabbdabba窗口内窗口内4个栅格有个栅格有3个以上不同属性编码，或对角个以上不同属性编码，或对角线上栅格属性编码两两相同，作为节点处理线上栅格属性编码两两相同，作为节点处理 边界点和节点提取边界点和节点提取 边界搜索与左右多边形信息记录边界搜索与左右多边形信息记录 n记录起始边界点的两个多边形编号记录起始边界点的两个多边形编号作为该弧段的左右多边形作为该弧段的左右多边形n下一点的搜索方向由前一点的进入下一点的搜索方向由前一点的进入方向和该点的可能走向来决定方向和该点的可能走向来决定 aabbab

15、abaaabaabaabbbabaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccccddddddddaaaaaaaaaabbbbbbbbbbbbbbbccccccccccccdddddddd边界点边界点节点节点多余点去除多余点去除 n在一个弧段上连续的三个点，如满足直在一个弧段上连续的三个点，如满足直线方程，则中间点为多余。线方程，则中间点为多余。31312121yyxxyyxx31313232yyxxyyxx或或 曲线平滑曲线平滑 n根据原曲线坐标链的坐标，构建一个曲根据原曲线坐标链的坐标，构建一个曲线函数，用这个函数计算的插值点坐标线函数，用这个函数计算的插值点坐标拟合原坐标链。拟合原坐标链。niiiniiiuByyuBxx11 njijjinjijjiuuuuuB11ni,2,1 uBxuBxuBxuBxx443321211 uByuByuByuByy44322211XYP1P2P3P4U=-1U=0U=1U=2U=-2/3U=-1/3U=1/3U=2/3U=4/3U=5/3