# recmap: Compute a Rectangular Statistical Cartogram In recmap: Compute the Rectangular Statistical Cartogram

## Description

The input consists of a map represented by overlapping rectangles. The algorithm requires as input for each map region:

• a tuple of (x, y) values corresponding to the (longitude, latitude) position,

• a tuple of (dx, dy) of expansion along (longitude, latitude),

• and a statistical value z.

The (x, y) coordinates represent the center of the minimal bounding boxes (MBB), The coordinates of the MBB are derived by adding or subtracting the (dx, dy) / 2 tuple accordingly. The tuple (dx, dy) also defines the ratio of the map region. The statistical values define the desired area of each map region.

The output is a rectangular cartogram where the map regions are:

• Non-overlapping,

• connected,

• ratio and area of each rectangle correspond to the desired areas,

• rectangles are placed parallel to the axes.

The construction heuristic places each rectangle in a way that important spatial constraints, in particular

• the topology of the pseudo dual graph,

• the relative position of MBB centers.

are tried to be preserved.

The ratios are preserved and the area of each region corresponds to the as input given statistical value z.

## Usage

 `1` ``` recmap(V, E = data.frame(u=integer(), v=integer())) ```

## Arguments

 `V` defines the input map regions formatted as `data.frame` having the column names `c('x', 'y', 'dx', 'dy', 'z', 'name')` as described above. V could also be considered as the nodes of the pseudo dual. `E` defines the edges of the map region's pseudo dual graph. If `E` is not provided, this is the default; the pseudo dual graph is composed of overlapping rectangles. If used, E must be a `data.frame` containing two columns named `c('u', 'v')` of type integer referencing the row number of `V`.

## Details

The basic idea of the current recmap implementation:

1. Compute the pseudo dual out of the overlapping map regions.

2. Determine the core region by `index <- int(n / 2)`.

3. Place region by region along DFS skeleton of pseudo dual starting with the core region.

Note: if a rectangle can not be placed, accept a non-feasible solution (avoid solutions having a topology error higher than 100) Solving this constellation can be intensive in the computation, and due to the assumably low fitness value the candidate cartogram will be likely rejected by the metaheuristic.

Time Complexity: The time complexity is O(n^2), where n is the number of regions. DFS is visiting each map region only once and therefore has time complexity O(n). For each placement, a constant number of MBB intersection are called (max 360). MBB check is implemented using `std::set`, `insert`, `upper_bound`, `upper_bound` costs are O(log(n)). However, the worst case for a range query is O(n), if and only if dx or dy cover the whole x or y range. Q.E.D.

Performance: In praxis, computing on a 2.4 GHz Intel Core i7 machine (using only one core), using the 50 state U.S. map example, recmap can compute approximately 100 cartograms in one second. The number of MBB calls were (Min., Median, Mean, Max) = (1448, 2534, 3174, 17740), using in each run a different index order using the (`sample`) method.

Geodetic datum: the `recmap` algorithm is not transforming the geodetic datum, e.g., WGS84 or Swissgrid.

## Value

Returns a `recmap` S3 object of the transformed map with new coordinates (x, y, dx, dy) plus additional columns containing information for topology error, relative position error, and the DFS number. The error values are thought to be used for fitness function of the metaheuristic.

## Author(s)

Christian Panse, 2016

## References

• Roland Heilmann, Daniel Keim, Christian Panse, and Mike Sips (2004). "RecMap: Rectangular Map Approximations." InfoVis 2004, IEEE Symposium on Information Visualization, Austin, Texas, 33-40. doi: doi: 10.1109/INFVIS.2004.57.

• Panse C (2018). "Rectangular Statistical Cartograms in R: The recmap Package." Journal of Statistical Software, Code Snippets, 86(1), pp. 1-27. doi: 10.18637/jss.v086.c01.

## See Also

• S3 class methods: `plot.recmap` and `summary.recmap`.

• the metaheuristic glue methods: `recmapGA` and `recmapGRASP`.

• The package vignette https://CRAN.R-project.org/package=recmap/vignettes/recmap.html or by calling `vignette("recmap")` on the R command prompt.

## Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78``` ```map <- checkerboard(2) cartogram <- recmap(map) map cartogram op <- par(mfrow = c(1, 2)) plot(map) plot(cartogram) ## US example usa <- data.frame(x = state.center\$x, y = state.center\$y, # make the rectangles overlapping by correcting # lines of longitude distance. dx = sqrt(state.area) / 2 / (0.8 * 60 * cos(state.center\$y * pi / 180)), dy = sqrt(state.area) / 2 / (0.8 * 60), z = sqrt(state.area), name = state.name) usa\$z <- state.x77[, 'Population'] US.Map <- usa[match(usa\$name, c('Hawaii', 'Alaska'), nomatch = 0) == 0, ] plot.recmap(US.Map) plot(recmap(US.Map)) par(op) # define a fitness function recmap.fitness <- function(idxOrder, Map, ...){ Cartogram <- recmap(Map[idxOrder, ]) # a map region could not be placed; # accept only feasible solutions! if (sum(Cartogram\$topology.error == 100) > 0){return (0)} 1 / sum(Cartogram\$z / (sqrt(sum(Cartogram\$z^2))) * Cartogram\$relpos.error) } ## Not run: ## use Genetic Algorithms (GA >=3.0.0) as metaheuristic M <- US.Map recmapGA <- ga(type = "permutation", fitness = recmap.fitness, Map = M, monitor = gaMonitor, min = 1, max = nrow(M) , popSize = 4 * nrow(M), maxiter = 10, run = 100, parallel=TRUE, pmutation = 0.25) plot(recmap(M[recmapGA@solution[1,],])) plot(recmapGA) ## End(Not run) ## Not run: # install.packages('rbenchmark') library(rbenchmark) benchmark(recmap(US.Map[sample(50,50),]), replications=100) ## test replications elapsed relative user.self ##1 recmap(US.Map[sample(50, 50), ]) 100 1.255 1 1.124 ## sys.self user.child sys.child ##1 0.038 0 0 ## End(Not run) ## Have Fun! ```

recmap documentation built on May 10, 2021, 9:09 a.m.