对于地理相关统计数据而言，以专题地图为代表的表示方法往往按照一定的地图投影法则对地理坐标进行变换，局限于传统地图框架中，使用户在获取知识时需要分析较多无关信息。近年来，随着各类媒体的使用，Cartogram逐步进入了大众视野。其以符合人类认知规律，表达内容直观、明确，自动生成效率高等特点得到快速发展。如文献[1]在TED演讲中向观众介绍了Cartogram这一新颖的表现方式，呈现了一种了解地球的全新视野。Worldmapping项目利用Cartogram表达了各种统计数据，对经济、文化、教育、医疗等方面进行了分析，呼吁社会保护环境、爱护人类的生存空间[2]。另外，在人口趋势分析[3]、自然灾害预测[4]中，Cartogram也已发挥了重要作用。

1、Cartogram与矩形Cartogram

Cartogram是一种以面域面积体现属性值的表达方法。它使用一定的策略对地图进行转换，使区域面积与某个属性值相匹配，从而得到适宜认知的制图表达。如用人口数量代替国家领土面积，可显示各个国家人口在世界范围内所占的比重;用GDP数据代替区域领土面积可反映地区发展水平及其差异;用选举数据代替领土面积可显示选举结果。文献[5]从认知科学的角度分析了Cartogram的作用，认为Cartogram是一种与人类大脑中的心象地图相对应的表示方法，适合区位专题信息的认知表达。作为Cartogram中的重要一类，矩形Cartogram最早可追溯到19世纪80年代，直到1934年文献[6]才第一次给出了矩形Cartogram的正式定义。

研究矩形Cartogram主要有两个原因:一是用规则图形表达地理数据具有实践意义，生活中处处存在的“线性启发式”，使读者易于接受“制式化”的要素表达，对其进行研究是对规则化图形表达方式的尝试;二是矩形Cartogram可应用于不包含地理坐标的数据，如网络数据的隐喻表达，同时也为地理信息数学抽象及表达提供了广阔的舞台。

尽管近年来有许多关于Cartogram的分析与综述[7,8,9]，但针对矩形Cartogram的专门研究较少。鉴于其巨大的应用与研究潜力，本文将系统论述矩形Cartogram的特点与评价标准，总结其生成方法的现状、分类与难点，进而分析其发展趋势。

2、矩形Cartogram的特点与评价标准

2.1矩形Cartogram的特点

矩形Cartogram使用与属性值相匹配的矩形表示地图区域，表示方式新颖独特，特点鲜明。其特点总结如下:

(1)几何形状。矩形Cartogram的外轮廓与各区域均由矩形表示。利用相同形状体现不同实体，消除了地理边界带来的差异，为数据特点的展示提供了空间，有助于差异的识别。但有时为保证正确的拓扑关系，布局内部会出现非矩形的几何图形。

(2)拓扑关系。矩形Cartogram通常通过矩形间的公共边表示邻接关系。两区域间有公共边即表示两者相邻，但由于矩形长宽比及数据值的限制，公共边的长度与原始图中实际相交长度没有必然联系。矩形Cartogram通常会产生拓扑错误，一般在其自动生成过程中通过设置容错率进行控制。

(3)数据处理。矩形Cartogram在表现统计数据时，通常为了保留数据的细节，根据图幅的大小对数据值进行统一缩放。矩形Cartogram只表达单一数据量的差别，但能表达数据中更多的细节。

(4)表示方法。矩形Cartogram通过矩形的面积表达数据量的特征。原始区域简化为矩形后，增加了面积差异的可识别度，提高了数据的分辨率，有利于用户识别更小的数据差异。

(5)构造方式。一般情况下，Cartogram可利用算法中的变形公式对原始图进行变形，但矩形Cartogram表达的图形与原图差异较大，使其不能由原始图变形得到。矩形Cartogram的构建需要提取原图的空间关系及拓扑关系，再通过转变成其他问题进行求解。

2.2矩形Cartogram的评价标准

2.2.1Cartogram的共性评价指标

文献[10]在评价Cartogram的表达效果时指出，评价Cartogram自动生成算法优劣的指标在数据精度、制图精度和拓扑精度3个方面的衡量是一致的。

(1)数据精度:衡量变换后的区域面积表达相关数据准确性的指标。数据精度与制图误差相关，通过计算Cartogram中实际区域面积与期望面积比值可得到相应结果。

(2)地理精度:衡量变换后形状变形程度及其相对位置变化程度的指标。可使用变形后图形与原图形在形状、偏移距离及偏移角度等方面的变化描述。通常使用汉明距离θ[11]度量形状变形、偏移距离BBSD[12]量化相对位置变化、角度误差[13]体现偏移角度。

(3)拓扑精度:衡量Cartogram拓扑关系与原始图拓扑关系相似度的指标。拓扑精度由Cartogram拓扑关系的错误率度量，其中Ec和Em分别代表原始图与Cartogram的拓扑关系集合。

(4)算法复杂度:算法复杂度及其运行效率是评价算法效率的重要指标，但由于不同Cartogram的自动生成算法总体过程不尽相同，有的需要较多的预处理工作，有的需要较多的后期工作，且多数文献中并没有给出具体的算法复杂度和运行时间，导致其评价较为困难。文献[11]使用Cartogram自动生成算法主体部分的运行时间作为评价依据。

2.2.2矩形Cartogram的个性评价指标

文献[11]认为除上述指标外，多边形复杂度与长宽比对矩形Cartogram的评价也较为重要。

(1)多边形复杂度:衡量变换后多边形复杂程度的指标，其对区域可识别性及数据表达效果具有重要影响。完全由矩形组成的Cartogram多边形复杂度为常数，而为保证拓扑关系而引进的非矩形多边形会增加多边形的复杂度。

(2)长宽比:变形后各区域外切矩形长与宽的比值。对矩形Cartogram而言，其外切矩形与自身重叠，其长宽比能体现其形状特点，可作为形状变形的度量指标。过大的长宽比不利于识别与标注，因此在矩形Cartogram的生成过程中，通常会设置各个区域的最大长宽比，以满足区域特征可识别和放置标签的要求。

3、矩形Cartogram自动生成方法

3.1矩形Cartogram自动生成方法现状

尽管矩形Cartogram提出较早，但直到2004年文献[13,14]才分别发表了矩形Cartogram的自动生成算法。随后文献[15]在算法中添加了用于纠正拓扑关系的海洋矩形块，提升了整体可视化效果。文献[16]在线段移动算法的基础上为每个边赋值得到线性方程算法。文献[12]基于同一幅地图有多种矩形布局的事实，使用进化算法在大量布局中搜索拓扑关系正确且制图误差最小的布局，进一步推动了其在理论及应用方面的发展。文献[17]将求解矩形布局的过程描述为整数型混合线性规划模型，并给出具有较好试验结果的解决方案。

为解决数据与拓扑这对难以调和的矛盾，研究人员开始研究直线型Cartogram[18,19]。直线型Cartogram可看作是对矩形Cartogram的一种扩展，其目的是用复杂度尽可能小的直角型多边形得到制图误差为零且拓扑正确的Cartogram。文献[20]研究了可二分图的布局问题，通过固定矩形布局中矩形的角点并对其进行弯曲，可得到制图误差为0且多边形复杂度为8的算法。文献[21]证明复杂度为8的直角多边形可以表示任何平面三角图。文献[22]给出了构造指定面积的Cartogram的线性算法，并通过添加每条边的水平和垂直约束[23]，得到矩形Cartogram。文献[24]使用规则瓦片覆盖地图区域，也克服了拓扑与数据相矛盾的问题，得到区域面积与数据相匹配的马赛克地图。马赛克图的功能是用规则图形对地图作除法，简化了边界，放大了细节，可以看作是矩形Cartogram简化思想的延伸。文献[25]在Heilmann算法的基础上进行改进并将其应用于社交网络的分析。文献[26]根据矩形易于分割的特性，将矩形布局与TreeMap相结合，表达具有二维空间属性的层级信息。文献[27]提出用多级矩形Cartogram表达具有层级属性的社会经济学数据。

3.2矩形Cartogram自动生成的主要方法

3.2.1矩形Cartogram构造方法分类及对比

矩形Cartogram的构造方法主要分为两类，一类是基于矩形对偶图的构造算法[14,16]，另一类是启发式构造算法[13]。基于矩形对偶图的Cartogram生成算法实质上是对矩形对偶图进行变换，使各矩形的面积与期望值相一致。其优点是利用矩形对偶图完成了部分工作，但矩形对偶图的生成增加了预处理工作，使总步骤较为烦琐，对图论知识要求较高。

启发式的构造算法则直接利用原始图提供的地理信息，根据矩形Cartogram的特点设置约束函数，再利用约束函数启发式地完成矩形Cartogram的构造。该方法的优点是理论简单、步骤较少，但由于约束函数只能提供部分拓扑及位置信息，对原始图信息利用不充分，导致成果拓扑错误较多。

3.2.2基于矩形对偶图的矩形Cartogram构造方法

基于矩形对偶图的构建方法通常分为准备阶段与变形阶段两个部分。准备阶段利用平面布局知识由原始数据生成拓扑关系及位置关系正确的矩形对偶图;变形阶段则对矩形对偶图进行调整，使各矩形面积与期望值一致，是自动构造算法的主要阶段。

3.2.2.1矩形对偶图概念及构造方法

平面图G=(V,E)的矩形对偶图[28]是满足对象映射与关系映射的矩形分割系统。满足以下定理的平面图(也称为三角化图(PTP))才具有矩形对偶图[29]。

定理1:平面图G具有外轮廓为矩形的矩形对偶图的充要条件为:(1)每个内面都是三角形[30]且外边为四边形;(2)平面图G中没有分割三角形。

利用正则边标号REL(regularedgelabeling)构造矩形对偶图的线性算法[31]思路简单，内部关系明确，且对偶图的坐标均为整数。其过程主要分为两步:(1)构造G的REL;(2)利用REL构造对偶图。图1简要说明了地图、平面图、REL及矩形对偶图之间的关系。

图1一个细分及其增广对偶图G,G的一个正则边标号及其对应的矩形对偶图[32]

PTP的REL并不唯一，文献[32]证明REL的选择可改进矩形Cartogram的表达，并给出了选择方案，在此基础之上利用遗传算法可提高计算效率[12]。文献[33]证明图G的所有REL组成一个晶格分布，利用反向搜索枚举所有REL，并利用退火算法可在指数量级的REL中找到使制图精度最优或接近最优的REL。

3.2.2.2基于矩形对偶图构造矩形Cartogram的主要算法

(1)L-型布局算法。文献[14]首次提出构建矩形Cartogram的L-型布局算法。笔者通过完全分析法证明按规定顺序去除矩形块后，剩余的L-型多边形的每条边总是与首个矩形的边长存在单调关系，因此可根据当前矩形目标函数的变化调整初始矩形的边长。通过该方法可避免求解高次方程而得到准确值或最优解。该算法存在的问题是应用对象局限性较强，且变换过程中以分组单元为整体进行变换，不能保证分组内部小区域接边的正确性。

(2)线段移动算法。文献[14]还提出了线段移动算法。矩形Cartogram中的最大线段是指多个矩形的公共边，该算法通过移动水平最大线段与垂直最大线段，使相关矩形的面积产生相应变化，可得到目标函数的一个极值，但在有限次运算下不一定能够得到最优解。其优点是可用于任何矩形布局，且迭代速度较快。

(3)线性方程解法。文献[16]提出的线性方程解法是一种解析法，其思路为:对于给定的矩形布局，其划分可由布局内部最大线段的坐标决定，其中任一矩形的位置及形状可由相邻的4条最大线段决定。在求解双线性约束方程时，依次将x轴或y轴变量视为常量，得到关于x轴或y的线性方程，将解逐次代入线性方程，经数次迭代可得到方程的最优解。该算法思路清晰，可操作性强，但当区域数量较多时，运算量较大。

3.2.3启发式的矩形Cartogram构造方法

文献[13]提出在原图基础上生成矩形Cartogram的启发式构造方法。笔者根据区域可识别性及数据正确性两点要求设计了5个度量方程。5个度量指标的线性组合形成的度量方程可在Cartogram生成过程中控制矩形位置等属性。各度量的权值可以影响度量方程，从而产生不同的构造方式，得到满足不同需求的矩形Cartogram。其具体实现有分割法与生成法两种形式，这两种方法可理解为自上而下的分割方法和自下而上的生成方法。

分割法是在制图平面上逐次分割包含多个重心的矩形，直到每个矩形只包含一个重心，从而得到满布的矩形Cartogram。其缺点在于分割采用的是二分法，分割产生的矩形难以辨认，且邻接关系正确性较差。

生成法是从中心向四周逐步生成小矩形块的过程。首先根据其拓扑关系生成最大生成树，其根节点为第1个矩形的生成节点，然后以相关系数从高到低的顺序依次生成矩形。相关系数是拓扑图中各顶点的度，反映了各矩形的重要程度。图2(a)、(b)分别为利用分割法与生成法得到的矩形Cartogram，其中灰色或黑色表示候选人赢得本区域选票，图幅中总面积大者为竞赛的获胜方。

3.3矩形Cartogram自动生成难点

矩形Cartogram自动生成的难点与其本身的特点息息相关:

(1)对地理信息的提取与利用较为困难。矩形Cartogram的生成需要有效地提取地理数据中所包含的空间信息及拓扑信息，并根据矩形的特点加以利用，而完全提取地图数据的信息并有效利用较为困难。

图22000年美国总统竞选可视化结果[13]

(2)使用矩形表示原图的拓扑关系较为困难。矩形具有4条边，处于布局内部的矩形需要至少4个相邻的矩形才能保证正确的拓扑关系。而现实中区域间的拓扑关系并无边界限制，因而在矩形布局中维持正确的拓扑关系非常困难。

(3)保持相对位置正确较为困难。原始区域变成矩形之后，其边界要抽象成垂直、水平直线，使其不能按照原图组合在一起。同时，矩形面积会根据属性值急剧扩张或缩小，从而导致相对位置的改变。

(4)准确表达专题数据较为困难。地理位置准确、拓扑关系正确且制图误差为0的完美矩形Cartogram是不存在的。有的Cartogram牺牲制图误差保证正确的拓扑关系，有的确保长宽比与原图一致而忽略制图误差与拓扑关系的正确性。

4、总结与展望

本文简要介绍了矩形Cartogram的研究背景、发展现状及其潜在价值，对矩形Cartogram的典型自动构建算法进行了梳理总结，并对其特点、自动构建难点及评价标准进行了分析。综上，矩形Cartogram在自动构建上已经取得了一定成果，但在自动化程度和可视化效果上仍存在问题与挑战。首先，基于矩形对偶图的算法没有将矩形对偶图的生成融入矩形Cartogram自动构建的算法中，增加了大量人为操作的预处理工作，不能实现由数据到矩形Cartogram的全自动过程。启发式构造算法在目标函数的选择上具有较大自由度，但针对不同特点的矩形Cartogram需要单独设计构建过程，使用户只能在有限的空间内进行选择。其次，纯矩形Cartogram的构建是否为NP困难问题仍没有确定的答案，对于任意地图能否在多项式时间内生成最佳矩形Cartogram仍属未知。

参考文献:

[3]赵正旭,任利敬.基于Cartogram可视化的信息传承方法研究[J].中国人口资源与环境,2016,26(5):526-529.

[5]艾廷华.适宜空间认知结果表达的地图形式[J].遥感学报,2008,12(2):347-354.

[7]王丽娜,江南,李响,等.Cartogram表示方法研究综述[J].计算机辅助设计与图形学学报,2017,29(3):393-405.

王维明,贾奋励.矩形Cartogram自动构建方法探究[J].测绘通报,2020(06):99-103+117.

基金:国家自然科学基金(41671407);国家重点研发计划(2017YFB0503500).