A New Construction Method for Rectangular Cartograms

Abstract

The rectangular cartogram is a geospatial visualization method that blends the characteristics of maps and charts. By simplifying geographic regions into rectangles and using the area of each rectangle to represent statistical data, it enables efficient geovisualization. This paper summarizes and analyzes the advantages and limitations of two main approaches used in current rectangular cartogram construction algorithms. To address the issues of high computational cost and inadequate preservation of adjacency and relative positional relationships in existing algorithms, we propose and implement a new rectangular cartogram construction algorithm. This algorithm simplifies the layout computation process while ensuring that the adjacency and relative positional relationships between regions during the layout generation process have only minor errors. In adjusting rectangle areas to match attribute values, the algorithm adopts a “region-by-region placement” strategy, ensuring that errors in area accuracy remain within a small range, while also keeping errors in adjacency and relative positional relationships minimal. Finally, by comparing the results of our algorithm with those of existing algorithms using real-world data with varying distribution characteristics, we demonstrate its effectiveness. The results show that the proposed algorithm not only improves computational efficiency but also effectively displays the adjacency and relative positional relationships between regions.

1. Introduction

Traditional geovisualization methods typically use lightness, symbol size, texture, and other visual variables to represent quantitative information [1]. However, this approach struggles to effectively highlight areas that are geographically small but have large statistical values, leading to an asymmetry between the distribution of statistical data and the size of geographic regions [2]. To address this issue, cartograms adopt an attribute-data-centric perspective, achieving proportionality between statistical values and area by distorting geographic regions while striving to preserve relative spatial relationships. This creates a visualization framework that represents the attribute characteristics of spatial objects based on the regional area [3,4]. This method compensates for the limitations of traditional approaches and can complement them, offering a more comprehensive and accurate understanding of spatial data distribution characteristics.

The core idea of the cartogram, which “simplifies and distorts geographical objects to emphasize certain attributes”, can be traced back to the Tabula Peutingeriana of 1598 [5]. However, it was not until 1934, when Raisz formally introduced the rectangular cartogram; that cartogram received a clear explanation and definition [6,7]. This method, which effectively integrates the characteristics of maps and charts, is particularly well suited for conveying thematic information about regions, offering highly efficient information transmission [8,9]. Consequently, it has gradually garnered attention from scholars in cartography, computational graphics, and related disciplines. The advancement of automatic generation algorithms has further facilitated the widespread adoption of cartograms [10]. Today, this innovative geovisualization technique has proven invaluable in diverse applications, including population trend analysis [11], natural disaster prediction [12], social network analysis [13], urban traffic management [14], and epidemic analysis [15], among others.

Cartograms can be categorized based on their graphical features into linear cartograms and area cartograms [2]. Area cartograms are further subdivided into four types: simple contiguous [6,7], simple non-contiguous [16,17], complex contiguous [18], and complex non-contiguous cartograms [19]. The rectangular cartogram is a typical example of a simple contiguous area cartogram. In this type of cartogram, rectangles represent geographic regions, with the area of each rectangle proportional to the associated statistical data, while preserving relatively accurate adjacency relationships between regions [20].

Rectangular cartograms offer several advantages. Firstly, the rectangular shape is simple and facilitates the estimation and comparison of area sizes, making the rectangular cartogram particularly effective and accurate in tasks such as comparison, identifying extremes, and estimating data [21]. Additionally, the rectangular cartogram adjusts the areas of regions to reflect the magnitude of attribute values, effectively visualizing the spatial distribution of data and avoiding visual errors caused by mismatches between spatial structure and data [22]. As a result, they have gained widespread application. Moreover, the ease of partitioning rectangles makes them well suited for integration with TreeMap, a hierarchical data visualization technique, effectively representing the spatial distribution of multi-level data [23,24,25,26,27].

Rectangular cartograms are widely used in various applications, prompting researchers to develop automated generation methods to improve their efficiency and accuracy. However, despite these advancements, the automatic generation of cartograms remains a formidable challenge. This difficulty arises from the fact that the construction of rectangular cartograms is a complex combinatorial optimization problem, characterized by a highly intricate optimization model.

The optimization model encompasses several critical constraints:

(1)

Rectangular Simplification: Each geographic region must be simplified into a rectangular shape, without overlap.

(2)

Area Proportionality: The area of each rectangle must accurately reflect the attribute value (e.g., population) of the corresponding region.

(3)

Adjacency Preservation: The original adjacency relationships between regions must be preserved after the transformation.

(4)

Relative Spatial Orientation Preservation: The relative spatial orientation of regions must be maintained to reflect accurate spatial relationships.

The optimization objectives associated with this problem are threefold:

(1)

Maximizing Area Accuracy: Ensuring that the areas of the rectangles are as accurate as possible in representing the underlying attribute data.

(2)

Minimizing Spatial Orientation Distortion: Reducing distortions in the relative spatial orientation of regions to maintain geographical similarity to the original map.

(3)

Minimizing Adjacency Errors: Ensuring that adjacency relationships between regions are preserved as accurately as possible to maintain the recognizability of each region.

In practice, these optimization objectives frequently conflict. Enhancing area accuracy to ensure that rectangle sizes faithfully represent underlying attribute data can disrupt spatial orientation and adjacency relationships. Consequently, efforts to minimize spatial orientation distortion and adjacency errors to preserve the recognizability of regions may necessitate trade-offs in area accuracy. Balancing these competing objectives is a central challenge in the optimization process. Additionally, to ensure that regions remain recognizable, it is essential to consider the aspect ratios of the rectangles, aiming to closely approximate those of the original regions [13].

Based on existing research, automated methods for the construction of rectangular cartograms can be broadly classified into two principal approaches:

(1)

Rectangular Segmentation and Cartogram Method (RSC Method)

The RSC Method involves two key steps:

(1)

Rectangular Segmentation: Simplify the shapes of regions into rectangles while preserving their spatial orientation and adjacency. This generates a rectangular segmentation map.

(2)

Cartogram Generation: Adjust the area of each rectangle to match the statistical data for each region, producing the final rectangular cartogram.

In the study of rectangular segmentation maps, the method proposed by Kant and He (1997) laid the foundation for generating rectangular layouts [28]. Subsequent algorithms have built upon this foundation to generate rectangular cartograms. Kreveld and Speckmann’s research team proposed three algorithmic approaches based on Kant and He’s method for generating rectangular cartograms [29]: Segment Moving Heuristic, Linear Programming, and L-sequence Algorithm.

References [29,30] provide a detailed discussion of the Segment Moving Heuristic, which iteratively adjusts the horizontal and vertical boundaries of rectangles to optimize their areas while balancing the adjustment of areas with the preservation of adjacency relationships. References [31,32] introduce linear programming-based algorithms, where the core idea is to alternately optimize the dimensions of rectangles in the horizontal and vertical directions. These algorithms use linear programming to minimize the area error of each rectangle, aiming to ensure that each rectangle’s area closely matches the target value while maintaining adjacency relationships and geometric constraints.

A key challenge in applying these algorithms is determining the adjacency relationships between regions before using Kant and He’s method to generate the rectangular segmentation map. This process is complex due to the potentially vast number of adjacency combinations. Theoretically, the adjacency relationship between any two regions (e.g., east, west, north, and south) can have multiple possibilities (typically two, though sometimes only one). For instance, the adjacency relationship between Italy and France could be represented as Italy being to the north or east of France, known as layout options. If there are m layout options for all regions, there could be up to 2^m possible adjacency combinations. Therefore, to obtain the optimal rectangular cartogram result, each possible layout combination must be computed. Given the large number of combinations, this computation can be extremely complex and time-consuming. To address this issue, reference [31] proposes reducing the number of layout combinations by partitioning the regions into independent groups (e.g., treating Europe as a single entity), which significantly reduces computation time, although it may lead to some errors. Reference [32] further accelerates the determination of rectangular layouts by employing Evolution Strategies, improving the efficiency of the process.

(2)

Direct Rectangular Cartogram Method (DRC Method)

The DRC Method generates a rectangular cartogram by directly utilizing the positional and adjacency relationships of regions from the original map, along with attribute values, according to a predefined objective function. A representative algorithm is the RecMap algorithm [33,34], proposed by Heilmann et al. The RecMap construction algorithm first establishes an objective function based on the expressive characteristics of the rectangular cartogram, which comprehensively considers area accuracy, adjacency preservation, and relative orientation accuracy. Then, the algorithm utilizes the geographic locations and adjacency relationships from the original map, combining this information with statistical attribute data to gradually determine the position of each region in the rectangular cartogram through the objective function. In this way, the RecMap algorithm can generate an area-accurate rectangular cartogram; however, due to its primary focus on area accuracy, the positional accuracy may not be fully guaranteed.

In summary, the characteristics of the two methods are as follows:

(1)

The RSC method effectively preserves the relative positions and adjacency relationships of regions, resulting in accurate geographical layouts. However, this method is complex and cumbersome, with high computational demands and long processing times, particularly when determining the optimal solution from a large number of possible layouts. Additionally, there are currently no public implementations of these algorithms, making it difficult to reproduce and verify their effectiveness.

(2)

In contrast, the DRC method is theoretically simpler, involves fewer steps, and has publicly available algorithm code [35], facilitating direct application and verification. Although ensuring accurate area precision, the DRC method does not fully utilize the geographic information from the original map, resulting in errors in adjacency and orientation relationships.

A key factor in the construction of cartograms is maintaining the spatial relationships between regions, as this enables users to better recognize connections and enhance their understanding of spatial information. This, in turn, improves decision-making ability. Due to the influence of perceptual constancy, humans find it difficult to accurately perceive differences in area visually [1]. Therefore, a trade-off is acceptable in rectangular cartograms: a slight loss in area accuracy can be tolerated to minimize errors in spatial relationships and adjacency. Achieving this balance is critical for effectively conveying geographical information.

To address these challenges and achieve this balance, we have adopted key aspects of the RSC method. First, we simplified the process of generating rectangular segmentation maps, which made the algorithm more feasible to implement without compromising its effectiveness. Next, we incorporated the concept of sequentially determining region positions from the RecMap algorithm and introduced a novel method for constructing rectangular cartograms, which we call “Adjacency Alignment”. This approach not only preserves critical adjacency relationships but also improves the practicality and efficiency of the cartogram generation process. Finally, real statistical data are used to compare the performance of the proposed algorithm with previous algorithms. Experimental results demonstrate that the proposed algorithm delivers high-quality visualization while minimizing area and topological errors and ensuring efficient computation time. Therefore, the algorithm presented in this paper can efficiently process data while ensuring accuracy.

2. Algorithm Overview

2.1. Basic Definitions

The basic concepts and definitions involved in the algorithms of this paper are provided first to ensure clarity and precision in the exposition.

Definition 1.

Unit: In the construction process of the rectangular cartogram, the minimum units that are transformed among the three forms—original map, rectangular segmentation map, and rectangular cartogram—are collectively referred to as “units”. However, since it is necessary to differentiate the various states of these units during the algorithm implementation, they are specifically designated as the map unit, the rectangular segmentation unit, and the cartogram unit, as shown in Figure 1.

Definition 2.

Length and width: We define the length of the horizontal side of a rectangular unit as its “length”, and the length of the vertical side as its “width”.

Definition 3.

Edge: The four edges of the rectangular unit are referred to as the top edge, bottom edge, left edge, and right edge, respectively.

2.2. Algorithm Workflow

The entire algorithmic process consists of three steps, as shown in Figure 2.

Step 1: Perform basic data preprocessing of the original map.

Step 2: Generate the rectangular segmentation map from the original map.

Step 3: Create the corresponding rectangular cartogram based on the rectangular segmentation map and statistical data.

3. Data Preprocessing

Data preprocessing lays the foundation for the subsequent construction of the rectangular cartogram, consisting of three main parts.

(1) Angle Correction: First, use the “Minimum Bounding Geometry” tool in ArcGIS to obtain the minimum bounding rectangle of the original map. If this rectangle is tilted, the original map needs to be rotated so that its bottom edge stays horizontal, as shown in Figure 3. This correction step not only preserves the correct relative orientation of map units for subsequent cartogram mapping but also enhances visualization, reduces distortion, and allows users to interpret the data more intuitively.

(2) Geometric Center Extraction: Extract the geometric centers of each map unit from the original map. These centers facilitate the calculation of the relative orientation among the various map units.

(3) Adjacency Matrix Construction: Construct the spatial adjacency matrix based on the adjacency relationships among map units.

4. Generation of Rectangular Segmentation Map

4.1. Calculation of Relative Positional Relationships of Rectangular Segmentation Units

In the construction of the rectangular segmentation map, calculating the relative positional relationships between its units is crucial. In the algorithm presented in this paper, the relative positional relationships of the units are specifically defined as the four cardinal directions: east, south, west, and north. This is because both the rectangular segmentation and cartogram units constructed in this paper are rectangular. Since rectangles have four clearly defined edges, restricting the positional relationships to these four directions simplifies the rectangular cartogram construction process.

The relative position between map units is determined by calculating the angle between the line connecting their geometric centers and the horizontal axis, as shown in Figure 4. Consider two map units, A and B, with geometric center coordinates (x_A, y_A) and (x_B, y_B), respectively. The angle between the line connecting the geometric centers and the horizontal axis is denoted as α. The calculation formula is given by Equation (1):

$$\alpha =\left({\mathit{tan}}^{-1}\left((y_B-y_A)/(x_B-x_A)\right)\ast 180\right)/\pi$$

(1)

If 45° ≤ α < 135°, then region B is north of region A.

If 135° ≤ α < 225°, then region B is west of region A.

If 225° ≤ α < 315°, then region B is south of region A.

If 315° ≤ α < 360° or 0° ≤ α < 45°, then region B is east of region A.

4.2. Calculation of Initial Length and Width of Rectangular Segmentation Units

The initial length and width of the rectangular segmentation units are determined by the number of adjacent units. Specifically, the initial length of a rectangular segmentation unit is determined by the largest number of neighboring units on either the northern or southern side, while the initial width is determined by the largest number of neighboring units on either the western or eastern side.

Let the set of rectangular segmentation units be M = {m₁, m₂, …, m_n}. For a rectangular segmentation unit $m_i$, let its length be $l_i$, width be $w_i$, the number of southern adjacent units be $n_i^S$, the number of northern adjacent units be $n_i^N$, the number of eastern adjacent units be $n_i^E$, and the number of western adjacent units be $n_i^W$. The formulas for calculating the initial length and width of the rectangular segmentation unit $m_i$ are shown in Formulas (2) and (3):

$$l_i=\left\{\begin{array}{c}Max\left(n_i^S,n_i^N\right) Max\left(n_i^S,n_i^N\right)>0\\ 1 Max\left(n_i^S,n_i^N\right)=0\end{array}\right.$$

(2)

$$w_i=\left\{\begin{array}{c}Max\left(n_i^E,n_i^W\right) Max\left(n_i^E,n_i^W\right)>0\\ 1 Max\left(n_i^E,n_i^W\right)=0\end{array}\right.$$

(3)

Based on the above calculations, taking the original image in Figure 1a as an example, the initial length and width of each rectangular segmentation unit can be obtained, as detailed in

Table 1. The initial length and width of the rectangular segmentation units.

Unit	Initial Length	Initial Width
A	2	1
B	1	2
C	2	1
D	1	1
E	2	1
F	2	1

.

4.3. Dynamic Adjustment of Length and Width of Rectangular Segmentation Units

4.3.1. Adjustment Order of Weighted Breadth-First Search

After determining the initial length and width of the rectangular segmentation units, the next step is to specify the order in which their length and width will be adjusted. The algorithm in this paper maps the original map to an undirected weighted graph G = (V, E, D) and then uses breadth-first search to determine the adjustment order. In graph G, the vertex set V contains the geometric centroids of each map unit. The edge set E includes all edges connecting pairs of vertices, representing adjacency between the corresponding map units. The weight set D consists of weights assigned to each edge, where the weight of each edge is calculated based on the Euclidean distance between its two endpoint vertices, which represent the geometric centroids of the corresponding map units.

Set the map unit that has no adjacent units to the south and west as the starting unit, and designate its corresponding vertex in graph G as the starting vertex. Next, perform a breadth-first traversal of the vertices in graph G. During the traversal, if a vertex is adjacent to multiple vertices, visit the adjacent vertices in order of increasing edge weights. The order of the breadth-first traversal determines the sequence in which the length and width of the units in the rectangular segmentation map are dynamically adjusted in subsequent steps. Figure 5 presents a specific example, using the EF edge as a reference. Assuming the Euclidean distance between the two points of EF is 1, the weight of the EF edge is 1.

4.3.2. Strategy for Dynamic Adjustment

The length and width of the rectangular segmentation units are determined by the side lengths and quantities of adjacent units. During construction, the edge lengths of the units are dynamically adjusted according to changes in adjacent units. This process continues until the rectangular segmentation map is complete, at which point the final edge lengths are established.

In the process of dynamically adjusting the length and width of the rectangular segmentation unit $m_i$, there are two distinct scenarios for calculating the length and width, depending on the adjacency and orientation relationships between the units:

(1) Case 1: When calculating the length of unit $m_i$, its length is determined by its southern adjacent units. Let ${S(m}_i)$ denote the set of southern adjacent units of unit $m_i$. If unit $m_i$ has no adjacent units to the south, its length remains unchanged. If unit $m_i$ has southern adjacent units, its length is determined by the lengths of these southern adjacent units and the number of northern adjacent units of these southern adjacent units. The specific calculation formula is shown in Formula (4):

$$l_i^{\prime }=\left\{\begin{array}{cc}{l}_i,\hfill & {S(m}_i)=\varnothing \hfill \\ \sum \left(l_j/n_j^N\right),& m_j\in {S(m}_i)\hfill \end{array}\right.$$

(4)

(2) Case 2: When calculating the width of unit $m_i$, its width is determined by its western adjacent units. Let ${W(m}_i)$ denote the set of western adjacent units of unit $m_i$. If unit $m_i$ has no western adjacent units, its width remains unchanged. If unit $m_i$ has western adjacent units, its width is determined by the widths of these western adjacent units and the number of eastern adjacent units of these western adjacent units. As shown in Formula (5):

$$w_i^{\prime }=\left\{\begin{array}{cc}{w}_i,\hfill & {W(m}_i)=\varnothing \hfill \\ \sum \left(w_j/n_j^E\right),\hfill & m_j\in {W(m}_i)\hfill \end{array}\right.$$

(5)

To ensure that the length and width of the rectangular segmentation units are integer multiples of the designated unit length, when calculating the length of unit $m_i$, if there exists a situation where $l_j/n_j^N$ is not an integer, the length and width of all rectangular segmentation units will be multiplied by $n_j^N$. Similarly, when calculating the width of unit $m_i$, if there exists a situation where $w_j/n_j^E$ is not an integer, the length and width of all rectangular segmentation units will be multiplied by $n_j^E$.

4.4. Algorithm Demonstration

After determining the positional relationships and initial dimensions of each rectangular segmentation unit, the length and width of the units are dynamically adjusted in a loop based on the breadth-first traversal order of the rectangular segmentation units, until the dimensions of all units no longer change, marking the end of the dynamic adjustment process. The specific process is shown in Figure 6, where units A–F correspond to units $m_1$, $m_2$, $m_3$, $m_4$, $m_5$ and $m_6$, and the units currently undergoing edge length adjustment are marked in red. The example in Figure 6 uses the initial length and width provided in Table 1 and gradually adjusts the edge lengths of the rectangular segmentation units according to the traversal order in Figure 5.

5. Generation of Rectangular Cartogram

5.1. Expected Area Calculation of Cartogram Units

The expected area represents the area that each cartogram unit should occupy, proportional to its attribute value, reflecting the relative magnitudes of attribute values across the units. When calculating the position of the cartogram units, their final positions need to be determined based on the expected area. Therefore, determining the expected area of the cartogram units is a prerequisite for calculating their positions.

Let $C=\{c_1,{ c}_2,\dots ,c_n\}$, represent the set of cartogram units, where each unit $c_i$ has an area $a_i$ in the rectangular segmentation map, n is the number of cartogram units, and the total area of the rectangular cartogram is denoted as A. The calculation method for A is given by Formula (6):

$$A=\sum _{i=1}^n{a}_i$$

(6)

Let the statistical value of unit $c_i$ be $v_i$, and the total statistical value of all cartogram units be V. The calculation method for V is given by Formula (7):

$$V=\sum _{i=1}^n{v}_i$$

(7)

Let the expected area of unit $c_i$ be $a_i^{\prime }$. The expected area of each cartogram unit should be proportional to its attribute value, with the calculation formula given by Formula (8):

$$a_i^{\prime }=A(v_i/V)$$

(8)

5.2. Position Determination Strategies for Cartogram Units

This section explains how to calculate the positions of cartogram units. Specifically, the construction algorithm proposed in this paper places each unit from the rectangular segmentation map into the rectangular cartogram one by one, and determines their positions by utilizing the adjacency relationships, positional relationships, and expected areas of the units. Once a unit’s position is established, it remains fixed. Therefore, in this paper, the units that have previously determined positions in the rectangular cartogram are referred to as “determined units”, while the units with yet-to-be-determined positions are referred to as “undetermined units”.

In a rectangular segmentation map, when two rectangles are adjacent, three cases may occur: (1) The two rectangles share two common vertices and have one overlapping edge. (2) The two rectangles share one common vertex and have one overlapping edge. (3) The two rectangles only have one overlapping edge. In the rectangular cartogram, the relative positional relationships between adjacent units are maintained as much as possible. If two adjacent units in the rectangular segmentation map share a common vertex, this positional relationship will also be preserved in the rectangular cartogram. Consequently, it is possible to derive some vertex coordinates of the undetermined units through the common vertices or overlapping edges of the determined and undetermined units. Additionally, by incorporating the expected area of the units, the remaining vertex coordinates can be calculated, thus determining the positions of the undetermined units.

Based on the three possible adjacency scenarios between neighboring determined and undetermined units in the rectangular segmentation map, we propose corresponding methods to calculate the positions of the undetermined units. In Figure 7, Figure 8 and Figure 9, determined units are marked in blue, while undetermined units are marked in orange. The orange area may represent a single undetermined unit or a combination of multiple units arranged together. For simplification, we treat the orange area as a single “whole unit” to determine its overall position. If the orange area consists of multiple units, their centroids must align along the same horizontal or vertical line and form a complete rectangle. After calculating the overall position of the orange area, we further subdivide it based on the expected area and the relative positions of the individual units, thus determining the specific positions of each unit within the rectangular cartogram.

(1) 

Case 1

In the rectangular segmentation map, the orange area and the blue area share only one coincident edge. Figure 7a illustrates the adjacency between unit A (hereinafter referred to as A) and unit B (hereinafter referred to as B) in the rectangular segmentation map, where the position of A is determined, and the position of B is to be determined based on its expected area and positional relationship. Figure 7b shows the positions and adjacency relationship of A and B in the rectangular cartogram. In the figure, $x_i$ and $x_i^{\prime }$ represent the horizontal coordinates of the vertical line segment, and $y_i$ and $y_i^{\prime }$ represent the vertical coordinates of the horizontal line segment.

To maintain the relative positional relationship between adjacent A and B, without affecting the determination of other units’ positions, the following principles are followed when determining the position of B:

(1)

A and B remain adjacent and share a coincident edge.

(2)

The center point of the coincident edge between A and B must maintain its relative position on the right edge of A.

(3)

The relative position of the centroids of A and B are maintained.

Based on these three conditions, the position of B can be uniquely determined. The calculation steps are as follows:

➀ Calculating the expected range of the coincident edge. To avoid affecting the determination of other units’ positions, the two endpoints of the coincident edge must be restricted within the expected range. Based on the width variation ratio of A, and the distance between the top edge of A and the top edge of B, as well as the distance between the bottom edge of A and the bottom edge of B, we can calculate the maximum value $s_1$ for the top edge and the minimum value $s_2$ for the bottom edge of B in the rectangular cartogram. The specific calculation formula is shown in Formula (9):

$$\left\{\begin{array}{c}{s}_1=y_1^{\prime }-{\displaystyle \frac{\left(y_1-y_3\right)\left(y_1^{\prime }-y_2^{\prime }\right)}{\left(y_1-y_2\right)}}\\ s_2=y_2^{\prime }+{\displaystyle \frac{\left(y_4-y_2\right)\left(y_1^{\prime }-y_2^{\prime }\right)}{\left(y_1-y_2\right)}}\end{array}\right.$$

(9)

➁ Calculating the position of the coincident edge. Since the position of A is already determined in Figure 7b, the midpoint of the coincident edge can be determined as ($x_2^{\prime },{\displaystyle \frac{s_1+s_2}{2}}$).

The expected area of unit B is denoted as area(B). When calculating the position of B in the rectangular cartogram, the angle θ between the centroids of A and B should remain consistent with that in the rectangular segmentation map. Based on this constraint, and considering area(B) along with the midpoint of the coincident edge ($x_2^{\prime },{\displaystyle \frac{s_1+s_2}{2}}$), the values of $y_3^{\prime }$ and $y_4^{\prime }$ for B can be calculated. The specific calculation formula is shown in Formula (10):

$$\left\{\begin{array}{c}\mathit{tan}\theta ={\displaystyle \frac{s_1+s_2-y_1^{\prime }-y_2^{\prime }}{x_3^{\prime }-x_1^{\prime }}} \\ area\left(B\right)=\left(x_3^{\prime }-x_2^{\prime }\right)\left(y_3^{\prime }-y_4^{\prime }\right)\\ s_1+s_2=y_3^{\prime }+y_4^{\prime } \end{array}\right.$$

(10)

➂ Determining whether the coincident edge is within the expected range. If the vertices fall outside this range, the top or bottom vertex should be set directly to $s_1$ or $s_2$.

If $y_3^{\prime }>s_1$, then set $y_3^{\prime }=s_1$;

If $y_4^{\prime }<s_2$, then set $y_4^{\prime }=s_2$.

➃ Determining the position of B. Based on the expected area and the determined $y_3^{\prime }$ and $y_4^{\prime }$, the corresponding $x_3^{\prime }$ can be calculated using Formula (11). This allows for the determination of the position of B in the rectangular cartogram.

$$x_3^{\prime }=x_2^{\prime }+{\displaystyle \frac{area\left(B\right)}{(y_3^{\prime }-y_4^{\prime })}}$$

(11)

(2) 

Case 2

In the rectangular segmentation map, the orange and blue areas share a common vertex and a coincident edge. Figure 8 shows the adjacency layout in Case 2 and the positioning determination in the rectangular cartogram.

The calculations for the position of B follow these principles:

(1)

A and B still maintain an adjacency relationship and have a coincident edge.

(2)

This common point is a vertex of unit B.

(3)

The relative positions of the centroids of A and B remain unchanged.

Based on these three conditions, the position of B can be uniquely determined. The calculation steps are as follows:

➀ Calculating the expected range of the coincident edge. Similar to Case 1, but with the upper vertex of the coincident edge being fixed, we only need to focus on the minimum value of the bottom edge. The specific calculation formula is shown in Formula (12):

$$\left\{\begin{array}{c}{s}_1=y_1^{\prime } \\ s_2=y_2^{\prime }+{\displaystyle \frac{\left(y_3-y_2\right)\left(y_1^{\prime }-y_2^{\prime }\right)}{\left(y_1-y_2\right)}} \end{array}\right.$$

(12)

➁ Calculating the position of the coincident edge. When calculating the position of B in the rectangular cartogram, the angle θ between the centroids of A and B should remain consistent with that in the rectangular segmentation map. Based on this constraint and considering the expected area of B, the following calculation Formula (13) can be used to compute $y_3^{\prime }$ and $x_3^{\prime }$.

$$\left\{\begin{array}{c}tan \theta ={\displaystyle \frac{y_3^{\prime }-y_2^{\prime }}{x_3^{\prime }-x_1^{\prime }}} \\ area\left(B\right)=\left(y_1^{\prime }-y_3^{\prime }\right)\left(x_3^{\prime }-x_2^{\prime }\right)\end{array}\right.$$

(13)

➂ Determining whether the coincident edge is within the expected range. If ${\mathrm{y}}_3^{\prime }<{\mathrm{s}}_2$, then set ${\mathrm{y}}_3^{\prime }={\mathrm{s}}_2$.

➃ Determining the position of B. Based on the expected area and the determined $y_3^{\prime }$ and $y_1^{\prime }$, the corresponding $x_3^{\prime }$ can be calculated using Formula (14). This allows for the determination of the position of B in the rectangular cartogram.

$$x_3^{\prime }=x_2^{\prime }+{\displaystyle \frac{area\left(B\right)}{(y_3^{\prime }-y_1^{\prime })}}$$

(14)

(3) 

Case 3

In the rectangular cartogram segmentation map, the orange area and the blue area share two common vertices and a shared edge. The adjacency layout is shown in Figure 9a.

Since B and A share two common vertices, $x_3^{\prime }$ can be directly calculated using the expected area, and the position of B can be determined according to Formula (15).

$$x_3^{\prime }=x_2^{\prime }+{\displaystyle \frac{area\left(B\right)}{(y_1^{\prime }-y_2^{\prime })}}$$

(15)

5.3. Algorithm Flow

The algorithm for constructing the rectangular cartogram sequentially places units from the rectangular segmentation map into the cartogram, determining their positions based on expected areas and adjacency relationships. The algorithm proceeds as follows:

Step 1: Determine the Initial Rectangular Cartogram Unit.

Select the unit located at the centroid of the rectangular segmentation map as the initial cartogram unit, setting its centroid to (0, 0). Calculate its position based on the aspect ratio and expected area of the initial unit in the rectangular segmentation map, and add it to the set of confirmed cartogram units, denoted as C.

Step 2: Calculate the Priority of Adjacent Units.

To ensure the relative positional accuracy of the cartogram units, only unplaced units that are adjacent to those in set C are considered. If multiple adjacent unplaced units exist, the one with the highest priority is selected. Priority is determined by the number of vertex coordinates that can be determined for the adjacent unplaced unit in the rectangular cartogram, obtained through common vertices with the already placed units.

Step 3: Determine the Unit to be Placed.

Select the unplaced unit with the highest priority as the unit to be placed. If this unit can form the previously mentioned “orange area” (which consists of multiple units and forms a rectangle) with other unplaced units and the priority of the orange area is not lower than that of the unit to be placed, then the orange area is designated as the new unit to be placed.

Step 4: Calculate the Position of the Unit to be Placed.

Based on the case of adjacency relationships determined in Section 5.2, calculate the position of the unit in the rectangular cartogram, and then add it to set C, updating C accordingly.

Repeat Steps 2 to 4 until all units are included in set C.

5.4. Algorithm Demonstration

Figure 10 provides an example of the algorithm, illustrating the implementation process from the rectangular segmentation map to the rectangular cartogram. The red points in the figure indicate the determined vertices of the units pending placement.

6. Evaluation Metrics and Experimental Results and Analysis

6.1. Evaluation Metrics for Rectangular Cartogram

To assess the effectiveness of rectangular cartogram generation, the following three evaluation metrics are used:

(1) Area error [36]: a metric to evaluate the accuracy of statistics expressed by rectangular area. The area error of a single unit $c_i$ is usually defined as ARE($c_i$). The specific calculation formula is shown in Formula (16):

$$ARE\left(c_i\right)={\displaystyle \frac{\left|O\left(c_i\right)-E\left(c_i\right)\right|}{max\left\{O\left(c_i\right),E\left(c_i\right)\right\}}}$$

(16)

$O\left(c_i\right)$ is the actual area of unit $c_i$, and $E\left(c_i\right)$ is the expected area of unit $c_i$. The area error of the overall region C is defined as ARE(C) and is usually evaluated in terms of the mean error. The calculation method of ARE(C) is shown in Formula (17):

$$ARE\left(C\right)={\displaystyle \frac{1}{n}}{\sum }_{c_i\in \mathrm{C}}{\displaystyle \frac{\left|O\left(c_i\right)-E\left(c_i\right)\right|}{max\left\{O\left(c_i\right),E\left(c_i\right)\right\}}}$$

(17)

(2) Adjacency error [33]: a metric to assess the similarity between the adjacency relation of a unit in a rectangular cartogram and its adjacency relation in the original graph. $A_M$ represents the adjacency relationship set of the original map, while $A_C$ represents the adjacency relationship set of the rectangular cartogram. The adjacency error of the overall region C is defined as ADE(C). The calculation method of ADE(C) is shown in Formula (18):

$$ADE\left(C\right)={\displaystyle \frac{\left|A_C\cup A_M\right|-\left|A_C\cap A_M\right|}{\left|A_C\cup A_M\right|}}$$

(18)

(3) Angle error [34]: a metric for assessing the degree of change in relative position between units. The average angle error of the overall region C is defined as AAE(C). The calculation method of AAE(C) is shown in Formula (19):

$$AAE(C)={\displaystyle \frac{2}{n\left(n-1\right)}}{\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^n\left|\angle (c_i,c_j)-\angle (\overline{c_i},\overline{c_j})\right|$$

(19)

The maximum angle error for region C is defined as MAE(C). The specific calculation formula is shown in Formula (20):

$$MAE\left(C\right)={\max }_{c_i\in \mathrm{C}}\left|\angle \left(c_i,c_j\right)-\angle \left(\overline{c_i},\overline{c_j}\right)\right|$$

(20)

$\mathrm{\angle }(c_i,c_j)$ is the angle between the centroids of the two units after the deformation and $\mathrm{\angle }(\overline{c_i},\overline{c_j})$ is the angle between the centroids of the two units before deformation.

6.2. Experiment Data

The implementation of the algorithm in this paper involves two types of data: geographic data and attribute statistical data. Geographic data are used to construct rectangular segmentation maps, while attribute statistical data are used to adjust the areas of the units in the rectangular segmentation map to generate rectangular cartograms. To validate the applicability of the algorithm, this paper employs three different geographic datasets: districts in Wuhan City, cities in Hubei province (cities whose administrative territories collectively subdivide the entirety of the provincial territory), and the states within the ‘lower 48 states’ of the United States. The details are shown in

Table 2. Experiment data in the study.

Geographic Data	Statistical Data	Year	Number of Units	Data Characteristics
districts in Wuhan City	Population	2022	13	The units in the central urban area have a small geographical area but a large population.
cities in Hubei province	Urbanization Rate	2020	17	The attribute data of each unit show little variation, and the geographical areas are also relatively consistent.
states within the ‘lower 48 states’ of the United States	Population	2010	48	There are many units, and there is a significant variation in the population numbers among them.

.

6.3. Our Algorithm vs. RecMap Algorithm

To evaluate the performance of the proposed algorithm, we employed the same experimental data—population data from districts in Wuhan and urbanization rates from cities in Hubei Province—to construct rectangular cartograms using both our algorithm and the RecMap algorithm. The results generated by our algorithm are shown in Figure 11a and Figure 12a, while Figure 11b and Figure 12b display the results from the RecMap algorithm. Additionally, we conducted an analysis of the evaluation indices for both algorithms, with detailed results presented in

Table 3. Experimental results of two constructions. The bold numbers in the table are the results generated by the algorithm in this paper.

Data	Construction Algorithm	Area Error	Adjacency Error	Average Angle Error	Maximum Angle Error
Population in Wuhan	RecMap	0	0.6	0.082	0.44
	Proposed algorithm	0	0.161	0.015	0.074
Urbanization rate of Hubei Province	RecMap	0	0.579	0.086	0.49
	Proposed algorithm	0	0.054	0.026	0.174

.

(1) Visualization results: The rectangular cartogram generated by the algorithm proposed in this paper effectively preserves the adjacency and relative positioning of most regions, with minimal positional errors in a few regions. In contrast, the RecMap algorithm loses many adjacency relationships and exhibits considerable positional errors. Therefore, the proposed algorithm provides more reliable visualization results for data analysis.

(2) Evaluation metrics: Both algorithms achieve zero area error, but discrepancies exist in adjacency and angle errors. For Wuhan City, the algorithm proposed in this paper achieves 16.1% adjacency error and 7.4% maximum angle error, while the RecMap algorithm shows 60% adjacency error and 44% maximum angle error. For Hubei Province, the corresponding figures are 5.4% and 17.4% for this paper’s algorithm, versus 57.9% and 49% for RecMap, as detailed in Table 3. Thus, this paper’s algorithm shows significant improvements in both adjacency and positional accuracy compared to RecMap.

6.4. Our Algorithm vs. Evolution Strategies Algorithm

Due to not obtaining the code for the Evolution Strategy algorithm, we compared the proposed algorithm with it using the same experimental data. Based on the 2010 geographic map of the United States and population data, the proposed algorithm generated a rectangular cartogram with zero area error and a run time of 8.6 s, as shown in Figure 13. In contrast, the Evolution Strategy algorithm produced a cartogram with an area error of 0.01 and an average run time of 476 s.

Both algorithms initially generate a rectangular segmentation map, followed by the rectangular cartogram. The proposed algorithm improves computational efficiency by simplifying the adjacency layout construction process. Although it does not achieve a perfectly accurate adjacency layout, its impact on the visualization is minimal.

The Evolution Strategy algorithm does not provide a clear computational complexity. Due to the exponential growth of layout options in the algorithm as the number of regions increases, its computation time may rise dramatically as the number of regions increases. In contrast, the algorithm proposed in this paper has a time complexity of O(n³), with a more stable growth in computation time. (Please refer to the Supplementary Materials for a detailed analysis.) Therefore, it significantly outperforms the Evolution Strategy algorithm in terms of efficiency, demonstrating substantial potential for practical applications.

7. Discussion and Conclusions

We conducted an in-depth analysis of the rectangular cartogram construction problem, framing it as a complex multi-objective optimization issue. It is essential to recognize that this problem often necessitates trade-offs among various optimization goals and computational costs. While achieving a fully optimal solution may not be feasible in practical applications, prioritizing specific optimization objectives based on actual requirements is crucial for meeting partial optimization criteria and ultimately arriving at a viable solution.

In this paper, we summarized two distinct approaches to existing rectangular cartogram construction algorithms and thoroughly explored the advantages and limitations of each approach concerning computational cost, area accuracy, adjacency preservation, and relative positioning. Based on this analysis, we developed our algorithmic strategy, which consists of two main processes. First, the map units are simplified into rectangles while maintaining relatively accurate adjacency and orientation relationships among the units, resulting in a rectangular segmentation map. Next, the sizes of the rectangular segments are adjusted based on their attribute values to ensure that the areas are proportional to these values. For each process, we provide corresponding algorithms and clear descriptions. Additionally, our algorithm has been implemented in C++ code.

Moreover, our method was applied to three different datasets, enabling us to compare it with existing algorithms. The results demonstrated that our algorithm outperformed in several key metrics. Specifically, it significantly improved computational efficiency, allowing for the processing of larger datasets. It exhibited relatively small errors in area transformation, thereby enhancing the accuracy of attribute representation. The resulting maps are clearer, are easier to read, has fewer topological errors, and are more effective in information communication.

However, there are still areas for improvement in our algorithm:

(1)

In generating the rectangular segmentation maps, we simplified the calculation of adjacency layouts, which may result in suboptimal adjacency relationships among the units in the final cartogram.

(2)

During the generation of the rectangular cartogram, when calculating the position of the next unit, we primarily focused on the accuracy of area representation and the relative positioning of adjacent units but paid insufficient attention to the aspect ratio of the rectangles. Further adjustments could incorporate the aspect ratio based on practical needs, potentially leading to a more optimal solution, though this would increase computational costs.

Overall, for such a multi-objective optimization problem, we encourage future research to explore these trade-offs and find effective methods to balance the optimization objectives, thereby contributing to the ongoing development of rectangular cartogram methodologies.