recmap: Compute a Rectangular Statistical Cartogram

In recmap: Compute the Rectangular Statistical Cartogram

Compute a 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

recmap(V, E = NULL)

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

Examples

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)
US.Map |> recmap() |> plot()
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)
}

recmap documentation built on Sept. 24, 2023, 1:08 a.m.