Method for generating contiguous cartograms

• US 6,853,386 B1
• Filed: 02/21/2003
• Issued: 02/08/2005
• Est. Priority Date: 02/27/2002
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Keim, Daniel, Panse, Christian, North, Stephen Charles
• Primary Examiner(s): Luu, Matthew
• Assistant Examiner(s): Lee, Hwa C.
• Application Number:
  US10/371,714
• Time in Patent Office: 718 Days
• Field of Search: 345/440, 345/441, 345/581, 345/582, 345/427, 345/647
• US Class Current: 345/647
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F
• CPC Class Codes: G09B 29/001 Planning boards
• CPC Class Codes: G09B 29/005 Map projections or methods associated specifically therewith

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 reached

The 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 the polygon. The proposed iterative step is accepted or discarded based in part on the magnitude of the resulting shape error.

Claims

1. A method for generating a cartogram from a plurality of contiguous polygons having vertices, and from a vector containing values corresponding to the polygons, the method comprising the steps of:

determining a first curvature function of a first polygon;

performing a Fourier transform of the first curvature function to calculate a first shape value;

repositioning one of the vertices of the polygon to produce an altered polygon;

determining an altered curvature function of the altered polygon;

performing a Fourier transform of the altered curvature function to calculate an altered shape value;

calculating a shape distortion by comparing the first and the altered shape values; and

deciding whether to accept the altered polygon based on the shape distortion.

2. The method of claim 1, wherein the steps of determining curvature functions of the polygons include approximating a region surrounding each vertex with a circular arc.

3. The method of claim 2, further comprising the step of normalizing a perimeter length of 2π

for each polygon, and wherein a radius of the circular arcs is π

/50.

4. The method of claim 2, wherein the radius is smaller than one half a length of a shortest edge of the polygon.

5. The method of claim 1, wherein each polygon is represented by a series of concatenated straight lines and radii, and the curvature function is a square wave.

6. The method of claim 1, wherein the steps of determining curvature functions include normalizing a perimeter length for each polygon.

7. The method of claim 6, wherein the perimeter length is normalized to 2π

.

8. The method of claim 1, wherein the steps of performing Fourier transforms include computing coefficients of Fourier sums analytically.

9. The method of claim 1, wherein the step of repositioning one of the vertices of the polygon includes selecting the vertices from a set of vertices in a region of the contiguous polygons having two edges orthogonal to a preselected scan line.

10. The method of claim 9, wherein each of the steps is performed on all vertices within the region.

11. The method of claim 1, wherein the vector values define target area values of the corresponding polygons, and further comprising the steps of:

calculating a relative area error of the first polygon by comparing an actual area value of the first polygon with a corresponding target area value;

calculating a relative area error of the altered polygon by comparing an actual area value of the altered polygon with the corresponding target area value; and

determining whether to revert to the first polygon by comparing the relative area error of the altered polygon and the relative area error of the first polygon.

12. The method of claim 11, wherein the relative area error of a j^th polygon is defined as follows:

$\frac{<br><br>A_{\mathrm{desire}}^j-A_{\mathrm{actual}}^j<br><br>}{A_{\mathrm{desire}}^j+A_{\mathrm{actual}}^j}$

wherein A_desire^j is a target area value for the j^th polygon and A_actual^j is an actual area value for that polygon.

13. The method of claim 1, further comprising the initial step of selectively removing at least one vertex from the plurality of contiguous polygons.

14. The method of claim 13, wherein the step of selectively removing at least one vertex comprises selecting a vertex based on a proximity to 180 degrees of an angle formed by adjacent edges.

15. The method of claim 13, wherein the step of selectively removing at least one vertex comprises selecting vertices based on a length of an adjacent edge.

16. The method of claim 13, wherein the at least one vertex is removed by removing all interior vertices not common to more than two polygons.

17. The method of claim 13, wherein interior vertices are removed based on criteria different from those used to remove vertices on a global polygon.

18. A method for generating a cartogram from a map having a plurality of contiguous map polygons with vertices, the cartogram having a plurality of cartogram polygons corresponding to the map polygons, the cartogram polygons having areas proportional to values contained in a data vector, the method comprising the steps of:

selecting a vertex for repositioning, the vertex having adjacent polygons;

repositioning the selected vertex;

determining an area error of the adjacent polygons based on corresponding data vector values;

determining a shape error of the adjacent polygons based on a Fourier transformation of a curvature function of a perimeter of each polygon; and

deciding whether to accept or reject the repositioning step based on the shape error and the area error.

19. The method of claim 18, wherein the curvature function includes circular arcs approximating regions surrounding each vertex of the polygons.

20. The method of claim 19, further comprising the step of normalizing a perimeter length of 2π

for each polygon, and wherein a radius of the circular arcs is π

/50.

21. The method of claim 19, wherein the radius is smaller than one half a length of a shortest edge of the polygon.

22. The method of claim 18, wherein each polygon is represented by a series of concatenated straight lines and radii, and the curvature function is a square wave.

23. The method of claim 18, wherein the curvature function is normalized to a predetermined perimeter length.

24. The method of claim 23, wherein the perimeter length is normalized to 2π

.

25. The method of claim 18, wherein Fourier sums are analytically computed from the Fourier transforms.

26. The method of claim 18, wherein the step of selecting a vertex includes selecting the vertex from a set of vertices in a region of the contiguous polygons having two edges orthogonal to a preselected scan line.

27. The method of claim 26, wherein each of the steps is performed on all vertices within the region.

28. The method of claim 18, wherein the area error of j^th polygon is defined as follows:

$\frac{<br><br>A_{\mathrm{desire}}^j-A_{\mathrm{actual}}^j<br><br>}{A_{\mathrm{desire}}^j+A_{\mathrm{actual}}^j}$

wherein A_desire^j is a target area value proportional to values contained in the data vector for the j^th polygon and A_actual^j is an actual area value for that polygon.

29. The method of claim 18, further comprising the initial step of selectively removing at least one vertex from the plurality of contiguous polygons.

30. The method of claim 29, wherein the step of selectively removing at least one vertex comprises selecting a vertex based on a proximity to 180 degrees of an angle formed by adjacent edges.

31. The method of claim 29, wherein the step of selectively removing at least one vertex comprises selecting vertices based on a length of an adjacent edge.

32. The method of claim 29, wherein the at least one vertex is removed by removing all interior vertices not common to more than two polygons.

33. The method of claim 29, wherein interior vertices are removed based on criteria different from those used to remove vertices on a global polygon.