System, method and apparatus for searching geographic area using prioritized spacial order

• US 6,745,115 B1
• Filed: 01/07/2003
• Issued: 06/01/2004
• Est. Priority Date: 01/07/2003
• Status: Active Grant

• Current Assignee: Garmin International, Inc. (Garmin Limited)
• Original Assignee: Garmin Limited
• Inventors: Chen, Susan S., Barber, Clayton E.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/337,598
• Time in Patent Office: 511 Days
• Field of Search: 701/9, 701/10, 701/13, 701/14, 701/15, 701/16, 244/158.R, 244/75.R, 340/945, 340/948
• US Class Current: 701/9
• CPC Class Codes: B64D 45/04 Landing aids; Safety measures to prevent collision with earth's surface
• CPC Class Codes: G01C 23/00 Combined instruments indicating more than one navigational value, e.g. for aircraft; Combined measuring devices for measuring two or more variables of movement, e.g. distance, speed or acceleration
• CPC Class Codes: G01C 5/005 altimeters for aircraft G01C5/02, G01C5/06 take precedence

Abstract

A spatial data search method, system and apparatus for identifying particular data of significance around a reference vector through the spatial data. The method involves determining a reference vector within a spatial region for which spatial data exists, loading a portion of the spatial data including the data around the reference vector into a memory buffer, and searching the spatial data in a prioritized order. The method, system and apparatus have particular utility in searching geographic data for a terrain awareness and warning system (“TAWS”) and display in an aircraft. Embodiments of the present invention provide advantages over existing sequential and radial search methods, significantly reducing the processing and calculations required and providing faster alerts to pilots.

Claims

1. A method of searching data relating to at least one characteristic of a spatial region, the method comprising:

identifying a search vector through the spatial region, the search vector having a starting point, a direction and a length;

storing a portion of the data relating to the spatial region in a memory buffer having memory cells representative of the search vector such that spatial region data corresponding to the search vector is stored in memory cells representative of the search vector; and

searching a portion of the memory buffer cells in a predetermined prioritized order.

2. The method of claim 1, wherein searching comprises searching the memory buffer cells in a non-linear prioritized order.

3. The method of claim 1, wherein searching comprises comparing a value stored in the memory cell with a predetermined search criteria.

4. The method of claim 3, further comprising storing an identity of each memory cell having a value matching the predetermined search criteria in an alert list.

5. The method of claim 4, further comprising providing results of the alert list when a predetermined number of memory cell values meet the predetermined search criteria.

6. The method of claim 1, wherein searching a portion of the memory buffer cells comprises searching a portion less than all of the memory buffer cells and searching each memory buffer cell searched an equal number of times.

7. The method of claim 6, wherein searching each memory bell an equal number of times comprises searching each memory cell once.

8. The method of claim 1, wherein searching comprises searching in alert cycles, each alert cycle comprising a different search vector.

9. The method of claim 8, wherein each alert cycle comprises searching at least one memory cell on the search vector followed by searching at least one memory cell adjacent to the search vector followed by searching at least one unsearched memory cell on the search vector.

10. The method of claim 1, wherein identifying a search vector through the spatial region comprises identifying an aircraft flight path through a geographic region, and storing data relative to elevation values for a portion of the geographic region in the memory cells.

11. The method of claim 10, wherein searching comprises comparing the data relative to an elevation value stored in a memory cell with a projected aircraft safety altitude for the memory cell.

12. The method of claim 11, further comprising storing in an alert list an identity of each memory cell having a data value exceeding the projected aircraft altitude.

13. The method of claim 12, further comprising calculating an alert status for a plurality of entries in the alert list when a predetermined number of memory cell data values exceed respective projected aircraft safety altitudes.

14. The method of claim 13, wherein calculating the alert status comprises determining a travel time for the aircraft to reach the geographic region represented by the memory cell value, determining a first pull-up time for a pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell, and comparing the travel time to a time relative to the first pull-up time.

15. The method of claim 14, wherein calculating the alert status further comprises determining a second pull-up time for the pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell plus a clearance value, and comparing the travel time to a time relative to the second pull-up time.

16. The method of claim 10, wherein searching comprises searching a portion of the memory buffer cells storing information representing the geographic region in a non-linear prioritized order.

17. The method of claim 10, wherein searching comprises searching in alert cycles, each alert cycle comprising a different search vector.

18. The method of claim 17, wherein each alert cycle comprises searching at least one memory cell on the flight path followed by searching at least one memory cell adjacent to the flight path followed by searching at least one unsearched memory cell on the flight path.

19. The method of claim 10, further comprising determining a terrain alert and displaying images on a terrain display, the images representative of terrain and an associated terrain alert level.

20. A terrain awareness and warning system (TAWS) for an aircraft, the TAWS comprising:

a terrain information database configured to store elevation information for a terrain region;

a terrain buffer configured to receive and store elevation information for a portion of the terrain region for an alert cycle;

a look-ahead warning generator configured to receive indications of terrain clearance alerts and communicate the indications by at least one of a visual display and an aural warning; and

a processor coupled to each of the terrain information database, the terrain buffer, and the look-ahead warning generator, the processor configured to receive at least one signal representative of at least an altitude of the aircraft, a position of the aircraft, and a direction of travel of the aircraft, select data representative of elevation values for a portion of the terrain region corresponding to the aircraft position and direction of travel, store the elevation values in the terrain buffer, and search data cells of the terrain buffer in a predetermined prioritized order.

21. The TAWS of claim 20, wherein the processor is further configured to maintain an alert list of each data cell of the terrain buffer for which a projected aircraft safety altitude is less than an elevation value for the cell.

22. The TAWS of claim 21, wherein the processor is further configured to calculate an alert status indicator for each data cell in the alert list when a number of cells in the alert list reaches a predetermined number.

23. The TAWS of claim 20, wherein the processor is further configured to monitor movements of the aircraft and responsively modify the predetermined prioritized order.

24. The TAWS of claim 20, wherein the processor is further configured to provide data to the visual display representing the elevation information for the terrain region in relation to a flying altitude of the aircraft for display in conjunction with the terrain clearance alerts.

25. The TAWS of claim 24, wherein the visual display is configured to display the terrain data in a form that also identifies the terrain clearance alerts.

26. A method of searching geographic data for a terrain awareness warning system, the method comprising a plurality of alert cycles, wherein a first alert cycle of the plurality comprising:

identifying a first search vector for the geographic data based upon at least a first direction of travel and a first location of the aircraft at a first time, the search vector having a first length representing a look-ahead distance;

locating the first location of the aircraft in the geographic data;

copying into a memory buffer having cells, a first subset of the geographic data corresponding to and encompassing cells corresponding to a geographic region through which the search vector extends; and

searching a portion of the memory buffer cells according to a first predetermined prioritized search order.

27. The method of claim 26, wherein searching comprises searching the memory buffer cells in a non-linear prioritized search order.

28. The method of claim 26, wherein a second alert cycle of the plurality comprising:

identifying a second search vector for the geographic data based upon at least a second direction of travel and a second location of the aircraft at a second time;

locating the second location of the aircraft in the geographic data;

copying a second subset of the geographic data corresponding to the second location of the aircraft and second direction of travel for the aircraft into the memory buffer;

searching the portion of the memory buffer cells according to a second predetermined search order.

29. The method of claim 26, wherein the predetermined prioritized search order is a search order predetermined with regard to its relation to the search vector.

30. The method of claim 26, wherein each alert cycle among the plurality searches the memory buffer cells according to at least first and second predetermined prioritized search orders depending upon an external factor.

31. The method of claim 26, wherein searching comprises comparing data relative to an elevation value stored in a memory cell with a projected aircraft safety altitude for the memory cell.

32. The method of claim 31, further comprising storing in an alert list an identity of each memory cell having a data value exceeding the projected aircraft safety altitude.

33. The method of claim 32, further comprising calculating an alert status for each entry in the alert list when a predetermined number of memory cell values exceed the predetermined alert elevation value during the first alert cycle.

34. The method of claim 33, wherein calculating the alert status comprises determining a travel time for the aircraft to reach the geographic region represented by the memory cell value, determining a first pull-up time for a pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell, and comparing the travel time to a time relative to the first pull-up time.

35. The method of claim 34, wherein calculating the alert status further comprises determining a second pull-up time for the pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell plus a clearance value, and comparing the travel time to a time relative to the second pull-up time.

36. The method of claim 35, wherein each alert cycle comprises searching at least one memory cell on the search vector followed by searching at least one memory cell adjacent to the search vector followed by searching at least one unsearched memory cell on the search vector.

37. The method of claim 26, further comprising determining a terrain alert and displaying images on a terrain display, the images representative of terrain and an associated terrain alert level.