Spatial data object indexing engine

• US 6,700,574 B1
• Filed: 10/29/1999
• Issued: 03/02/2004
• Est. Priority Date: 10/29/1999
• Status: Expired due to Term

• Current Assignee: Trapeze Its USA LLC
• Original Assignee: Siemens Transportation Systems, Inc. (Siemens AG)
• Inventors: Song, Yiping
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US09/430,447
• Time in Patent Office: 1,586 Days
• Field of Search: 345/418, 345/419, 345/420, 345/421, 345/423, 707/5, 707/6, 707/3, 707/2, 707/100, 706/20, 378/901
• US Class Current: 345/423
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A method of indexing spatial object data comprises dividing space that contains objects based on the clustering of the objects within the space. A computer readable medium contains computer executable instructions. The instructions cause the computer to divide a space containing spatial objects based on clustering of the objects within the space. A method of searching spatial object data includes utilizing spatial object data that has been gridded based upon clustering of the spatial objects. The grids are then recursively checked to see if they cover a range of interest. If the grids overlap the range of interest objects within the grids are checked to see if they satisfy a search criterion.

Claims

1. A method of indexing spatial object data, comprising:

utilizing spatial object data which characterizes objects within a defined space;

determining a clustering limit equal to a maximum number of objects and based on at least one of memory size, screen size, screen resolution, viewing scale, and the type of application;

dividing the space based upon clustering of the objects;

identifying if the clustering limit has been reached for a particular cluster of objects.

2. The method of claim 1, further comprising:

encompassing the space with a level one grid;

dividing the level one grid into second generation grids if indicated by a comparison between the clustering in the level one grid and the clustering limit;

recursively dividing at least one of the second generation grids into subsequent generation grids if indicated by a comparison between objects in at least one of the second or subsequent generation grids and the clustering limit.

3. The method of claim 2 wherein the comparison is between objects in each of the second and subsequent generation grids and the clustering limit.

4. The method of claim 3 wherein grids are divided into 2″

equal sized subsequent generation grids, wherein n is an integer.

5. The method of claim 4 wherein n is the largest number of spatial dimensions of the spatial objects.

6. The method of claim 5 wherein n equals 2 or 3.

7. A computer readable medium having computer executable instructions for causing a computer to perform the steps of:

utilizing spatial object data that characterizes objects within a defined space;

dividing the space based upon clustering of the objects;

indexing the objects of each cluster into different layers, each layer being related to at least one object type;

determining a clustering limit equal to a maximum number of objects and based on hardware limitations of the computer and associated display; and

identifying if the clustering limit has been reached for a particular cluster of objects.

8. The computer readable medium of claim 7, having further computer executable instructions for causing the computer to perform the steps of:

setting, or receiving as input, a clustering limit;

encompassing the space with a grid;

recursively dividing the grid into subsequent generation grids if indicated by a comparison between objects in at least one subsequent generation grid and the clustering limit.

9. The computer readable medium of claim 8 wherein the comparison is between objects in each of the subsequent generation grids and the clustering limit.

10. The computer readable medium of claim 9 wherein parent grids are divided into 2″

equal sized subsequent generation grids with n being the largest number of spatial dimensions of the spatial objects.

11. The computer readable medium of claim 10 wherein n equals two.

12. The computer readable medium of claim 10 wherein n equals three.

13. The computer readable medium of claim 7 in combination with a computer, the computer having a memory and a processor.

14. The computer readable medium of claim 8 in combination with a computer, the computer having a memory and a processor.

15. A method of searching through spatial object data, comprising:

utilizing spatial object data that has been indexed in grids based upon clustering of the spatial objects according to a clustering limit equal to a maximum number of objects; and

recursively determining if the grids cover a range of interest, and if so, checking objects within the grids to see if they satisfy a search criterion.

16. The method of claim 15 wherein the search returns objects satisfying the search criterion.

17. The method of claim 16 wherein the search returns are displayed on a graphical display.

18. The method of claim 17 wherein the graphical display is a GPS screen.

19. The method of claim 18 wherein the GPS screen also displays a current location of a GPS device.

20. The method of claim 17 wherein the graphical display is a video monitor.

21. A computer readable medium having computer executable instructions for causing a computer to perform the steps of:

utilizing spatial object data indexed in grids based on clustering of spatial object data, recursively determining if the grids cover a range of interest, and if so checking objects within the grids to see if they satisfy a search criterion;

indexing the objects of each cluster into different layers, each layer being related to at least one object type;

determining a clustering limit equal to a maximum number of objects and based on hardware limitations of the computer and associated display; and

identifying if the clustering limit has been reached for a particular cluster of objects.

22. The computer readable medium of claim 21 in combination with a computer, said computer having a memory, a processor, and a display.

23. The computer readable medium of claim 22 in further combination with a Global Positioning Device.

24. The computer readable medium of claim 23 in further combination with a vehicle.

25. A vehicle comprising:

a vehicle;

a computer readable medium having computer executable instructions for causing a computer to perform the steps of utilizing spatial object data indexed in grids based on clustering of spatial object data, recursively determining if the grids cover a range of interest, and, if so, checking objects within the grids to see if they satisfy a search criterion, indexing the objects of each cluster into different layers, each layer being related to at least one object type, determining a clustering limit equal to a maximum number of objects and based on hardware limitations of the computer and associated display, and identifying if the clustering limit has been reached for a particular cluster of objects;

spatial object data indexed in grids based on clustering of spatial object data;

a computer having memory and processor;

a global positioning system device; and

a display adapted to indicate position.

26. The vehicle of claim 25, further comprising,

a route manager.