R/RcppExports.R

Defines functions recmap place_rectangle get_angle

Documented in recmap

# Generated by using Rcpp::compileAttributes() -> do not edit by hand
# Generator token: 10BE3573-1514-4C36-9D1C-5A225CD40393

#' @import Rcpp
get_angle <- function(x0, y0, x1, y1) {
    .Call('_recmap_get_angle', PACKAGE = 'recmap', x0, y0, x1, y1)
}

place_rectangle <- function(x0, y0, dx0, dy0, dx1, dy1, alpha) {
    .Call('_recmap_place_rectangle', PACKAGE = 'recmap', x0, y0, dx0, dy0, dx1, dy1, alpha)
}

#' 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:
#' \itemize{
#'   \item{a tuple of (x, y) values corresponding to the 
#'  (longitude, latitude) position,}
#'   \item{a tuple of (dx, dy) of expansion along (longitude, latitude),}
#'  \item{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:
#'
#' \itemize{
#'   \item{Non-overlapping,}
#'   \item{connected,}
#'   \item{ratio and area of each rectangle correspond to the desired areas,}
#'   \item{rectangles are placed parallel to the axes.}
#' }
#'
#' The construction heuristic places each rectangle in a way that important spatial 
#' constraints, in particular
#' \itemize{
#'   \item{the topology of the pseudo dual graph,}
#'   \item{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.
#'
#' @param V defines the input map regions formatted as \code{\link{data.frame}}
#'  having the column names \code{c('x', 'y', 'dx', 'dy', 'z', 'name')} 
#'  as described above. V could also be considered as the nodes of the pseudo dual.
#'
#' @param E  defines the edges of the map region's pseudo dual graph. 
#'  If \code{E} is not provided, this is the default; the pseudo dual graph is
#'  composed of overlapping rectangles. If used, E must be a
#'  \code{\link{data.frame}} containing two columns named \code{c('u', 'v')}
#'  of type integer referencing the row number of \code{V}.
#'
#' @details The basic idea of the current recmap \emph{implementation}:
#' \enumerate{
#'  \item{Compute the pseudo dual out of the overlapping map regions.}
#'  \item{Determine the \emph{core region} by \code{index <- int(n / 2)}.}
#'  \item{Place region by region along DFS skeleton of pseudo dual starting 
#'  with the \emph{core region}.}}
#'
#' Note: if a rectangle can not be placed, accept a non-\emph{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.
#'
#' \emph{Time Complexity:}
#' The time complexity is \eqn{O(n^2)}, where n is the number of regions.
#' DFS is visiting each map region only once and therefore has 
#' time complexity \eqn{O(n)}. For each placement, a constant number of
#' MBB intersection are called (max 360). MBB check is implemented using
#' \code{std::set}, \code{insert}, \code{upper_bound}, \code{upper_bound} 
#' costs are \eqn{O(\log(n))}{O(log(n))}.
#' However, the worst case for a range query is \eqn{O(n)}, if and only if dx or dy
#' cover the whole x or y range. Q.E.D.
#' 
#' \emph{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 (\code{\link{sample}}) method.
#' 
#' \emph{Geodetic datum:} the \code{recmap} algorithm is not transforming the 
#' geodetic datum, e.g., WGS84 or Swissgrid.
#' 
#' @return
#' Returns a \code{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.
#'
#' @aliases RecMap cartogram all.equal.recmap
#'
#' @author 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)
#' }
#'
#' @export
recmap <- function(V, E = NULL) {
    .Call('_recmap_recmap', PACKAGE = 'recmap', V, E)
}
cpanse/recmap documentation built on Jan. 3, 2024, 11:45 p.m.