空间数据组织算法.ppt

《空间数据组织算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、空间数据组织算法《地理信息系统算法基础》第六章1本讲内容1矢量数据的压缩2栅格数据的压缩3拓扑关系的生成21矢量数据的压缩矢量数据的压缩包括两个方面的内容：一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀；二是对矢量坐标数据重新进行编码，以减少所需要的存储空间。矢量数据的压缩往往是不可逆的，数据压缩后，数据量变小了，数据的精度降低了。31矢量数据的压缩1.1间隔取点法1.2垂距法和偏角法1.3道格拉斯-普克法1.4光栏法1.5曲线压缩算法的比较1.6面域的数据压缩算法41.1间隔取点法原理：每隔K个点取一点，或舍去那些离已选点比规定距离更近的点，但首、末点一定要保

2、留，如图5.1所示。优缺点：可大量压缩数字化仪用连续方法获取的点列中的点、曲率显著变化的点，但不一定能恰当地保留方向上曲率显著变化的点。51.2垂距法和偏角法原理：按垂距或偏角的限差，选取符合或超过限差的点。优缺点：不能同时考虑相邻点间的方向与距离，且有可能舍去不该舍去的点，但较前一种方法有进步。61.3道格拉斯-普克法原理：将一条曲线首、末点连一条直线，求出其余各点到该直线的距离，选其最大者与规定的临界值相比较，若大于临界值，则离该直线距离最大的点保留，否则将直线两端间各点全部舍去。如图5.3所示，经数据采样得到的曲线MN由点序{P1，P2，P3，…，Pn}组成，n个点

3、的坐标集为(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)。其中P1，Pn代分别对应曲线的起点M和终点N。根据应用需要和数据精度要求，给定控制数据压缩的极差为ε，ε表示为被舍弃的点偏离特征点连线之间的垂直距离。71.3道格拉斯-普克法曲线的空间数据压缩过程如下：第一步：确定曲线MN对应弦的直线方程。由起点M、终点N建立直线―方程为将上式化简为一般形式为：Ax+By+C=0第二步：求曲线MN上各点Pi到弦线MN的距离di。Pi(xi，yi)到弦线MN的距离为第三步：求距离di的最大值dh第四步：比较dh与ε的大小，并计算开关Q：81.3道格拉斯-普克法第五

4、步：决定取舍，提取中间特征点。(1)如果Q=0，则直接可以用弦线MN(M、N为特征点)代替曲线MN；转第六步。(2)如果Q=1，则将dh所对应的点Pi(Xi，yi)抽出，暂时作为中间特征点；然后连接新弦线MPj；转第一步(以MPj已代替MN，继续计算和判断)。若Q=0，则可以用弦线MPj代替曲线MPj；将Pj作为中间特征点取出；顺序排在M点之后，成为继M之后的第一个中间特征点；并连接PjN，转第一步（以PjN代替MN，继续计算和判断)……91.3道格拉斯-普克法若Q=1，则不可以用弦线MPj代替曲线MPj；找到此时dh所对应的点Pk，并连接新弦线MPk；转第一步(以MPk

5、代替MN，继续计算和判断)……第六步：形成新的数据文件。将所有提取出的中间特征点从起点M开始，顺序排列至终点N，并写入新的数据文件，即得到化简后的折线的数据文件。101.3道格拉斯-普克法如图5.3所示，曲线MN的特征点提取过程如下：(1)找到曲线MN上dh对应点位为1号点；经判断可以用弦线M1代替曲线M1，故1号点是继似点之后提取出的第一个特征点；(2)连接弦线1N；经判断，不可以用弦线1N代替曲线1N；找到曲线lN上dh的对应点位为2号点；故连接1、2号点之弦线12；经判断，还是不可以用弦线12代替曲线12；找到曲线12上dh的对应点位为3号点；再连接1、3号点之弦线

6、13；经判断，可以用弦线13代替曲线13；故3号点是继1号点之后提取出的第二个特征点；111.3道格拉斯-普克法(3)连接弦线3N；经判断，不可以用弦线3N代替曲线3N；找到曲线3N上之dh的对应点位仍为2号点；然后，连接3、2号点之弦线32；经判断，可以用弦线32代替曲线32；故2号点是继1号点、3号点之后提取出的第三个特征点；(4)连接2、N号点之弦线2N；经判断，可以用弦线2N代替曲线2N；中间特征点提取结束。至此可知，曲线MN可以用特征点M、1、3、2、N顺序连接的折线简化表示。121.4光栏法原理：预先定义的一个扇形(“喇叭口”），根据曲线上各节点是在扇形外还是

7、在扇形内，决定节点是保留还是舍去。设有曲线点列{Pi}，i=1，2，…，n，“光栏口径”为d(由用户自己定义），则该方法实施的具体步骤：(1)连接p1和p2，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p1=a2p2=d/2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以P1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的）。通过p1并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。131.4光栏法(2)若p3点