EFFICIENT PRE-COMPUTING OF SIMPLIFIED VECTOR DATA FOR RENDERING AT MULTIPLE ZOOM LEVELS

• US 20120206469A1
• Filed: 02/15/2011
• Published: 08/16/2012
• Est. Priority Date: 02/15/2011
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hulubei, Tudor, Eustis, David
• Application Number:
  US13/027,540
• Publication Number:
  US 20120206469A1
• Time in Patent Office: Days
• US Class Current: 345/581
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G09B 29/006 Representation of non-cartographic information on maps, e.g. population distribution, wind direction, radiation levels, air and sea routes
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

Aspects of the invention relate generally to accessing, storing, and processing vector data to represent various geographical features such as roads, rivers, lakes, countries, continents, and oceans on one or more maps. More specifically, the vector data may be pre-simplified for rendering at different zoom levels. The simplification process is based on removing vertices from vector data in order to reduce the number of points in a given polygon or line. As this process is very expensive in terms of time and processing power, the system and method allow for estimation of the proportion of vertices which that would be removed from the original geometry. Based on this estimation, one may decide whether or not the simplification is worth the effort to compute and store the simplified data.

Claims

1. A computer-implemented method comprising:

accessing map information associated with a first zoom level, the map information including a plurality of vertices associated with one or more objects such that each object is associated with a set of one or more vertices of the plurality of vertices;

identifying a minimum threshold proportion for determining whether to simplify the map information;

identifying a tolerance distance value associated with a second zoom level that includes a lesser amount of detail than the first zoom level;

determining, by a processor, a subset of the plurality of vertices based on;

(1) for each object of the one or more objects, calculating a distance from each given vertex of the set of one or more vertices associated with the object to a line between the immediate neighboring vertices of the given vertex, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the second zoom level;

determining a proportion based on the subset and the plurality of vertices; and

if the proportion is greater than or equal to the minimum threshold proportion, calculating a simplified version of the map information at the second zoom level.

2. The method of claim 1, further comprising:

identifying a tolerance distance value associated with a third zoom level;

if the proportion is less than the minimum threshold value, determining, by the processor, a second subset of the plurality of vertices based on;

(1) for each object of the one or more objects, calculating the distance from each given vertex of the set of one or more vertices associated with the object to a line between the immediate neighboring vertices of the given vertex, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the third zoom level;

determining a second proportion based on the second subset and the plurality of vertices; and

if the second proportion is greater than the minimum threshold value, calculating another simplified version of the map information at the third zoom level.

3. The method of claim 2, wherein the second zoom level includes a greater level of detail than the third zoom level.

4. The method of claim 2, wherein the tolerance distance value associated with the second zoom level is less than the tolerance distance value associated with the third zoom level.

5. The method of claim 1, wherein the simplified version of the map information at the second zoom level includes a second plurality of vertices of the plurality of vertices associated with one or more second objects such that each second object is associated with a second set of one or more vertices of the plurality of vertices;

identifying a tolerance distance value associated with a third zoom level which includes a lesser amount of detail than the second zoom level;

determining, by the processor, a second subset of the plurality of vertices based on;

(1) for each second object of the one or more second objects, calculating a distance from each given vertex of the second set of one or more vertices associated with the second object to a line between the immediate neighboring vertices of the given vertex associated with the second object, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the third zoom level;

determining a second proportion based on the second subset and the plurality of vertices; and

if the second proportion is greater than or equal to the minimum threshold value, calculating a second simplified version of the map information at the third zoom level.

6. The method of claim 5, further comprising:

identifying a tolerance distance value associated with a fourth zoom level;

if the second proportion is less than the minimum threshold value, determining, by the processor, a third subset of the plurality of vertices based on;

(1) for each second object of the one or more second objects, calculating a distance from each given vertex of the set of one or more vertices associated with the second object to a line between the immediate neighboring vertices of the given vertex associated with the second object, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the fourth zoom level;

determining a third proportion based on the third subset and the plurality of vertices; and

if the third proportion is greater than the minimum threshold value, calculating another simplified version of the map information at the fourth zoom level.

7. The method of claim 5, further comprising:

receiving, from a first device, a request for map information associated with a particular zoom level including a particular level of detail;

identifying responsive map information associated with a zoom level which includes a level of detail closest to the particular level of detail and which is also greater than or equal to the particular level of detail; and

transmitting the responsive map information to the first device for display at the particular zoom level.

8. The method of claim 5, further comprising storing the simplified version of the map information at the second zoom level and the second simplified version of the map information at the third zoom level in memory accessible by the processor.

9. A device comprising:

memory storing map information associated with a first zoom level, the map information including a plurality of vertices associated with one or more objects such that each object is associated with a set of one or more vertices of the plurality of vertices;

a processor coupled to the memory, the processor being operable to;

identify a minimum threshold proportion for determining whether to simplify the map information;

identify a tolerance distance value associated with a second zoom level that includes a lesser amount of detail than the first zoom level;

determine a subset of the plurality of vertices based on;

(1) for each object of the one or more objects, calculating a distance from each given vertex of the set of one or more vertices associated with the object to a line between the immediate neighboring vertices of the given vertex, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the second zoom level;

determine a proportion based on the subset and the plurality of vertices; and

if the proportion is greater than or equal to the minimum threshold proportion, calculate a simplified version of the map information at the second zoom level.

10. The device of claim 9, wherein the processor is further operable to:

identify a tolerance distance value associated with a third zoom level;

if the proportion is less than the minimum threshold value, determine a second subset of the plurality of vertices based on;

(1) for each object of the one or more objects, calculating the distance from each given vertex of the set of one or more vertices associated with the object to a line between the immediate neighboring vertices of the given vertex, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the third zoom level;

determine a second proportion based on the second subset and the plurality of vertices; and

if the second proportion is greater than the minimum threshold value, calculate another simplified version of the map information at the third zoom level.

11. The device of claim 10, wherein the second zoom level includes a greater level of detail than the third zoom level.

12. The device of claim 10, wherein the tolerance distance value associated with the second zoom level is less than the tolerance distance value associated with the third zoom level.

13. The device of claim 9, wherein the simplified version of the map information at the second zoom level includes a second plurality of vertices of the plurality of vertices associated with one or more second objects such that each second object is defined by a second set of one or more vertices of the plurality of vertices, and the processor is further operable to:

identify a tolerance distance value associated with a third zoom level which includes a lesser amount of detail than the second zoom level;

determine a second subset of the plurality of vertices based on;

(1) for each second object of the one or more second objects, calculating a distance from each given vertex of the second set of one or more vertices associated with the second object to a line between the immediate neighboring vertices of the given vertex associated with the second object, and

(2) determine whether each calculated distance is less than or equal to the tolerance distance value associated with the third zoom level; and

determine a second proportion based on the second subset and the plurality of vertices; and

if the second proportion is greater than or equal to the minimum threshold value, calculate a second simplified version of the map information at the third zoom level.

14. The device of claim 13, wherein the processor is further operable to:

identify a tolerance distance value associated with a fourth zoom level;

if the second proportion is less than the minimum threshold value, determine a third subset of the plurality of vertices based on;

(1) for each second object of the one or more second objects, calculating a distance from each given vertex of the set of one or more vertices associated with the second object to a line between the immediate neighboring vertices of the given vertex associated with the second object, and

(2) determining whether each calculated distance is less than or equal to the tolerance distance value associated with the fourth zoom level; and

determine a third proportion based on the third subset and the plurality of vertices; and

if the third proportion is greater than the minimum threshold value, calculate another simplified version of the map information at the fourth zoom level.

15. The device of claim 13, wherein the processor is further operable to:

receive, from a first device, a request for map information associated with a particular zoom level including a particular level of detail;

identify responsive map information associated with a zoom level which includes a level of detail closest to the particular level of detail and which is also greater than or equal to the particular level of detail; and

transmit the responsive map information to the first device for display at the particular zoom level.

16. The device of claim 13, wherein the processor is further operable to store the simplified version of the map information at the second zoom level and the second simplified version of the map information at the third zoom level in the memory.