定制论文·联系客服·网站地图·收藏本页·设为首页
电力当前位置:中国论文库 > 工学论文 > 电力> 正文

聚合算法在电力GIS中的应用

时间:2012-09-01作者:来源:中国论文库
字号:T|T

  地理信息系统(GeographicInformation System, GIS)在最近几年取得了重大技术进展,各类地图服务商提供多层次、多类别在线地图服务,渲染客户端可选种类繁多、渲染速度快,基于地图的信息展现

标签:

  地理信息系统(GeographicInformation System, GIS)在最近几年取得了重大技术进展,各类地图服务商提供多层次、多类别在线地图服务,渲染客户端可选种类繁多、渲染速度快,基于地图的信息展现显得更为友好、直观,使得GIS应用在各行业的信息化建设中逐渐得到普及。

  在电力系统中,GIS可以友好准确地展示如变电站、线路、杆塔、故障点、输变电管理、配电管理、用电管理等电力对象设备的具体位置和各设备之间的层次关系。但是随着网络技术的普及和各类系统的不断增加,故障点等点要素数据也在呈几何级增长,当地图上加载大量点要素数据时,会出现彼此覆盖和加载速度过慢的问题。

  据验证,当浏览器地图客户端(Flash. Silverlight或JavaScript)一次性加载超过500个点要素时会出现加载速度明显变慢的现象,超过1 000个点要素时基本造成地图客户端宕掉,亚需一种解决方案即能快速展示且不丢失数据。

  地理空间点聚合(M arkerCluster)可以依据一定的模型和算法,将分布密集的点要素聚合在一起统一展现。当矢量数据非常大时,通过聚合会大大减少浏览器客户端渲染消耗时间,从而增强系统实用性,提高系统用户体验度。

  文章以空间点聚合为出发点,通过比较当前通用的层次聚类算法和划分算法两大类聚合算法及与GIS结合的优缺点,依据划分算法思想,设计并实现一种l决速空间点聚合算法,通过该算法可以很好地解决海量电力设备资产的客户端展现能力。

  聚合算法本质为将集合内具有相似性或相关性的一类或多类对聚合为一个对象,从而达到降低复杂因子的目的,方便分析问题。目前比较通用的聚合算法有层次聚类算法和划分算法等两大类。文章将分别对这2类算法思想做分析和比较。

  层次聚类算法原理为预先定义要聚类的K的对象集合以及KXK的相互间隔矩阵(或者是相似性规则矩阵),层次聚类算法的基本操作步骤如下所列。

  1)整理待聚类对象集合。

  2)将单个对象划分为一类,共计得到 K 类,每类仅且只包含1 个对象。约定类 i 和类 j 的间距为它们所包含的对象之间的最小距离。

  3)找到距离最接近的 2 个类(对象)并合并成 1 个类(对象),于是总的类数少了 1 个。

  4)然后重新算出新的类(对象)和所有未合并的对象之间的距离

  5)重复以上第 3~4 步,直到把所有类合并为 1 个类(对象)为止,此类含有的对象个数为 K。

  6)根据步骤 4 的不同,层次聚类算法可以细分为完整连结法、单一连结法、平均法聚类法等。

  1.2 划分算法

  划分算法基本实现原理为确定一个区间,把符合特定条件的元素放到这个区间中,具体步骤如下所列。

  1)定义 2 个指针 ki 和 kj,初始化 ki 和 kj 区间的下界和上界,即 ki=lowCell,ki=hkighCell;选取无序区的第 1 个对象 V[ki]( 即V[lowCell]) 作为基准对象,并将它保存在变量 node 中。

  2)令 kj 自 hkighCell 起向左依次遍历,直至找到第 1 个主键数值小于 node.key 的对象 V[kj],将 V[kj] 移至 ki 所指的位置上。此 步 相 当 于 V[kj] 和 基 准 V[ki]( 即 node) 进行了交换,使主键小于基准主键 node.key 的记录进行左移。

  3)令 ki 指针自 ki+1 位置向右开始遍历,直至找到第 1 个主键数值大于 node.key 的对象标记为 V[ki],将 V[ki] 移到 ki 所指的位置上,相当于对 V[ki] 和基准 V[kj] 进行了交换,使主键大于基准主键的记录移到了基准的右边,交换后 V[ki] 中又相当于存放了 node。

  4)依据步骤 3 的结果,令指针 kj 从位置 kj-1 开始向左遍历,如此重复,对遍历方向进行交替改变,从两端向中间部分进行靠拢,直 至 ki=kj 时,ki 便 是 基 准node 最终的位置,将 node 放置在此位置点上就完成了一次划分。

  通过比较上述 2 类算法可以得出:层次聚类算法时间复杂度为 T(n)=n2;划分算法时间复杂度为 T(n)=nlog2n。划分算法具有较高的执行效率,但是层次方法在算法上和真实数据的特性吻合度高,相对于划分方法聚类的实际效果比较好,能够更好地服务于生产运行,所以在应用时需根据不同的目的做相应选择或改进。

  2 GIS 应用点聚合的算法设计

  以上描述了 2 类聚合算法与GIS 应用结合的目的在于减少一次性渲染对象个数,提高客户端显示效率,增强用户体验度。

  层次聚类算法需要首先对地图展现屏幕划分为 N×N 个地理方格,然后依次计算待聚合空间点集合的子对象坐落于哪个方格内部,从而实现聚合。该算法实现容易,但是需要遍历所有地理方格,因此比较耗时。

  划分算法思想则不同,直接归纳到对象集合,减少了 CPU 计算时间,结合 GIS 实际技术特点,得出在 GIS 中聚合实现思想为:当前显示比例下,聚合中心点为(0,0),选取聚合半径(Distance)为 20 像素的空间对象集合,则聚合几何对象(Cluster Geometry)将展现所有的距离不超过 20 屏幕像素单位的点要素。这种设计思想的优势为实现方便而且效率很高。具体实现步骤如下所列。

  1)定义相关参数,包括待聚合空间点对象集合(features)、聚合后空间对象集合(clusters)、聚合半径(Distance)、当前比例地图分辨率(Resolution)。

  2)依次遍历 features 对象,首 先 得 到 A=features[i(]i=0、1、2……、features.length)。

  3)依次遍历 clusters 对象,得到 B=clusters[j(]j=0、1、2……、clusters.length)。

  4)判 断 A 与 B 对 象 中 心点距是否超过 Distance,如果小 Distance,则把 A 对象添加至clusters[j] 集合内,并返回第 2 步继续执行;如果大于 Distance 则范围第 3 步继续执行。

  5)当第 4 步完全执行完毕,仍未归纳 A 对象时,需要把 A 当做新的聚合体添加至 clusters,而clusters 个数增加 1 个。继续从第 2 步开始执行。

  6)当 features 所有对象遍历完毕后,聚合结束。

  7)在 GIS 中展现聚合几何对象。

  划分算法在 GIS 中应用难点为第 4 步如何判断 A 与 B 距离,第 1 步需要得到 B 对象的地理中心坐标,第 2 步需要根据当前 地 图 投 影(Projection)、地 图比例(Scale)及地图显示分辨率(Resolution)等三大影响因子把A 与 B 的地理距离转换为屏幕像素距离,然后与 Distance 做比较。

  3 算法实现

  3.1 划分算法和电力 GIS 结合实现为了验证上述算法的有效性和实用性,根据图 1 聚合算法流4 结语文章重点以 GIS 聚合算法为基础,在比较层次聚类算法和划分算法的基础上,详细介绍了划分算法在 GIS 聚合中的设计和实现。

  GIS 聚合算法应用广泛,不仅可以减少每次空间点渲染个数,提高地图渲染客户端效率,能够很好地解决海量电力设备节点的展现问题,而且可以进一步改进算法,实现GIS 热点跟踪专题图,如事件发生频率、人口出生分布密度等,通过GIS 直观展示后,可以更容易发现问题,为上层决策提供重要技术依据,GIS 聚合算法在其他行业中也有着广泛的应用,具有很好的应用和推广价值。

转贴于中国论文库 http://www.lwkoo.com

    相关阅读

    推荐论文

    热门

    最新

    推荐