空间数据结构的可视化: 四个抽象层次的研究

理论计算机科学电子笔记178（2007）89-99www.elsevier.com/locate/entcs不同抽象Jussi Nikander尤西·尼坎德1，5 Ari Korhonen阿里·科尔霍宁2，5赫尔辛基理工芬兰埃斯波Eiri Valanto3 Kirsi Virrantaus4赫尔辛基理工芬兰埃斯波摘要空间数据结构用于操作位置数据。这种结构的可视化面临着许多与一维数据可视化无关的挑战。可视化数据可以使用几种不同类型的视觉隐喻来表示。根据可视化的目的，这些隐喻可以分为几个不同的抽象层次。 本文提出将数据结构可视化分为四个抽象层次，并展示了这些抽象可以在空间数据结构的可视化中考虑关键词：可视化，空间数据算法，抽象1介绍空间数据结构是存储空间数据的结构。 空间（Spatial）是一个术语，用于指位于任何空间中的对象的定位数据[5]。空间数据用于计算机科学的许多领域，如地理信息系统（GIS），机器人，计算机图形学和虚拟现实。操作空间结构的算法被称为空间数据算法（SDA）。1电子邮件：Jussi. tkk.fi2电子邮件：Ari. tkk.fi3电子邮件：Eiri. tkk.fi4电子邮件：Kirsi. tkk.fi5这项工作得到了芬兰科学院的支持，资助号为210947。1571-0661 © 2007 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.01.02990J. Nikander等人理论计算机科学电子笔记178（2007）89空间数据结构基于常规的非空间数据结构，如数组，列表和树结构，以及操作这些基本结构的算法。然而，空间数据结构的复杂性主要来自数据的多维性。高效算法的二维和三维变体使算法开发更具挑战性。在GIS文献中，有一套基本的核心以及先进的空间算法和数据结构。然而，没有关于这一主题的综合教科书。空间数据和操作定位数据的算法是一个不可分割的部分地理信息学是将信息技术应用于制图和地球科学的一个科学分支。地理信息学与制图学密切相关，因此经常使用插图，如地图和其他图表。对于这个研究领域的人来说，图形是一种熟悉和自然的方式来说明工作。软件可视化（SV）是软件工程的一个分支，旨在使用图形和动画来说明软件的不同方面。 它通常分为两个细分：程序可视化和算法可视化[8]。在这两个细分中，重要的是能够在可视化中的各种抽象级别之间进行区分。例如，使用两个数组实现的链表可以通过显示数组及其内容来可视化。这样的可视化显示了列表的实现级别的细节，但是很难掌握它的逻辑结构， list被可视化为通过引用连接的节点。在本文中，我们将集中在SV的算法可视化（AV）方面SV的主要用途之一是在教学中，许多SV系统已被开发用于教学。例如，见[3，6，9]。然而，在教育学中，形象化并没有任何内在价值。正如Hundhausen [4]所指出的，学习者必须积极参与使用算法可视化的活动，以获得更好的学习效果。空间数据算法及其应用的图形性质使SV成为教授它们的自然工具。空间算法处理的数据是多维的，因此输入、输出和求解过程的自然可视化是地图或图表。 如果不使用图形，来解释空间算法或数据结构。 因此，我们目前正在扩展TRAKLA 2可视化系统[6]，以包括SDA。我们专注于地球信息学所需的结构和算法，这是一门将信息技术应用于制图和地球科学的科学。我们不知道任何其他的工作，适用于SV技术的空间数据结构。在本文中，我们将提出一个算法可视化分为不同的抽象层次，并描述这些层次如何可以映射到可视化的数据结构一般。我们将从Price等人[8]的分类法中扩展类别的真实性和完整性，以便更好地了解“自由地提供更简单、更易于理解的视觉解释”的教学系统的各种需求这个想法是命名四个不同的J. Nikander等人理论计算机科学电子笔记178（2007）8991“呈现底层虚拟机器的行为的视觉隐喻”的级别 我们将在SDA的可视化中应用这些抽象层次，教授地理信息学的学生这个课题本文的其余部分组织如下。在第2节中，我们介绍了我们的模型的不同层次的抽象可视化数据结构。 在第三节中，我们讨论了如何将该模型应用于空间数据结构的可视化。最后，第4节讨论了如何在SDA教学中使用不同层次的可视化。2数据结构抽象数据结构（DS）可以定义为变量的集合，可能是几种不同的数据类型，以各种方式连接。 抽象数据类型（ADT）是一组（抽象）项，其中定义了一组操作。逻辑（ADT）世界和物理（DS）世界的单独定义出于许多原因是必不可少的。首先，这些将设计与实现区分开来。 ADT的定义没有指定如何实现数据类型，并且对ADT的最终用户隐藏了实现级别的详细信息。这个藏身之的实现细节称为封装。其次，ADT的概念是通过抽象来管理复杂性的重要原则。 可以安全地忽略不相关的实现细节。 这也是人类处理复杂性的方式。 我们使用隐喻来为概念集合分配标签，然后操纵标签来代替集合。第三，可重用性是软件工程中的关键原则之一，可以通过设计适用于许多任务的通用数据结构来促进，即，通过实现适合于几种算法的数据类型在软件可视化中，我们感兴趣的是说明相关数据项的组织，无论它们是否抽象。根据可视化的目的，相同的数据项可以在几个抽象级别中表示。然而，这种对粒度的需求不仅偏向于这两个极端（DS和ADT）。例如，二进制堆是优先级队列ADT，是作为数组实现的。在这两个抽象级别之间，它有一个众所周知的表示，其中二叉堆可以被可视化为二叉树。在下文中，我们将微调或中的数据类型抽象的概念-为了创建一个模型，让人们更深入地了解数据结构实现的世界和教科书中使用的传统视觉符号。我们主张，为了实现任何数据结构，只需要少量的基本结构。此外，基本结构都有广泛接受的可视化或规范视图。反过来，这些视图可以用来说明使用这些基本结构定义的任何数据结构2.1简单的例子让我们从图1（a）中的示例开始，它显示了在四个不同抽象级别上可视化的有两个示例结构92J. Nikander等人理论计算机科学电子笔记178（2007）89(a) 数据结构可视化中的抽象层次(b) 基本结构的规范观点Fig. 1. 不同的可视化在图中，左边是一个二叉堆，右边是一个红黑树。我们将首先关注二进制堆的可视化二进制堆通常使用数组实现。数组的规范视图显示在图中的最低层。 数组可用于实现一个二进制堆，通过对它施加一组语义：节点i的子节点位于位置2i和2i+1，并且对于每个节点，堆属性“父节点小于或等于子节点”成立。二进制堆的实例显示在图1（a）（数据结构视图）中的第二个最低级别。在这个层次上，堆被可视化为数组，因此可视化准确地反映了数据结构是如何实现的。 然而，在数组可视化中，很难看出堆属性是否成立。当使用二叉树表示（表示视图）显示数据结构时，堆属性更容易看到。最后，二进制堆可以用于例如网络路由器模拟（应用程序视图）。不同的数据包可以有不同的优先级，优先级队列可以抽象成一个黑盒子，里面的结构根本没有显示出来。 数据包从右边进入，转发的数据包从左边出来。如果数据包被丢弃，它们将显示在可视化下方2.2基本结构层次通常，基本结构是用于实现特定数据结构的通用数据类型（骨架）。例如，数组、链表、树和图都是基本结构。这些都是原型，是用于创建结构的可重用基本构建块，并且可以实现教科书中使用的所有数据结构在这些原型方面。例如，邻接表是一个数组和多个链表的组合。基本结构的规范观点被普遍接受和使用，例如，在大多数教科书中。它们是简单且易于识别的可视化，任何熟悉数据结构的人都会立即将其识别为某种类型的结构。规范视图的示例可以在图1（b）中看到。数组的规范视图是一组并排排列的框，每个框J. Nikander等人理论计算机科学电子笔记178（2007）8993保存单个数据项的框。 类似地，列表的规范视图是排成一行的一组节点，其中每个节点都有一个对其后继节点的引用（末尾可能有一个箭头的行）。第一个节点是最左边的节点。（有根）树的规范视图是以自上而下的方式布置到层级的多个节点，其中每个节点具有对其子节点的引用，并且距根节点给定距离的所有节点都在同一层级上。 图的规范视图是一组节点，每个节点都有对其后继节点的引用，通常使用视觉上令人愉悦和易于理解的布局进行排列从可视化的角度来看，基本结构层是我们感兴趣的最低抽象层。该级别包含规范视图，可用于可视化使用基本结构定义的任何数据结构。尽管如此，即使是这些规范的观点也是抽象的。例如，数组是计算机科学中常用的术语，表示内存位置的连续块，其中每个内存位置存储一个固定长度和固定类型的变量。然而，数组也可以引用由变量的（同构）集合组成的结构，每个变量由特定的索引号标识大多数编程语言不直接支持后一种形式 由于它的抽象性，因此，可能有几种不同的阵列实现方式然而，它们背后的低层次抽象对于所有实现都是通用的，并且可以以统一的方式表示。正如我们所看到的，基本结构没有语义。 什么的定义是一个数组，它不规定数据类型，也不规定其中项的顺序。然而，算法的设计和分析需要以这样一种方式组织信息，即计算可以有效地执行。 同样，我们需要以说明实际数据和其他限制，以便提出一个有意义的说明。基本结构背后的基本思想是多次重用它们来表示具有不同语义的多个数据结构。例如，数组可以是哈希表和二进制堆的基本构建块。类似地，在这些基本构建块的可视化中，我们可以为所有使用数组的数据结构提供一个可重用的表示。这使得用少数不同的表示来可视化任何数据结构成为2.3数据结构级在数据结构层，我们有数据结构，这些数据结构是封装特定ADT的概念模型的实现。 这个概念模型定义了用于实现模型的基本结构以及类型约束 这为实施奠定了基础。 对应的数据结构是一种实现，它还定义了改变结构所需的操作。 例如，红黑树是一种具有以下基本结构的数据结构：的二叉树，并实现了一个ADT称为字典（操作搜索，插入和删除）。图1（a）中展示了一个示例树（红色节点用双圆圈表示）。6当然，有几种方法来说明数组，但通常使用的规范视觉符号 都是平等的，这样一个人就可以很容易地从他们每个人掌握数组的想法94J. Nikander等人理论计算机科学电子笔记178（2007）89在数据结构级，数据结构使用根据基本结构定义的规范视图进行可视化。因此，可视化准确地反映了数据结构的实际实现，并显示了结构的所有（相关）部分。在可视化中，我们最感兴趣的是布局以及它是否满足数据结构的约束。例如，红黑树中的旋转概念可以用以下术语表示： 这种布局的变化（即， 移动节点和节点之间的弧）。 当然，我想，实际代码也可以例如被示为伪代码。在数据结构层面，可视化的布局可以在 为了给观察者一个可视化哪种数据结构的视觉提示，或者显示关于结构的不同部分的一些附加信息。 例如，红黑树的节点通常被绘制为红色或黑色。2.4表示等级单个数据结构通常可以用几种方式表示。在我们的定义中，表示层包含的可视化不一定反映实际的实现，但仍然显示存储在结构中的所有数据。例如，二叉堆可以表示为反映其实际实现的数组，或者表示为更好地说明堆。因此，不同的表示形成了一个抽象层次，其中可视化可以被修改以隐藏数据结构的“物理”特征，以便使一些隐式特征显式。我们称这些抽象为表示层可视化。在表示层次上，可以改变用于表示数据结构的视觉方法，以便更清楚地显示结构的期望特征。例如，红黑树可以用来实现B树[2]，因此它也可以被可视化。在图1（a）中，2-3树表示用于表示层上的红黑树。此外，在表示层面上，一些可视化不再符合图1（b）中所示的任何标准视图。然而，应该注意的是，任何数据结构都可以使用规范视图来可视化。然而，有时候，定制的可视化更适合于掌握结构的一些重要方面当存储在结构中的数据是多维的时，替代可视化特别有用。 在规范化视图中，只有一个维度可用于显示数据元素之间的关系：数据键值的可视化。例如，如果元素是二维空间中的点，则观察者很难掌握元素之间的关系。一维可视化中的元素。然而，如果将点绘制到二维平面中，则更方便地查看关系（例如，距离、方向）。J. Nikander等人理论计算机科学电子笔记178（2007）89952.5应用水平抽象的最高层称为应用层。 在数据结构中的信息不完全可见的视觉隐喻被认为是在这个级别上。 这被称为应用程序级，因为几乎所有使用图形的应用程序 为了说明数据，仅示出相关数据项而不是整个数据集。通常，只有那些用于软件可视化的应用程序才能显示所有数据。通常，在这个级别上，我们以特定于域的方式来说明数据，忽略了大部分或所有数据结构的细节。 例如，B树通常用作数据库索引或存储结构，如图1（a）中的数据库符号所示。该视图隐藏了实现的所有细节。因此，在应用程序级别，数据结构可视化类似于一名ADT。接口是定义的，但实现是隐藏的。2.6合并水平软件可视化技术和工具也可以用于许多其他学科。特别是，存在已被证明是特别重要的许多学科的抽象。对这些摘要进行分类的想法是，我们可以反复使用相同的组件和概念 并利用先前的工作。此外，当可视化用于说明一个概念或数据结构时，同时使用同一数据结构上的不同视图的多个可视化通常是有用的。例如，通过显示二叉堆如何演变，同时在数组和二叉树可视化中添加或删除新元素，可以帮助查看者看到堆的逻辑和物理结构如何相互关联某些应用领域本质上是可视的。例如，在GIS应用中，典型的表示是地图。然而，底层的数据结构和它们的视觉对应物基本上是相同的，例如，在软件可视化中。因此，我们需要区分应用程序级可视化和底层数据结构和算法的说明。然而，无论我们想到的是哪种应用程序，都可以通过抽象层次将其简化为那些基本的构建块，我们将在下一节中看到。3空间数据可视化算法空间数据算法处理自然可视化为地图的数据。 在本节中，我们将展示如何将上一节中的模型应用于SDA。具体来说，我们提出了一个常见的地理信息学问题，称为地图覆盖，作为一个例子，并描述了如何使用不同抽象层次上的几个可视化可视化。在应用程序级别，我们通常以某种形式说明数据。 GIS中96J. Nikander等人理论计算机科学电子笔记178（2007）89应用程序源和结果数据集都可以被可视化为某种类型的映射。因此，应用级可视化可以很好地概述问题，特别是当地球科学和制图领域的专家被用来处理和理解地图时。然而，虽然GIS应用程序中的可视化很好地说明了数据，但它们忽略了所使用的数据结构的所有细节将两个不同的地图结合起来生成一个新地图的问题称为地图叠加。 利益往往在于发现某些属性重合的区域。例如，松鼠栖息地区域可以组合到植被层中，以获得一张地图，该地图显示了在针叶林中发现松鼠的区域。将地图叠加描述为两个地图层的组合属于我们概念框架中的最高抽象级别（图1（a））。我们有两张地图，分别展示了赫尔辛基大都市区的四个城市和同一地区的邮政编码区。我们的问题是找出每个邮政编码区属于哪个市，并找到邮政编码区跨越市边界的区域。地图叠加可以为这些问题提供解决方案。图2（a）说明了源映射以及所得到的叠加。为了用计算机解决一个问题，这个问题必须以某种方式形式化地表示出来。通常，使用数学表示来存储地图数据。这种表示还提供了独立于任何计算机化数据结构实现的数据视图。即使数学表示隐藏了数据结构的所有物理细节，它也清楚地显示了数据元素之间的逻辑连接，因此属于表示级别。在地理信息学中，数学表示的例子是Voronoi图及其对偶，三角形不规则网络（TIN）[7]。在GIS中，数据可以使用两种模型表示：矢量模型或栅格模型。在矢量表示中，数据被表示为点、线或多边形对象，这些对象具有与它们相关联的空间位置数据。多边形可用于构造多边形地图，线可用于图形，点集可构造成TIN模型或Voronoi图。TIN和Voronoi图的优点是离散的测量点构成支持例如插值和可视化的结构。栅格模型利用规则网格将所表示的区域划分为大小相等的单元。每个单元格都包含一个表示相应区域值地图叠置问题可以通过应用矢量或栅格模型来解决。 在我们的示例中，我们使用矢量格式的地图覆盖操作。在矢量格式中，要叠加的区域通常表示为多边形。多边形是一组点和连接它们的引用的抽象，数据的多边形地图可视化属于表示层。因此，我们有两个多边形地图，它们通过相交多边形边界而重叠。地图覆盖首先使用某种方法，例如线扫描算法，来定位相交线。然后使用交点来创建新的多边形，这些多边形形成结果地图。图2（a）iv显示了赫尔辛基的详细情况J. Nikander等人理论计算机科学电子笔记178（2007）8997(a)地图叠加问题i）邮政编码区，ii）城市-（b）城市- ipality边界源地图的DCEL结构表示，iii）地图叠加结果，iv）ipality边界市政边界将邮政编码区域划分为两个面图二. DCEL可视化地图叠加将邮政编码划分为两个多边形的边界。图2（a）iii中的矩形突出显示了细节的位置为了在计算机上获得有效的解决方案，需要一个合适的数据结构来存储数学模型。通常，有几种可能的数据结构可用于存储每个模型。模型本身定义了一种抽象的数据类型：它告诉我们如何操作数据以及如何构造数据，但并没有定义如何实现数据结构。因此，用于实现数学模型的数据结构具有良好建立的语义集，因此是封装特定ADT的概念模型。对于地图覆盖，一种可能的数据结构是双连接边列表（DCEL）[1]。DCEL由顶点、多边形面和连接顶点的半边组成。每个顶点都有一个位置，并连接到源自该顶点的边。 每个多边形面在其外边界上具有半边信息和一个包含脸部每个洞的列表。 每条边被分成两个半边。一个半边有它的原始顶点和孪生的信息。目的地是不需要的，因为它是相同的顶点作为双胞胎此外，一个下一个和一个上一个半边连接到每个半边以及入射多边形面。图2（b）显示了简化的市政边界作为DCEL。 左边是一个（部分）结构的可视化，显示为一个图形，右边是一组数组。对于DCEL结构，图形可视化可以被认为是表示级别的可视化，因为它隐藏了数据项之间的许多关系。例如，每个半边都知道它的后继边和前导边，但是这些边通常不会在图形可视化中显式地示出。由于DCEL结构包含空间数据，因此显示其逻辑结构的最佳图形可视化将考虑数据项的坐标。 因此，我们建议，不同的点和半边以其正确的坐标绘制使用DCEL地图覆盖是通过首先将两个地图层的DCEL结构组合成无效的DCEL来解决的。然后检查并修改以形成有效的结构。最后，对DCEL实现的基本结构进行了可视化 在图2（b）的右侧。DCEL包含三种类型的对象：顶点、面98J. Nikander等人理论计算机科学电子笔记178（2007）89和半边。因此，DCEL实现至少需要三个结构来存储数据。构建DCEL的一种自然方法是使用三个包含相应信息的数组。在数据结构级别，用于可视化空间数据结构的基本规范表示与任何其他数据结构的4讨论在本文中，我们已经描述了数据结构可视化如何可以分为四个不同的抽象层次，这些层次如何彼此不同，以及它们如何可以应用于不同类型的数据结构的可视化。特别是，我们已经展示了不同层次的可视化如何应用于空间数据结构和算法。我们的例子，地图覆盖，是从地理信息学领域，作为一个学科，是非常直观的性质。大多数地理信息学问题在描述、求解和求解过程中都涉及到图形视图。对于该领域的人们来说，可视化是处理和表示数据的一种自然且非常常见的方式。因此，可视化也是地理信息学教学的一个非常好的工具，包括SDA。由于空间数据结构包含二维数据，传统的算法可视化技术可能会低于标准。传统上，可视化的重点是显示数据结构的组成。例如，图形可视化以视觉上吸引人的方式显示顶点和边，而树可视化被优化以显示树节点之间的关系。当存储在结构中的数据是一维的（如数字或字符串）时，这也显示了数据元素之间的关系然而，当数据是二维的时，结构的不同部分之间的关系通常不能给出数据项之间关系的全面视图。例如，DCEL通常用于表示地理信息学中的矢量地图。根据所使用的抽象级别和所选择的可视化类型，可以从DCEL中获得的信息有很大的不同。 当作为数组查看时，可视化有助于理解实现的微小细节，但不能很好地概述它所代表的数据。如果以图2（b）中的图形形式查看，则可视化可以很好地查看所表示的数据，但忽略了许多实现级别的细节。为了有效地可视化一些SDA，我们显然需要同时进行多个可视化。一个可视化显示所讨论的数据结构的内部组成，另一个可视化提供所表示的数据的易于理解的视图。这有效地扩展了[8]的多视图类别，该类别衡量可视化可以提供的多个同步视图的程度。分类法讨论了不同粒度的视图。另一方面，我们需要使用不同的图形隐喻来显示数据的视图，从而使逻辑结构的不同方面变得清晰。J. Nikander等人理论计算机科学电子笔记178（2007）8999引用[1] de Berg，M.，M. V. Kreveld，M. Overmars和O. Schwarzkopf，29比33[2] 吉巴斯湖J.和R. Sedgewick，平衡树的二色性框架，在：计算机科学基础第19届年度研讨会论文集，IEEE计算机协会，1978年，pp. 八比二十一[3] 洪德豪森角和S. A. Douglas，SALSA和ALVIS：A language and system for constructing and presentinglow fidelity algorithm visualizations，in：Visual Languages，2000，pp.67比68URLhttp://citeseer.ist.psu.edu/hundhausen00salsa.html[4] 洪德豪森角D、S. A.道格拉斯和J. T. Stasko，算法可视化有效性的元研究，Journal of Visual LanguagesComputing13（2002），pp.259-290。[5] 劳里尼河和D.汤普森，[6] 马 尔 米 湖诉Kar avirta ， A. Korhonen ， J.Ni kander ， O.SeppéaléaanddP.Silvasti ，Visualalgorithmsimulation exercise system with automatic assessment ： TRAKLA2 ， Informatics inEducation 3（2004），pp. 267[7] Okabe，A.，B. Boots，K. Sugihara和S. N.邱，[8] 普 赖斯 湾一 、 R. M.贝 克和 我S. Small ， A Principal Taxonomy of Software Visualization，Journal ofVisual Languages and Computing4（1993），pp.211-266[9] Roßling，G.，M. SchuélerandB. Freisleben，TheANIMALalgorithmanimationto o ol，in：Proceedingsof the5thAnnual SIGCSE/SIGCUEConference on InnovationandTechnology inComputer ScienceEducation，ITiCSE'00（2000），pp. 37比40[10] 斯塔斯科，J.T.，J. B. Domingue，M. H. Brown和B. A. Price，“软件可视化：编程作为一种多媒体体验”，