System and method for rapid determination of visibility-based terrain properties over broad regions

• US 6,173,067 B1
• Filed: 04/07/1998
• Issued: 01/09/2001
• Est. Priority Date: 04/07/1998
• Status: Expired due to Term

• Current Assignee: The DIRECTV Group, Inc. (AT&T, Inc.)
• Original Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Inventors: Keirsey, David M., Payton, David W.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/061,356
• Time in Patent Office: 1,008 Days
• Field of Search: 382/113, 382/103, 382/106, 382/154, 455/456, 455/457
• US Class Current: 382/106
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A system and method for rapidly obtaining information about the suitability of terrain to meet concealment or visibility objectives, such as might be needed for military planning or for determining placement of relay antennas in a cellular communication system, is disclosed. The disclosed system precomputes heuristic visibility fields for a geographic area, then uses the precomputed heuristic visibility fields to rapidly determine points on a map that will provide the desired characteristics of exposure or concealment in response to a query.

Claims

1. A method for determining and representing the visibility in a first direction of an array of points on a map based on a digital elevation map, the method comprising the steps of:

defining a separate visibility cone associated with each point in said array of points, each visibility cone extending in a second direction, having a number of cells and having an angle less than 180 degrees;

counting, for each point in the array of points, visible cells in said associated visibility cone that are visible;

calculating an array of heuristic visibility numbers having elements corresponding to said points in said array of points, each element of said array of heuristic visibility numbers based on said count of said visible cells in said visibility cone associated with said point corresponding to said element;

representing said visibility of said array of points on said map in said first direction with said array of heuristic visibility numbers; and

storing said array of heuristic visibility numbers in a database.

2. The method of claim 1 wherein, said counting of said visible cells comprises using a ray trace technique.

3. The method of claim 1 wherein, said calculating of said array of heuristic visibility numbers comprises calculating a ratio of said count of said visible cells to said number of cells in each of said visibility cones.

4. The method of claim 1 wherein, said calculating of said array of heuristic visibility numbers comprises using an inverse square function.

11. The method of claim 1, wherein the array of heuristic visibility numbers is a first array of heuristic visibility numbers, the method further comprising the steps of:

defining a separate visibility cone associated with each point in said array of points, each visibility cone extending in a third direction, having a number of cells and having an angle less than 180 degrees;

counting, for each point in the array of points, visible cells in said associated visibility cone that are visible;

calculating a second array of heuristic visibility numbers having elements corresponding to said points in said array of points, each element of said second array of heuristic visibility numbers based on said count of said visible cells in said visibility cone associated with said point corresponding to said element;

representing said visibility of said array of points on said map in said third direction with said second array of heuristic visibility numbers;

storing said second array of heuristic visibility numbers in a database; and

combining said first array of heuristic visibility numbers with said second array of heuristic visibility numbers to determine said visibility in said first direction of said array of points on said map.

12. The method of claim 11, wherein said combining step comprises adding said elements of said first array of heuristic visibility numbers to corresponding elements of said second array of heuristic visibility numbers.

13. The method of claim 11, wherein said combining step comprises multiplying said elements of said first array of heuristic visibility numbers by corresponding elements of said second array of heuristic visibility numbers.

18. The method of claim 1, wherein the first direction is the same as the second direction.

5. A method for analyzing geographical locations based on a query from a user specifying desired terrain characteristics, the method comprising the steps of:

accepting an input specifying desired terrain characteristics in a fist direction from said user;

recalling previously stored terrain characteristic information from a database, said terrain characteristic information comprising an array of heuristic visibility numbers having elements representing a number of visible cells that are visible inside separate visibility cones that extend in a first direction, each visibility cone having an angle less than 180 degrees; and

performing calculations using said previously stored terrain characteristic information, said calculations yielding a set of geographical locations matching said specified desired terrain characteristics in said first direction.

6. The method of claim 5 wherein, said specified desired terrain characteristics comprise visibility and concealment requirements.

7. The method of claim 5 wherein, said previously stored terrain characteristic information comprises a set of heuristic visibility information.

8. The method of claim 6 wherein, said calculations comprise calculations based on said heuristic visibility information.

14. The method of claim 5, wherein the array of heuristic visibility numbers is a first array of heuristic visibility numbers and the accepting step further comprises accepting an input specifying desired terrain characteristics in a second direction, the method further comprising the step of recalling previously stored terrain characteristic information from a database, said previously stored terrain characteristic information comprising a second array of heuristic visibility numbers having elements representing a number of visible cells that are visible inside a visibility cone having an angle less than 180 degrees, wherein said step of performing calculations comprises combining said first array of heuristic visibility numbers and said second array of heuristic visibility numbers to yield a set of geographical locations matching said specified desired terrain characteristics in said first and second directions.

15. The method of claim 14, wherein said step of performing calculations comprises adding said elements of said first array of heuristic visibility numbers to corresponding elements of said second array of heuristic visibility numbers.

16. The method of claim 14, wherein said step of performing calculations comprises multiplying said elements of said first array of heuristic visibility numbers by corresponding elements of said second array of heuristic visibility numbers.

9. An apparatus for determining a visibility in a first direction of an array of points on a map, said apparatus comprising:

a data processor; and

a database;

said data processor accepting a set of digital elevation map information and a visibility query;

said digital elevation map information comprising a number of cells representative of elevations;

said data processor programmed to determine said visibility of said point on said map by performing the steps of;

(1) defining a separate visibility cone associated with each point in said array of points, each visibility cone extending in a second direction, having a number of cells and having an angle less than 180 degrees;

(2) counting, for each point in the array of points, visible cells in said associated visibility cone that are visible;

(3) calculating an array of heuristic visibility numbers having elements corresponding to said points in said array of points, each element of said array of heuristic visibility numbers based on said count of said visible cells in said visibility cone associated with said point corresponding to said element;

(4) representing the visibility of said array of points on said map in said first direction with said array of heuristic visibility numbers; and

(5) storing said array of heuristic visibility numbers in said database.

10. The data processor of claim 9 further programmed to perform the steps of:

accepting an input specifying desired-terrain characteristics from a user;

recalling a previously stored array of heuristic visibility numbers; and

performing calculations using said array of heuristic visibility numbers, said calculations yielding a set of geographical locations matching said desired terrain characteristics.

17. The data processor of claim 10, wherein said step of performing calculations comprises adding a first heuristic visibility number to a second heuristic visibility number.