| recmap {recmap} | R Documentation |
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 |
E |
defines the edges of the map region's pseudo dual graph.
If |
Details
The basic idea of the current recmap implementation:
Compute the pseudo dual out of the overlapping map regions.
Determine the core region by
index <- int(n / 2).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)
}