Method for converting a digital elevation database to a polygon database

• US 5,974,423 A
• Filed: 03/09/1998
• Issued: 10/26/1999
• Est. Priority Date: 03/09/1998
• Status: Expired due to Fees

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Jed Margolin
• Inventors: Margolin, Jed
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/036,680
• Time in Patent Office: 596 Days
• Field of Search: 707/1, 707/6, 707/104, 701/120, 701/207, 701/213, 340/945, 340/961, 340/964, 702/150, 169/53, 455/504, 455/671, 345/419, 345/421, 345/142, 345/420, 345/422, 345/423, 345/502, 345/503, 345/522, 434/12, 434/38, 342/195, 382/180
• US Class Current: 345/606
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A Digital Elevation Database is converted to a Polygon Database by creating square cells of varying sizes, starting with a minimum size cell. A center elevation point in the cell is used to form four three-dimensional triangles. The points within the cell are then tested against the flatness criteria. If the cell meets the flatness criteria it is expanded and tested again. This goes on until the cell fails the flatness criteria or a maximum specified cell size is reached. The cell parameters for the last trial cell meeting the flatness criteria or the maximum specified cell size are then entered into the polygon database. The points in the cell are then removed from the elevation database and the process starts over until all the points have been processed. In a second embodiment the procedure starts with a maximum size cell and the cell size is reduced until the cell meets the flatness criteria.

Claims

1. A method for converting a digital elevation database to a polygon database comprising the computer generated steps of:

a) providing a selected active elevation point in said digital elevation database, whereby said digital elevation database comprises a plurality of elevation points, each elevation point representing an elevation of a point on a terrain;

b) defining a square cell defined by a center elevation point and four corner elevation points, whereby said selected active elevation point is selected as said center elevation point, and said four corner elevation points are selected to produce a square cell having a minimum size;

c) using said center elevation point and said four corner elevation points to produce four three dimensional triangles whereby each three dimensional triangle is formed from said center elevation point and two adjacent said corner elevation points forming a side of said square cell;

d) determining if said four three dimensional triangles meet a flatness criteria;

whereas said flatness criteria is defined such that no point in said four three dimensional triangles may be greater than a first distance above the corresponding point in said digital elevation database and no point in said four three dimensional triangles may be greater than a second distance below the corresponding point in said digital elevation database;

e) if said four three dimensional triangles meet said flatness criteria and said square cell has not exceeded a maximum specified size, performing the steps of;

(i) expanding the size of said square cell, thereby selecting new said four corner elevation points, while retaining said center elevation point;

(ii) repeating step c) through step e);

otherwise, performing the steps of;

(i) storing said square cell in said polygon database;

(ii) marking as inactive the points in said digital elevation database corresponding to the area covered by said square cell.

2. The method of claim 1 wherein the highest active point in said digital elevation database is selected as said selected active elevation point.

3. The method of claim 1 wherein the lowest active point in said digital elevation database is selected as said selected active elevation point.

4. The method of claim 1 wherein step a) through step e) are repeated until each elevation point in said digital elevation database is processed.

5. The method of claim 1 wherein said square cell having a minimum size that fails said flatness criteria is tagged as having failed said flatness criteria before being stored in said polygon database.

6. The method of claim 5 wherein said center elevation point of said square cell having a minimum size that fails said flatness criteria is selected to be the highest elevation of the points in said digital elevation database corresponding to the area covered by said square cell having a minimum size.

7. The method of claim 1 wherein the elevation points in said four three dimensional triangles are calculated by performing the steps of:

a) reading the elevations of said center elevation point and said four corner elevation points;

b) calculating the elevations of the remaining points in said square cell by performing the steps of;

(i) using said four corner elevation points to interpolate the elevations of the remaining points on the left edge, right edge, top edge, and bottom edge of said square cell;

(ii) using said center elevation point and said four corner elevation points to interpolate the elevations of the remaining points on the four diagonal lines formed from said center elevation point to each of said four corner elevation points of said square cell;

(iii) using the elevations of said four diagonal lines to interpolate the elevations of the remaining points in each one of said four three dimensional triangles.

8. The method of claim 1 wherein said flatness criteria may be different for different altitudes above ground level.

9. The method of claim 1 wherein said polygon database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a first said flatness criteria and a second geographic block may have a second said flatness criteria.

10. A method for converting a digital elevation database to a polygon database comprising the computer generated steps of:

a) providing a selected active elevation point in said digital elevation database, whereby said digital elevation database comprises a plurality of elevation points, each elevation point representing an elevation of a point on a terrain;

b) defining a square cell defined by a center elevation point and four corner elevation points, whereby said selected active elevation point is selected as said center elevation point, and said four corner elevation points are selected to produce a square cell having a predetermined maximum size;

c) using said center elevation point and said four corner elevation points to produce four three dimensional triangles whereby each three dimensional triangle is formed from said center elevation point and two adjacent said corner elevation points forming a side of said square cell;

d) determining if said four three dimensional triangles meet a flatness criteria;

whereas said flatness criteria is defined such that no point in said four three dimensional triangles may be greater than a first distance above the corresponding point in said digital elevation database and no point in said four three dimensional triangles may be greater than a second distance below the corresponding point in said digital elevation database;

e) if said four three dimensional triangles fail to meet said flatness criteria, performing the steps of;

(i) reducing the size of said square cell, thereby selecting new said four corner elevation points, while retaining said center elevation point;

(ii) repeating step c) through step e);

otherwise, performing the steps of;

(i) storing said square cell in said polygon database;

(ii) marking as inactive the points in said digital elevation database corresponding to the area covered by said square cell.

11. The method of claim 10 wherein the highest active point in said digital elevation database is selected as said selected active elevation point.

12. The method of claim 10 wherein the lowest active point in said digital elevation database is selected as said selected active elevation point.

13. The method of claim 10 wherein step a) through step e) are repeated until each elevation point in said digital elevation database is processed.

14. The method of claim 10 wherein a square cell having a minimum size that fails said flatness criteria is tagged as having failed said flatness criteria before being stored in said polygon database.

15. The method of claim 14 wherein said center elevation point of said square cell having a minimum size that fails said flatness criteria is selected to be the highest elevation of the points in said digital elevation database corresponding to the area covered by said square cell having a minimum size.

16. The method of claim 10 wherein the elevation points in said four three dimensional triangles are calculated by performing the steps of:

a) reading the elevations of said center elevation point and said four corner elevation points;

b) calculating the elevations of the remaining points in said square cell by performing the steps of;

(i) using said four corner elevation points to interpolate the elevations of the remaining points on the left edge, right edge, top edge, and bottom edge of said square cell;

(ii) using said center elevation point and said four corner elevation points to interpolate the elevations of the remaining points on the four diagonal lines formed from said center elevation point to each of said four corner elevation points of said square cell;

(iii) using the elevations of said four diagonal lines to interpolate the elevations of the remaining points in each one of said four three dimensional triangles.

17. The method of claim 10 wherein said flatness criteria may be different for different altitudes above ground level.

18. The method of claim 10 wherein said polygon database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a first said flatness criteria and a second geographic block may have a second said flatness criteria.

19. A method for interpolating the edge points and interior points of a square cell defined by a center elevation point and four corner elevation points, whereby said center elevation point and said four corner elevation points form four three dimensional triangles, whereby each three dimensional triangle is formed from said center elevation point and two adjacent said corner elevation points forming a side of said square cell, comprising the computer generated steps of:

a) using said four corner elevation points to interpolate the elevations of the remaining points on the left edge, right edge, top edge, and bottom edge of said square cell;

b) using said center elevation point and said four corner elevation points to interpolate the elevations of the remaining points on the four diagonal lines formed from said center elevation point to each one of said four corner elevation points of said square cell;

c) using the elevations of said four diagonal lines to interpolate the elevations of the remaining points in each one of said four three dimensional triangles.