We present a new circular-arc cartogram model in which countries are drawn as polygons with circular arcs instead of straight-line segments. Given a political map and values associated with each country in the map, a cartogram is a distorted map in which the areas of the countries are proportional to the corresponding values. In the circular-arc cartogram model straight-line segments can be replaced by circular arcs in order to modify the areas of the polygons, while the corners of the polygons remain fixed. The countries in circular-arc cartograms have the aesthetically pleasing appearance of clouds or snowflakes, depending on whether their edges are bent outwards or inwards. This makes it easy to determine whether a country has grown or shrunk, just by its overall shape. We show that determining whether a given map and given area-values can be realized as a circular-arc cartogram is an NP-hard problem. Next we describe a heuristic method for constructing circular-arc cartograms, which uses a max-flow computation on the dual graph of the map, along with a computation of the straight skeleton of the underlying polygonal decomposition. Our method is implemented and produces cartograms that, while not yet perfectly accurate, achieve many of the desired areas in our real-world examples.
More general cartograms, without restrictions to rectangular or rectilinear shapes, have also been studied. Dougenik introduced a method based on force fields where the map is divided into cells and every cell has a force related to its data value which affects the other cells @cite_17 . Dorling used a cellular automaton approach, where regions exchange cells until an equilibrium has been achieved, i.e., each region has attained the desired amount of cells @cite_8 . This technique can result in significant distortions, thereby reducing readability and recognizability. Keim defined a distance between the original map and the cartogram with a metric based on Fourier transforms, and then used a scan-line algorithm to reposition the edges so as to optimize the metric @cite_1 . Edelsbrunner and Waupotitsch generated cartograms using a sequence of homeomorphic deformations and measured the quality with local distance distortion metrics @cite_13 . Kocmoud and House @cite_0 described a technique that combines the cell-based approach of Dorling @cite_8 with the homeomorphic deformations of Edelsbrunner and Waupotitsch @cite_13 .
@cite_8 @cite_1 @cite_0 @cite_13 @cite_17
1507189098 2151045902 2007701319 2199159668 2071807189
Cartograms are a well-known technique for showing geography-related statistical information, such as population demographics and epidemiological data. The basic idea is to distort a map by resizing its regions according to a statistical parameter, but in a way that keeps the map recognizable. We formally define a family of cartogram drawing problems. We show that even simple variants are unsolvable in the general case. Because the feasible variants are NP-complete, heuristics are needed to solve the problem. Previously proposed solutions suffer from problems with the quality of the generated drawings. For a cartogram to be recognizable, it is important to preserve the global shape or outline of the input map, a requirement that has been overlooked in the past. To address this, our objective function for cartogram drawing includes both global and local shape preservation. To measure the degree of shape preservation, we propose a shape similarity function, which is based on a Fourier transformation of the polygons' curvatures. Also, our application is visualization of dynamic data, for which we need an algorithm that recalculates a cartogram in a few seconds. None of the previous algorithms provides adequate performance with an acceptable level of quality for this application. We therefore propose an efficient iterative scanline algorithm to reposition edges while preserving local and global shapes. Scanlines may be generated automatically or entered interactively to guide the optimization process more closely. We apply our algorithm to several example data sets and provide a detailed comparison of the two variants of our algorithm and previous approaches. Area cartograms are used for visualizing geographically distributed data by attaching measurements to regions of a map and scaling the regions such that their areas are proportional to the measured quantities. A continuous area cartogram is a cartogram that is constructed without changing the underlying map topology. We present a new algorithm for the construction of continuous area cartograms that was developed by viewing their construction as a constrained optimization problem. The algorithm uses a relaxation method that exploits hierarchical resolution, constrained dynamics, and a scheme that alternates goals of achieving correct region areas and adjusting region shapes. It is compared favorably to existing methods in its ability to preserve region shape recognition cues, while still achieving high accuracy. Abstract A homeomorphism from R 2 to itself distorts metric quantities, such as distance and area. We describe an algorithm that constructs homeomorphisms with prescribed area distortion. Such homeomorphisms can be used to generate cartograms, which are geographic maps purposely distorted so their area distributions reflects a variable different from area, as for example population density. The algorithm generates the homeomorphism through a sequence of local piecewise linear homeomorphic changes. Sample results produced by the preliminary implementation of the method are included. Continuous area cartograms distort planimetric maps to produce a desired set of areas while preserving the topology of the original map. We present a computer algorithm which achieves the result iteratively with high accuracy. The approach uses a model of forces exerted from each polygon centroid, acting on coordinates in inverse proportion to distance. This algorithm can handle more realistic descriptions of polygon boundaries than previous algorithms and manual methods, thus enhancing visual recognition.