System and method for contiguous images from polygons

• US 7,286,144 B2
• Filed: 10/13/2004
• Issued: 10/23/2007
• Est. Priority Date: 02/27/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Keim, Daniel, North, Stephen Charles, Panse, Christian
• Primary Examiner(s): YANG, RYAN R
• Application Number:
  US10/963,868
• Publication Number:
  US 20050062763A1
• Time in Patent Office: 1,105 Days
• Field of Search: 345440-442, 345/619
• 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

A system, method and computer-readable media are disclosed for generating an image from another image of contiguous polygons and a vector containing values to which areas of corresponding polygons are scaled. The method embodiment relates to generating an image from a plurality of contiguous polygons having vertices. The method comprises calculating a shape value associated with a polygon, calculating an altered shape value associated with an altered polygon, the altered polygon being an altered version of the polygon, calculating a shape distortion by comparing the shape value and the altered shape value and determining whether to accept the altered polygon based on the calculated shape distortion.

Claims

1. A computing device for generating a cartogram from 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 computing device comprising:

a module configured to select a vertex for repositioning, the vertex having adjacent polygons;

a module configured to reposition the selected vertex;

a module configured to determine an area error of the adjacent polygons based on corresponding data vector values;

a module configured to determine a shape error of the adjacent polygons based on a Fourier transformation of a curvature function of a perimeter of each polygon; and

a module configured to decide whether to accept or reject the repositioning step based on the shape error and the area error.

2. The computing device of claim 1, wherein the curvature function includes circular arcs approximating regions surrounding each vertex of the polygons.

3. The computing device 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 computing device of claim 2, wherein the radius is smaller that one half a length of a shortest edge of the polygon.

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

6. The computing device of claim 2, wherein the curvature function is normalized to a predetermined perimeter length.

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

.

8. The computing device of claim 2, wherein the module configured to select a vertex further selects the vertex from a set of vertices in a region of the contiguous polygons having two edges orthogonal to a preselected scan line.

9. The computing device of claim 2, wherein each module performs its function on all vertices within the region.

10. The computing device of claim 2, wherein the area 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^j_desire is a target is a target value proportional to values contained in the data vector for the j^th polygon and A^j_actual is an actual area value for that polygon.

11. The computing device of claim 2, further comprising a module configured to selectively remove at least one vertex from the plurality of contiguous polygons.

12. The computing device of claim 11, wherein the module configured to selectively remove at least one vertex further selects a vertex based on a proximity to 180 degrees of an angle formed by adjacent edges.

13. The computing device of claim 11, wherein the module configured to selectively remove at least one vertex further selects vertices based on a length of adjacent edge.

14. The computing device of claim 11, wherein the at least one vertex is removed by removing all interior vertices not common to more than two polygons.

15. The computing device of claim 11, wherein interior vertices are removed based on criteria different from those used to remove vertices on a global polygon.

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

a module configured to determine a first curvature function of a first polygon;

a module configured to perform a Fourier transform of the first curvature function to calculate a first shape value;

a module configured to reposition one of the vertices of the polygon to an altered polygon;

a module configured to determine an altered curvature function of the altered polygon;

a module configured to perform a Fourier transform of the altered curvature function to calculate an alter shape value;

a module configured to calculate a shape distortion by comparing the first and the altered shape values; and

a module to decide whether to accept the altered polygon based on the shape distortion.

17. The computing device of claim 16, wherein the module configured to determine curvature functions of the polygons further approximates a region surrounding each vertex with a circular arc.

18. The computing device of claim 17, further comprising a module configured to normalize a perimeter length of 2π

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

/50.

19. The computing device of claim 17, wherein the radius is smaller that one half a length of a shortest edge of the polygon.

20. The computing device of claim 16, wherein each is represented by a series of concatenated straight lines and radii, and the curvature function is a square wave.

21. The computing device of claim 16, wherein the module configured to determine curvature function normalized to a predetermined perimeter length.

22. The computing device of claim 21, wherein the perimeter length is normalized to 2π

.

23. The computing device of claim 16, wherein the module configured to perform a Fourier transform further computes coefficients of Fourier transforms and analytically.

24. The computing device of claim 16, wherein the module configured to reposition one of the polygon further selects the vertices from set of vertices in a region of the contiguous polygons having two edges orthogonal to a preselected scan line.

25. The computing device of claim 24, wherein the modules perform each of their respective functions on all vertices within the region.

26. The computing device of claim 16, wherein the vector values define target area values or the corresponding polygons and the computing device further comprises:

a module configured to calculate a relative area error of the first polygon by comparing an actual area value of the first polygon with a corresponding target area value;

a module configured to calculate 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

a module configured to determine 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.

27. The computing device of claim 26, wherein the area 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^j_desire is a target area value proportional to values contained in the data vector for the j^th polygon and A^j_actual is an actual area value for that polygon.

28. The computing device of claim 26, further comprising a module configured to selectively remove at least one vertex from the plurality of contiguous polygons.

29. The computing device of claim 28, wherein the module configured to selectly remove at least one vertex further selects a vertex based on a proximity to 180 degrees of an angle formed by adjacent edges.

30. The computing device of claim 28, wherein the module configured to selectively remove at least one vertex further selects vertices based on a length of adjacent edge.

31. The computing device of claim 28, wherein the at least one vertex is removed by removing all interior vertices not common to more than two polygons.

32. The computing device of claim 28, wherein interior vertices are removed based on criteria different from those used to remove vertices on a global polygon.

33. A computer readable medium storing a computer program having instructions for generating a cartogram from plurality of contiguous polygons having vertices, and from a vector containing values corresponding the polygons, the instructions 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 a corresponding data vector values;

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

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