Density sampling map labels

• US 10,102,669 B2
• Filed: 03/19/2015
• Issued: 10/16/2018
• Est. Priority Date: 09/08/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Watts, Michael Marcel William, Cohen, Erez
• Primary Examiner(s): Summers, Geoffrey E
• Application Number:
  US14/663,181
• Publication Number:
  US 20160070984A1
• Time in Patent Office: 1,307 Days
• Field of Search: 382305
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Sampling map labels is disclosed. A region of a map to be rendered is determined. It is determined that a first subregion is included in the region. Map labels associated with subregions in a neighborhood of the first subregion are analyzed to determine a regional density of map labels. Map labels associated with the first subregion are sampled based on the regional density of map labels.

Claims

1. An electronic device comprising:

a set of processing units; and

a non-transitory machine-readable medium storing a program for sampling map labels in a region of a map, the program comprising sets of instructions for;

determining a first subregion of the map region to be rendered;

determining a set of subregions in a neighborhood of the first subregion;

for each subregion in the set of subregions, applying a weight value to the subregion based on the subregion'"'"'s distance from the first subregion, wherein more weight is applied to a subregion that is closer to the first subregion than a subregion that is farther from the first subregion;

analyzing map labels associated with the set of subregions in the neighborhood of the first subregion to determine a regional density of map labels, the regional density being based on a total weighted area of the set of subregions and a weighted total number of map labels of the set of subregions, where analyzing map labels includes;

calculating the weighted total area of the set of subregions by summing an area for each subregion in the set multiplied by the weight value applied to the subregion,

calculating the weighted total number of map labels of the set of subregions by summing a number of map labels of each subregion in the set multiplied by the weight value applied to the subregion, and

multiplying a desired density by the weighted total area of the neighborhood set of subregions and dividing by the weighted total number of map labels in the neighborhood of the set of subregions; and

sampling map labels associated with the first subregion based on the determined regional density of map labels, wherein a sampling rate for the map labels associated with the first subregion (i) is increased when the determined regional density of map labels decreases and (ii) is decreased when the determined regional density of map labels increases.

2. The electronic device of claim 1 further comprising a communication interface configured to provide the sampled map labels of the first subregion to a client device for rendering.

3. The electronic device of claim 1, wherein the first subregion is associated with a data structure that includes entries corresponding to map labels located within the first subregion.

4. The electronic device of claim 3, wherein the data structure is ordered using a relevance identifier assigned to each map label entry of the data structure.

5. The electronic device of claim 1, wherein the set of subregions in the neighborhood of the first subregion includes one or more subregions located adjacent to the first subregion.

6. The electronic device of claim 1, wherein the set of instructions for analyzing the map labels associated with the set of subregions comprises a set of instructions for determining, for each subregion in the set of subregions, a total number of map labels associated with the subregion that meet an eligibility criteria.

7. The electronic device of claim 1, wherein the set of instructions for analyzing the map labels comprises a set of instructions for determining the desired density.

8. A method for sampling, the method comprising:

determining a first subregion of a map region to be rendered;

determining a set of subregions in a neighborhood of the first subregion;

for each subregion in the set of subregions, applying a weight value to the subregion based on the subregion'"'"'s distance from the first subregion, wherein more weight is applied to a subregion that is closer to the first subregion than a subregion that is farther from the first subregion;

analyzing map labels associated with the set of subregions in the neighborhood of the first subregion to determine a regional density of map labels, the regional density being based on a total weighted area of the set of subregions and a weighted total number of map labels of the set of subregions, where analyzing map labels includes;

calculating the weighted total area of the set of subregions by summing an area for each subregion in the set multiplied by the weight value applied to the subregion,

calculating the weighted total number of map labels of the set of subregions by summing a number of map labels of each subregion in the set multiplied by the weight value applied to the subregion, and

multiplying a desired density by the weighted total area of the neighborhood set of subregions and dividing by the weighted total number of map labels in the neighborhood of the set of subregions; and

sampling map labels associated with the first subregion based on the determined regional density of map labels, wherein a sampling rate for the map labels associated with the first subregion (i) is increased when the determined regional density of map labels decreases and (ii) is decreased when the determined regional density of map labels increases.

9. The method of claim 8, wherein sampling the map labels comprises selecting map labels associated with the first subregion that have a highest relative relevance.

10. The method of claim 9, wherein the relative relevance for each map label is at least partly determined by automatically analyzing reference content.

11. The method of claim 8 further comprising providing the sampled map labels of the first subregion to a client device that renders the map region.

12. A non-transitory machine readable medium storing a program for execution by at least one processing unit, the program comprising computer sets of instructions for:

determining a first subregion of a map region to be rendered;

determining a set of subregions in a neighborhood of the first subregion;

for each subregion in the set of subregions, applying a weight value to the subregion based on the subregion'"'"'s distance from the first subregion, wherein more weight is applied to a subregion that is closer to the first subregion than a subregion that is farther from the first subregion;

analyzing map labels associated with the set of subregions in the neighborhood of the first subregion to determine a regional density of map labels, the regional density being based on a total weighted area of the set of subregions and a weighted total number of map labels of the set of subregions, where analyzing map labels includes;

calculating the weighted total area of the set of subregions by summing an area for each subregion in the set multiplied by the weight value applied to the subregion,

calculating the weighted total number of map labels of the set of subregions by summing a number of map labels of each subregion in the set multiplied by the weight value applied to the subregion, and

multiplying a desired density by the weighted total area of the neighborhood set of subregions and dividing by the weighted total number of map labels in the neighborhood of the set of subregions; and

sampling map labels associated with the first subregion based on the determined regional density of map labels, wherein a sampling rate for the map labels associated with the first subregion (i) is increased when the determined regional density of map labels decreases and (ii) is decreased when the determined regional density of map labels increases.

13. The non-transitory machine readable medium of claim 12, wherein the desired density is based on a user request.

14. The non-transitory machine readable medium of claim 12, wherein the desired density is based on a type of map labels to be rendered.

15. The non-transitory machine readable medium of claim 12, wherein the set of instructions for sampling the map labels comprises selecting map labels associated with the first subregion that have a highest relative relevance.