Techniques for drawing geodetic polygons

• US 8,085,268 B2
• Filed: 10/20/2009
• Issued: 12/27/2011
• Est. Priority Date: 10/20/2009
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Carrino, John Antonio, Cervelli, Daniel Patrick
• Primary Examiner(s): HAJNIK, DANIEL F
• Application Number:
  US12/582,130
• Publication Number:
  US 20110090254A1
• Time in Patent Office: 798 Days
• Field of Search: None
• US Class Current: 345/427
• CPC Class Codes: G09B 29/005 Map projections or methods associated specifically therewith

Abstract

Techniques in a data processor for drawing on a map a geodetic polygon that straddles a splitting meridian include, in one embodiment, maintaining data that represents the geodetic polygon, the data comprising a set of geographic coordinates; transforming the set of geographic coordinates into a set of planar coordinates representing a planar polygon; splitting the planar polygon into a plurality of sub-figures; shifting at least one sub-figure of the plurality of sub-figures along a horizontal axis of two-dimensional plane to produce a shifted sub-figure; and causing the shifted sub-figure to be displayed on a map concurrently with at least one other sub-figure of the plurality of sub-figures that was not shifted.

Claims

1. A method for drawing a geodetic polygon on a map, the method comprising:

maintaining data that represents a geodetic polygon;

wherein the data comprises an ordered set of geographic coordinates representing adjacent vertices along a perimeter of the geodetic polygon;

transforming the set of geographic coordinates into a set of planar coordinates representing vertices of a planar polygon;

wherein transforming the set of geographic coordinates into the set of planar coordinates includes proceeding through the set of geographic coordinates in a manner that represents a counter clockwise or clockwise traversal along the perimeter of the geodetic polygon until each geographic coordinate of the set of geographic coordinates is transformed to a corresponding planar coordinate;

wherein proceeding through the set of geographic coordinates includes;

transforming a first geographic coordinate of the set of geographic coordinates corresponding to a first vertex of the geodetic polygon to a first planar coordinate,

transforming a second geographic coordinate of the set of geographic coordinates corresponding to a second vertex of the geodetic polygon to a second planar coordinate,

wherein the first vertex and the second vertex are adjacent vertices according to the order of the set of geographic coordinates,

calculating a distance along a horizontal axis of a two-dimensional plane between the first planar coordinate and the second planar coordinate, and

determining that the geodetic polygon straddles a splitting meridian by determining that said distance is greater than one-half a horizontal extent of the map along the horizontal axis of the two-dimensional plane;

where the geodetic polygon straddles the splitting meridian;

dividing the planar polygon into a plurality of sub-figures;

shifting at least one sub-figure of the plurality of sub-figures along the horizontal axis of the two-dimensional plane to produce a shifted sub-figure; and

causing the shifted sub-figure to be displayed on the map concurrently with at least one other sub-figure of the plurality of sub-figures that was not shifted;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein transforming the set of geographic coordinates into the set of planar coordinates representing the planar polygon further comprises:

calculating a third planar coordinate based on a difference between (1) said distance along the horizontal axis and (2) the horizontal extent of the map along the horizontal axis; and

wherein said set of planar coordinates representing said planar polygon includes the first planar coordinate and the third planar coordinate but does not include the second planar coordinate.

3. The method of claim 2, wherein the x-value of the third planar coordinate is based on the x-value of the first planar coordinate and said difference.

4. The method of claim 3, wherein the x-value of the third planar coordinate places the third planar coordinate along the horizontal axis to the right of the right-most boundary of said map.

5. The method of claim 3, wherein the x-value of the third planar coordinate places the third planar coordinate along the horizontal axis to the left of the left-most boundary of said map.

6. The method of claim 1, wherein at least one planar coordinate of said planar polygon has an x-value that places the at least one planar coordinate along the horizontal axis to the right of the right-most boundary of said map.

7. The method of claim 6, wherein at least one other planar coordinate of said planar polygon has an x-value that places the at least one other planar coordinate along the horizontal axis to the left of the left-most boundary of said map.

8. The method of claim 1, wherein splitting the planar polygon into a plurality of sub-figures comprises splitting the planar polygon along the right-most boundary of said map to form two sub-figures comprising the planar polygon.

9. The method of claim 1, wherein splitting the planar polygon into a plurality of sub-figures comprises splitting the planar polygon along the right-most boundary and the left-most boundary of said map to form three sub-figures comprising the planar polygon.

10. The method of claim 1, wherein shifting the at least one sub-figure of the plurality of sub-figures along the horizontal axis comprises:

shifting the at least one sub-figure of the plurality of sub-figures along the horizontal axis by an amount corresponding to the horizontal extent of the map along the horizontal axis.

11. The method of claim 10, wherein the shifted sub-figure has a plurality of vertices having y-values along a vertical axis in the two-dimensional plane equal to the y-values along the vertical axis of the vertices of the at least one sub-figure, and wherein the x-values along the horizontal axis of the vertices of the shifted sub-figure are offset from the x-values along the horizontal axis of the vertices of the at least one sub-figure by an amount equal to the horizontal extent of the map along the horizontal axis.

12. The method of claim 1, wherein the geographic coordinates are maintained in terms of latitude and longitude.

13. The method of claim 1, wherein the set of geographic coordinates are transformed into the set of planar coordinates using a cylindrical projection mapping function selected from the group consisting of a Mercator projection mapping function, a cylindrical equidistant projection mapping function, and a Miller cylindrical projection mapping function.

14. A non-transitory computer-readable medium storing instructions for drawing a geodetic polygon on a map, the instructions, when executed by one or more computing devices, cause the one or more computing devices to perform a method comprising:

maintaining data that represents a geodetic polygon;

wherein the data comprises an ordered set of geographic coordinates representing adjacent vertices along a perimeter of the geodetic polygon;

transforming the set of geographic coordinates into a set of planar coordinates representing vertices of a planar polygon;

wherein transforming the set of geographic coordinates into the set of planar coordinates includes proceeding through the set of geographic coordinates in a manner that represents a counter clockwise or clockwise traversal along the perimeter of the geodetic polygon until each geographic coordinate of the set of geographic coordinates is transformed to a corresponding planar coordinate;

wherein proceeding through the set of geographic coordinates includes;

transforming a first geographic coordinate of the set of geographic coordinates corresponding to a first vertex of the geodetic polygon to a first planar coordinate,

transforming a second geographic coordinate of the set of geographic coordinates corresponding to a second vertex of the geodetic polygon to a second planar coordinate,

wherein the first vertex and the second vertex are adjacent vertices according to the order of the set of geographic coordinates,

calculating a distance along a horizontal axis of a two-dimensional plane between the first planar coordinate and the second planar coordinate, and

determining that the geodetic polygon straddles a splitting meridian by determining that said distance is greater than one-half a horizontal extent of the map along the horizontal axis of the two-dimensional plane;

where the geodetic polygon straddles the splitting meridian;

dividing the planar polygon into a plurality of sub-figures;

shifting at least one sub-figure of the plurality of sub-figures along the horizontal axis of the two-dimensional plane to produce a shifted sub-figure; and

causing the shifted sub-figure to be displayed on the map concurrently with at least one other sub-figure of the plurality of sub-figures that was not shifted.

15. The medium of claim 14, wherein transforming the set of geographic coordinates into the set of planar coordinates representing the planar polygon further comprises:

calculating a third planar coordinate based on a difference between (1) said distance along the horizontal axis and (2) the horizontal extent of the map along the horizontal axis; and

wherein said set of planar coordinates representing said planar polygon includes the first planar coordinate and the third planar coordinate but does not include the second planar coordinate.

16. The medium of claim 15, wherein the x-value of the third planar coordinate is based on the x-value of the first planar coordinate and said difference.

17. The medium of claim 16, wherein the x-value of the third planar coordinate places the third planar coordinate along the horizontal axis to the right of the right-most boundary of said map.

18. The medium of claim 16, wherein the x-value of the third planar coordinate places the third planar coordinate along the horizontal axis to the left of the left-most boundary of said map.

19. The medium of claim 14, wherein at least one planar coordinate of said planar polygon has an x-value that places the at least one planar coordinate along the horizontal axis to the right of the right-most boundary of said map.

20. The medium of claim 19, wherein at least one other planar coordinate of said planar polygon has an x-value that places the at least one other planar coordinate along the horizontal axis to the left of the left-most boundary of said map.

21. The medium of claim 14, wherein splitting the planar polygon into a plurality of sub-figures comprises splitting the planar polygon along the right-most boundary of said map to form two sub-figures comprising the planar polygon.

22. The medium of claim 14, wherein splitting the planar polygon into a plurality of sub-figures comprises splitting the planar polygon along the right-most boundary and the left-most boundary of said map to form three sub-figures comprising the planar polygon.

23. The medium of claim 14, wherein shifting the at least one sub-figure of the plurality of sub-figures along the horizontal axis comprises:

shifting the at least one sub-figure of the plurality of sub-figures along the horizontal axis by an amount corresponding to the horizontal extent of the map along the horizontal axis.

24. The medium of claim 23, wherein the shifted sub-figure has a plurality of vertices having y-values along a vertical axis in the two-dimensional plane equal to the y-values along the vertical axis of the vertices of the at least one sub-figure, and wherein the x-values along the horizontal axis of the vertices of the shifted sub-figure are offset from the x-values along the horizontal axis of the vertices of the at least one sub-figure by an amount equal to the horizontal extent of the map along the horizontal axis.

25. The medium of claim 14, wherein the geographic coordinates are maintained in terms of latitude and longitude.

26. The medium of claim 14, wherein the set of geographic coordinates are transformed into the set of planar coordinates using a cylindrical projection mapping function selected from the group consisting of a Mercator projection mapping function, a cylindrical equidistant projection mapping function, and a Miller cylindrical projection mapping function.

27. A geodetic polygon drawing computer system comprising:

memory configured to store data that represents a geodetic polygon;

wherein the data comprises an set of geographic coordinates representing adjacent vertices along a perimeter of the geodetic polygon;

transformation logic coupled to the memory and configured to transform a state of the memory by transforming the set of geographic coordinates into a set of planar coordinates representing vertices of a planar polygon;

wherein the transformation logic includes logic configured to transform a state of the memory by;

proceeding through the set of geographic coordinates in a manner that represents a counter clockwise or clockwise traversal along the perimeter of the geodetic polygon until each geographic coordinate of the set of geographic coordinates is transformed to a corresponding planar coordinate,

transforming a first geographic coordinate of the set of geographic coordinates corresponding to a first vertex of the geodetic polygon to a first planar coordinate,

transforming a second geographic coordinate of the set of geographic coordinates corresponding to a second vertex of the geodetic polygon to a second planar coordinate,

wherein the first vertex and the second vertex are adjacent vertices according to the order of the set of geographic coordinates,

calculating a distance along a horizontal axis of a two-dimensional plane between the first planar coordinate and the second planar coordinate, and

determining that the geodetic polygon straddles a splitting meridian by determining that said distance is greater than one-half a horizontal extent of a map along the horizontal axis of the two-dimensional plane;

planar polygon splitting logic coupled to the transformation logic and configured to further transform the state of the memory by dividing the planar polygon into a plurality of sub-figures where the geodetic polygon straddles the splitting meridian;

shifting logic coupled to the planar polygon splitting logic and configured to further transform the state of the memory by shifting at least one sub-figure of the plurality of sub-figures along the horizontal axis of the two-dimensional plane to produce a shifted sub-figure where the geodetic polygon straddles the splitting meridian; and

display driving logic configured to cause displaying, on a computer display unit, the shifted sub-figure on the map concurrently with at least one other sub-figure of the plurality of sub-figures that was not shifted where the geodetic polygon straddles the splitting meridian.