雷达图和加权图布局算法的研究与实现.doc

《雷达图和加权图布局算法的研究与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、5.3.3质心算法465.4雷达图和加权图应用举例475.5本章小结51第六章总结与展望526.1工作总结526.2展望52参考文献54致谢58第一章绪论1.1概述近年来，信息技术可视化在各个领域中得到越来越广泛的应用〔口。对信息技术可视化的研究越来越广泛，信息可视化充分利用了人类视觉感知系统，将信息以图形化方式进行展示，直观快速地解释信息的意义〔"】。种类繁多的信息源产生的大量数据，远远超出了人脑分析解释这些数据的能力。由于缺乏海量数据的有效分析手段，大量的计算资源被浪费，这严重阻碍了科学研究的进展。可视化技术作为解释海量数据

2、最有效的手段率先被科学与工程计算领域采用⑸，并发展为当前热门的研究领域——信息可视化。可视化技术把数据转换成图形，给予人们深刻与意想不到的洞察力，在很多领域使科学家的研究方式发生了根本变化。可视化技术的应用大至高速飞行模拟，小至分子结构的演示，无处不在血7】。特别是近年来，可视化数据挖掘和分析越来越被人注意，得到广泛应用【忙1.2研究背景与意义计算机科学的发展，使人们在使用计算机时，对视觉的要求越來越高。近年来，计算机用户图形界面技术迅速发展,信息可视化技术得到越来越广泛的应用。信息可视化的需求主要來自以下方面：1）当目标数据过

3、于复杂时，可以将观察焦点集中于目标信息；2）当目标数据不够直观，不利于分析时，信息可视化作为一种辅助手段帮助分析数据；3）当专业领域信息让常人难于理解时，用于辅助信息的沟通。图论是数学上的一个重要的分支，在计算机科学中，图（Graph）在许多方面都具有重要的位置。然而，图论中的图，在计算机科学中常用于研究现实世界中实体与实体Z间的关系。这种关系表现为图中抽象的拓扑关系。数据可视化常常与图论相结合。将现实世界中实体之间的关系表示成图论中的图。再将图以•种适当的方式进行展示。也就是说，数据口J视化最常用的方法之一是将数据转换为图的模

4、型，再以人们易于理解的方式表现在各种媒体上。特别是在计算机显示屏幕上。其研究的算法常称为布局算法，也称为图布局算法。布局算法已成为了当前研究的热点之一。在布局算法中要解决两个问题：1.如何将现实世界中的数据关系转换为图论中的模型；2.如何将图模型以一种较好的方式进行展示。这也是本课题研究的目标。图布局技术是信息可视化与应用数学的一个交叉领域，主要研究从图到几何空间的映射关系。图布局技术的内容极其丰富，主要是根据不同的实际应用需求,满足数据可视化的基本要求。从布局的观点来看，在图的绘制中，主要解决的是图中节点的布局问题⑴。一般，布

5、局技术研究的往往是针对特定要求下的特定图，如普通图、有向图、平面图、层次图、树图等。与此同时，还需考虑特定领域的不同数据特性。对不同类型的图采用不同的布局方法。布局技术研究中的困难主要来源于以下两方面〔儿1）布局规模。当图的规模变大时，会给布局带来诸多困难：一方面，大量的节点和连接可能会引起算法性能上的问题；另一方面，即使能够完成布局,但因为布局空间有限，布局结果将布满整个平面而变得毫无意义。多数绘图算法均在这方面存在严重制约。2）布局约束。一般可以分为两种约束，一种是来自美学标准，另一种则是实际要求，但其实质是一致的。令图G=

6、（以£）的节点坐标为％X），MX,K）为满足约束的目标函数，图的布局问题则转换为求满足min[f（XY）]时3,X）的取值问题。这是典型的组合优化问题，是NP完全问题。当前信息可视化的研究大部分集中于两个方面〔叫一是制定美学标准，使绘制的布局结构能够得到最佳的感知，从而得到更好的理解；另一个就是根据任务主题，建立不同的可视化系统，辅助用户高效直观地挖掘数据的内涵。图布局的研究已经成果颇丰，本课题的研究目标是在前人研究的基础上，能够再设计出一些实用的算法。为信息可视化再做一些贡献。在现实世界中，常有一些间接关联关系，间接关联关系从

7、一个中心岀发，以关联的层次向外辐射，成散射状。这种关系在可视化上，可以看成是以一个点为中心，若干个同心圆组成环的图。有一个焦点，即我们的关注点，在图的中心，外面是若干个环，按中心点关联的层次(或称为级)划分。因此，在第一个环上的是与中心节点有直接关联的节点，在第二个环上的节点是与中心节点间接关联,但与第一个环上节点直接关联的节点，依此类推。这样的图，我们称为雷达图(RadarPicture)o因为我们常见的雷达示意图上就是有一个中心点，外面是一圈一圈的雷达环。显然，这样的应用例子是很多的。如网络的路由结构和社会关系网络等等。本文

8、给出了一种图布局方法——雷达图，研究并实现了雷达图的布局算法，并描述了其应用前景。图的布局算法已有多人研究。其中最著名的是FR算法〔9】和KK算法卩叭鉴于其应用的广泛性，本文研究并实现了FR算法和KK算法。包括FR算法和KK算法，基本上图布局算法的研究都集中于无