《空间数据结构的转换课件》由会员分享，可在线阅读，更多相关《空间数据结构的转换课件（54页珍藏版）》请在金锄头文库上搜索。
1、空间数据结构的转换空间数据结构的转换空间数据结构的转换课件矢量数据向栅格数据转换矢量数据向栅格数据转换n在矢量表示的多边形边界内部的在矢量表示的多边形边界内部的所有栅格上赋予相应的多边形编所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。号，从而形成栅格数据阵列。空间数据结构的转换课件（1）内部点扩散算法）内部点扩散算法n将将矢矢量量图图栅栅格格化化，每每个个面面域域多边形选择一个种子点；多边形选择一个种子点；n判判断断种种子子点点的的8个个相相邻邻栅栅格格是是否在多边形的边界上；否在多边形的边界上；n进进行行新新的的扩扩散散运运算算，直直至至所所有有新新老老种种子子点点填填满满该该多多边
2、边形形并遇到边界为止。并遇到边界为止。 内部点扩散原理内部点扩散原理空间数据结构的转换课件n算法程序设计比算法程序设计比较复杂；当栅格较复杂；当栅格尺寸取的不合理尺寸取的不合理时，会造成多边时，会造成多边形不连通。形不连通。 多边形不连通实例多边形不连通实例空间数据结构的转换课件（2）射线算法）射线算法 n由待定栅格向任意由待定栅格向任意方向引射线，判断方向引射线，判断该射线与某个多边该射线与某个多边形所有边界的相交形所有边界的相交总次数。总次数。 射线法判断原理射线法判断原理空间数据结构的转换课件n运算量很大运算量很大n当射线与多边性边界相切、重合时会影当射线与多边性边界相切、重合时会影响交
3、点数的统计响交点数的统计 空间数据结构的转换课件（3）扫描算法）扫描算法 n行扫描算法行扫描算法n扫描线算法扫描线算法n带扫描算法带扫描算法空间数据结构的转换课件行扫描算法行扫描算法n每两次遇到同一多边形的边界时，其间的栅格属于该每两次遇到同一多边形的边界时，其间的栅格属于该多边形多边形行扫描原理行扫描原理空间数据结构的转换课件扫描线算法扫描线算法 2j+1P1P3n1ii+1jP2空间数据结构的转换课件带扫描算法带扫描算法 空间数据结构的转换课件（4）复数积分算法）复数积分算法 n对整个栅格矩阵的栅格单元逐个判断其对整个栅格矩阵的栅格单元逐个判断其所属多边形的编号。所属多边形的编号。n由待判
4、定点对每个多边形的封闭边界计由待判定点对每个多边形的封闭边界计算复数积分，若积分值为算复数积分，若积分值为2i，则赋予该，则赋予该多边形编号。多边形编号。 空间数据结构的转换课件（5）边界代数算法）边界代数算法 n将将覆覆盖盖该该多多边边形形的的面面域域进进行行整整体体栅栅格格化化，并并对对栅栅格格阵阵进进行行零零初始化。初始化。n由由其其边边界界上上某某一一点点开开始始顺顺时时针针方方向向搜搜索索其其边边界界线线。循循环环一一周，回到起点。周，回到起点。 ABDEa空间数据结构的转换课件ABDEaABDE-a-a-a-a-a-a-a-a-a-a-aA-B空间数据结构的转换课件ABDEa a
5、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 aaaaa aaaa a aa aaaaaa aaaaaaE-A空间数据结构的转换课件边界代数法原理扩展边界代数法原理扩展n从某一位置开始，对图中的所有弧段逐从某一位置开始，对图中的所有弧段逐条搜索条搜索n当弧段上行时，将该弧段与左图框之间的栅当弧段上行时，将该弧段与左图框之间的栅格加上一个值格加上一个值=（该弧的左多边形编号）（该弧的左多边形编号）-（该弧的右多边形编号）（该
6、弧的右多边形编号）n当弧段下行时，将该弧段与左图框之间内的当弧段下行时，将该弧段与左图框之间内的栅格加上一个值栅格加上一个值=（该弧的右多边形编号）（该弧的右多边形编号）-（该弧的左多边形编号）（该弧的左多边形编号）n当弧段平行栅格行行走时，不做运算。当弧段平行栅格行行走时，不做运算。 空间数据结构的转换课件DBAECFGHIa=3b=4c=6空间数据结构的转换课件弧段名称弧段名称行走性质行走性质左左多多边边形形编编码码右右多多边边形形编编码码代数运算值代数运算值AB上行上行03-3BC平行平行430CD平行平行030DE下行下行033EA平行平行030BF上行上行04-4FG平行平行040G
7、C下行下行044HI下行下行066IH上行上行06-6空间数据结构的转换课件DBAECFGHI-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 333空间数据结构的转换课件DBAECFGHI33333 3 3 3333333 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 4
8、44空间数据结构的转换课件H-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 3 3 3 3 333I-H44444444 4 44 44444 444 4444 444666 666空间数据结构的转换课件栅格数据向矢量数据转换栅格数据向矢量数据转换 n多边形边界提取多边形边界提取n边界线搜索边界线搜索n拓扑关系生成拓扑
9、关系生成n去除多余点并进行曲线圆滑去除多余点并进行曲线圆滑空间数据结构的转换课件栅格数据向矢量数据转换栅格数据向矢量数据转换 n基于图像处理的矢量化基于图像处理的矢量化n基于窗口匹配的矢量化基于窗口匹配的矢量化 空间数据结构的转换课件基于图像处理的矢量化算法基于图像处理的矢量化算法 n图像二值化图像二值化n对扫描获得的灰度图像进行对扫描获得的灰度图像进行0 0或或1 1的简化处理。的简化处理。 空间数据结构的转换课件n平滑平滑 （图像预处理）（图像预处理）0000101101去毛刺模板去毛刺模板去孔洞模板去孔洞模板空间数据结构的转换课件空间数据结构的转换课件n细化细化 n保证细化后曲线的连通性
10、保证细化后曲线的连通性n细化结果是原曲线的中心线细化结果是原曲线的中心线n保留线端点保留线端点 空间数据结构的转换课件n剥皮法剥皮法: :从线的边沿两侧开始，每次剥去从线的边沿两侧开始，每次剥去等于一个栅格宽度的一层，直到最后仅等于一个栅格宽度的一层，直到最后仅剩下彼此相连的两个栅格宽或恰好一个剩下彼此相连的两个栅格宽或恰好一个栅格宽的线划图形为止。栅格宽的线划图形为止。空间数据结构的转换课件空间数据结构的转换课件n骨架法骨架法 :针对各条矢量化的栅格线，求出针对各条矢量化的栅格线，求出线上每一栅格的线上每一栅格的3*33*3窗口的属性码之和，窗口的属性码之和，并重复赋值；每一行中最大栅格属性
11、码并重复赋值；每一行中最大栅格属性码所在位置即为栅格线的骨架。所在位置即为栅格线的骨架。 空间数据结构的转换课件110000111000011100001100011100001100空间数据结构的转换课件455376130132165478756623300000135420空间数据结构的转换课件001010000000000011100000000000001000空间数据结构的转换课件经典算法经典算法 nN(p)为为p的邻点的数值的和；的邻点的数值的和；nT(p)为像素邻点从为像素邻点从0变为变为1的次数；的次数；n 分别是像素左侧、右分别是像素左侧、右侧、下边、上边邻点的数值。侧、下边
12、、上边邻点的数值。 空间数据结构的转换课件11111111111111111111111111111111111111111空间数据结构的转换课件n如果如果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转到第一步。转到第一步。空间数据结构的转换课件空
13、间数据结构的转换课件1111111111111111111111111111111空间数据结构的转换课件跟踪跟踪 n从图幅西北角开始，用水平扫描线检测线段的从图幅西北角开始，用水平扫描线检测线段的起点；起点；n以当前点为中心，寻找属性编码相同的下一点；以当前点为中心，寻找属性编码相同的下一点；n若找到，则将所找到的点置为当前点，转第若找到，则将所找到的点置为当前点，转第（2）步；若未找到，则跟踪结束；）步；若未找到，则跟踪结束；n将全部点的坐标数据顺序写入弧段数据文件；将全部点的坐标数据顺序写入弧段数据文件；n判断是否跟踪完毕。判断是否跟踪完毕。空间数据结构的转换课件n链式编码（弗里曼码）链式
14、编码（弗里曼码） n用曲线出发点坐标和线的斜率来描述二用曲线出发点坐标和线的斜率来描述二值线图形。值线图形。空间数据结构的转换课件3 3 2 2 1 14 4 p p 0 05 5 6 6 7 7空间数据结构的转换课件n矢量线提取矢量线提取 n将每个点链转化为一条矢量线，每条线将每个点链转化为一条矢量线，每条线由一系列点组成。由一系列点组成。 空间数据结构的转换课件基于窗口匹配的矢量化算法基于窗口匹配的矢量化算法n通过边界提取，将边界的左右多边通过边界提取，将边界的左右多边形信息保存在边界点上，每条边界形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分弧段由两个并行的边界链组成，分别
15、记录该边界弧段的左右多边形编别记录该边界弧段的左右多边形编号。号。 空间数据结构的转换课件aabbababaaabaabaabbbabaa边界点和节点提取边界点和节点提取 如果窗口内如果窗口内4个栅格有两个属性编码，则该个栅格有两个属性编码，则该4个栅格为边界点个栅格为边界点 空间数据结构的转换课件abcdaacdabddabadabcbabcaabbdabba窗口内窗口内4个栅格有个栅格有3个以上不同属性编码，或对角个以上不同属性编码，或对角线上栅格属性编码两两相同，作为节点处理线上栅格属性编码两两相同，作为节点处理 边界点和节点提取边界点和节点提取 空间数据结构的转换课件边界搜索与左右多边
16、形信息记录边界搜索与左右多边形信息记录 n记录起始边界点的两个多边形编号记录起始边界点的两个多边形编号作为该弧段的左右多边形作为该弧段的左右多边形n下一点的搜索方向由前一点的进入下一点的搜索方向由前一点的进入方向和该点的可能走向来决定方向和该点的可能走向来决定 空间数据结构的转换课件aabbababaaabaabaabbbabaa空间数据结构的转换课件aaaaaaaaaabbbbbbbbbbbbbbbccccccccccccdddddddd空间数据结构的转换课件aaaaaaaaaabbbbbbbbbbbbbbbccccccccccccdddddddd边界点边界点节点节点空间数据结构的转换课件多余点去除多余点去除 n在一个弧段上连续的三个点，如满足直在一个弧段上连续的三个点，如满足直线方程，则中间点为多余。线方程，则中间点为多余。或或 空间数据结构的转换课件曲线平滑曲线平滑 n根据原曲线坐标链的坐标，构建一个曲根据原曲线坐标链的坐标，构建一个曲线函数，用这个函数计算的插值点坐标线函数，用这个函数计算的插值点坐标拟合原坐标链。拟合原坐标链。 空间数据结构的转换课件空间数据结构的转换课件空间数据结构的转换课件空间数据结构的转换课件XYP1P2P3P4U=-1U=0U=1U=2U=-2/3U=-1/3U=1/3U=2/3U=4/3U=5/3空间数据结构的转换课件
