Method for generating contiguous cartograms

US6853386B1 · kind B1 · utility

Assignee

• AT&T CORP. · US

Inventors

• Daniel Keim · Steißlingen, DE
• Stephen C. North · Lebanon, US
• Christian Panse · Konstanz, DE

Key dates

• Filing date: Feb 21, 2003
• Grant date: Feb 8, 2005
• Expiry date: May 11, 2023

Classification

• Technology area (CPC G): Physics
• CPC primary: G09B29/001
• WIPO field: Control
• WIPO sector: Instruments

Abstract

The present invention is a method for generating cartograms using a base map of contiguous polygons and a vector containing values to which areas of corresponding polygons are scaled. The general problem is intractable, so an iterative heuristic is proposed. The heuristic is based on “scanlines.” The scanlines may be defined automatically (typically, by placing a grid over the map) or entered manually (to provide finer control over the results). At each step, one scanline is chosen and a new candidate map is made by adjusting the vertices of polygons intersected by the scanline, moving them orthogonally to the scanline. A candidate solution is accepted if it improves the solution and preserves the input mesh's topology. Improvement depends on metrics for area and shape error. The solver is run until the improvement falls below some threshold, or a time limit or maximum number of iterations is reachedThe method determines shape error created by a candidate iterative step by first estimating a curvature function of the polygon and then performing a Fourier transform on the function to yield a shape representation that is relatively independent of scale, translation and rotation of th…