System and method for identifying bounds of a geographical area

• US 7,576,754 B1
• Filed: 04/07/2006
• Issued: 08/18/2009
• Est. Priority Date: 10/27/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rose, Mark, Ramaswamy, Sridhar, Joseph, Joshy
• Primary Examiner(s): Sajous; Wesner
• Application Number:
  US11/399,949
• Time in Patent Office: 1,229 Days
• Field of Search: 345619-620, 345/643, 345/645, 345/660, 345/671, 715/213, 715/216, 715/218, 715/241, 715/246, 715/247, 715/788, 715/790, 715800-801, 715/815, 715/866, 701/200, 701/212, 701206-208, 701214-216, 707/3, 707/14
• US Class Current: 345/619
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/53 using third party service providers
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

A system and method for determining bounds of a geographical area, such as a city, metropolis, region (e.g., state) or country. From a set of coordinates within the area (e.g., latitude/longitude coordinates), a grid of relatively small cells of geographic data is overlaid upon those coordinates and associated with the area. Each initial cell is iteratively replaced with a larger cell that encompasses the initial cell until the replacement cell intersects a cell associated with some other geographical area or some other boundary condition is met (e.g., a threshold number of replacements).

Claims

1. A computer-implemented method of identifying boundaries of a geographic area comprising a city, the method comprising:

(a) identifying coordinates of multiple cities;

(b) associating with each city a grid of cells of geographic data encompassing the city'"'"'s coordinates;

(c) for each cell associated with a city, identifying a larger replacement cell of geographic data encompassing the cell;

(d) testing for intersection between replacement cells of cells of different cities;

(e) for each cell whose replacement cell does not intersect another replacement cell of another cell of another city, replacing the cell with the replacement cell and associating the replacement cell with the city;

(f) repeating (c)-(e) to replace replacement cells with further replacement cells until;

(1) no cell associated with a city can be replaced without the replacement cell intersecting a replacement cell associated with a different city;

or

(2) said (e) has been performed a threshold number of times;

or

(3) an area covered by cells associated with the city meets a threshold size; and

(g) using said replacement cells to define a boundary of the geographic area;

wherein the method is implemented in a computer system that comprises a process and a memory.

2. The method of claim 1, wherein a replacement cell intersects another replacement cell if the replacement cell and the other replacement cell are the same cell.

3. The method of claim 1, wherein said (d) further comprises testing for intersection between a replacement cell of a cell associated with a city and a replacement cell associated with a geographic area that does not include the city.

4. The method of claim 1, wherein said (d) further comprises testing for intersection between a replacement cell of a cell associated with a city and a void cell.

5. The method of claim 4, wherein a void cell is a cell encompassing a body of water that is not part of the geographic area.

6. The method of claim 4, wherein a void cell is a cell whose geographic data is substantially devoid of land.

7. The method of claim 4, wherein a void cell is a cell comprising null geographic data.

8. The method of claim 4, wherein a void cell is a cell comprising less than a threshold of geographic data.

9. The method of claim 1, wherein:

said identified coordinates are latitude/longitude coordinates of the cities; and

said grid comprises leaf cells of a hierarchical tree of cells of geographic data.

10. The method of claim 9, wherein said associating a grid of cells comprises:

identifying within the hierarchical tree a first leaf cell whose geographic data encompass the city'"'"'s coordinates; and

identifying additional leaf cells whose geographic data are adjacent to the geographic data of the first leaf cell.

11. The method of claim 9, wherein a replacement cell of a cell associated with a city is the immediate ancestor of the cell within the hierarchical tree.

12. The method of claim 1, further comprising:

maintaining a spatial index comprising multiple hierarchical layers of nodes;

wherein each node corresponds to a cell within a hierarchical tree of cells of geographic data, and is configured to identify a geographic area comprising the cell.

13. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of identifying boundaries of a geographic area comprising a city, the method comprising:

(a) identifying coordinates of multiple cities;

(b) associating with each city a grid of cells of geographic data encompassing the city'"'"'s coordinates;

(c) for each cell associated with a city, identifying a larger replacement cell of geographic data encompassing the cell;

(d) testing for intersection between replacement cells of cells of different cities;

(e) for each cell whose replacement cell does not intersect another replacement cell of another cell of another city, replacing the cell with the replacement cell and associating the replacement cell with the city;

(f) repeating (c)-(e) to replace replacement cells with further replacement cells until;

(1) no cell associated with a city can be replaced without the replacement cell intersecting a replacement cell associated with a different city;

or

(2) said (e) has been performed a threshold number of times;

or

(3) an area covered by cells associated with the city meets a threshold size; and

(g) using said replacement cells to define a boundary of the geographic area;

wherein the method is implemented in a computer system that comprises a processor and a memory.

14. A method of determining boundaries of a geographical area comprising a city, the method comprising:

identifying coordinates of the city;

associating with the city a grid of cells of geographical data, wherein the grid encompasses the city coordinates;

repeatedly expanding each cell associated with the city and associating the expanded cell with the city until;

the expanded cell cannot be expanded without intersecting a cell associated with a different geographical area;

or

said expanding has been performed a threshold number of times; and

defining a boundary of the city using the cells associated with the city;

wherein the method is implemented in a computer system that comprises a processor and a memory.

15. The method of claim 14, further comprising:

(a) discarding the expanded cells;

(b) repeating said identifying, said associating and said repeatedly expanding for one or more cities within the geographic area, including the city; and

(c) defining a boundary of the area using the cells associated with the one or more cities.

16. The method of claim 14, further comprising:

identifying coordinates of one or more additional cities within the geographical area;

associating with each additional city a grid of adjacent cells of geographical data, wherein the grid encompasses the additional city'"'"'s coordinates;

expanding each cell associated with each additional city and associating the expanded cell with the additional city until;

the expanded cell cannot be expanded without intersecting a cell associated with a different geographical area;

or

said expanding has been performed a threshold number of times; and

defining a boundary of the geographical area using the cells associated with the city.

17. The method of claim 14, wherein said defining comprises defining the boundary from a perimeter of cells associated with the city.

18. The method of claim 14, wherein said expanding each cell associated with the city stops when an area encompassed by all cells associated with the city exceeds a threshold size.

19. The method of claim 14, wherein said expanding each cell associated with the city stops when an expanded cell would intersect a void cell.

20. The method of claim 19, wherein a void cell is a cell comprising less than a threshold amount of land geographical data.

21. The method of claim 19, wherein a void cell is a cell comprising a body of water not part of the geographical area.

22. The method of claim 19, wherein a void cell is a cell not associated with any geographical area.

23. The method of claim 14, further comprising, prior to said associating:

(a) subdividing a larger geographical area comprising multiple geographical areas, including the geographical area, into a plurality of level 1 cells of geographical data;

(b) subdividing each said level 1 cell into an equal number of level 2 cells;

(c) repeating said (b) for N−

2 additional levels (N>

2), to subdivide each said level 2 cell into a plurality of level N cells;

wherein said adjacent cells are selected from said level N cells.

24. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of determining boundaries of a geographical area comprising a city, the method comprising:

identifying coordinates of the city;

associating with the city a grid of adjacent cells of geographical data, wherein the grid encompasses the city coordinates;

repeatedly expanding each cell associated with the city and associating the expanded cell with the city until;

the expanded cell cannot be expanded without intersecting a cell associated with a different geographical area;

or

said expanding has been performed a threshold number of times; and

defining a boundary of the city using the cells associated with the city;

wherein the method is implemented in a computer system that comprises a processor and a memory.

25. A system for determining boundaries of a geographic area, comprising:

a spatial index comprising multiple layers of nodes, each node corresponding to a cell of geographic data, wherein each cell at a layer M−

1 comprises multiple layer M cells (M>

1);

a boundary generator configured to;

receive coordinates of a point within the geographic area;

associate with the geographic area a set of layer N cells (N>

2) encompassing said coordinates;

iteratively replace the identified cells with encompassing cells at layer N−

1 until;

an encompassing cell intersects a terminating cell;

or

a threshold number of replacement iterations has been performed; and

identify a boundary of the geographical area from the encompassing cells;

wherein a terminating cell is;

a cell encompassing a cell associated with a different geographic area;

or

a cell encompassing unassigned geographic data.

26. The system of claim 25, further comprising:

a first server configured to serve a map view that intersects the geographic area; and

a second server comprising a set of target areas associated with information to be served with maps intersecting the target areas, wherein the target areas include the geographic area.

27. The system of claim 26, wherein each node of said spatial index comprises identities of target areas encompassing the corresponding cell of geographic data.

28. The system of claim 26, wherein the second server further comprises the information to be served.

29. The system of claim 25, wherein an intersection of the geographic areas of the cells of geographic data corresponding to all nodes of said spatial index comprises the earth'"'"'s surface.