Grid retaining irregular network in 3D

Abstract

Systems and methods are provided for compression of 3 dimensional (3D) geophysical (e.g., air temp, water temp, wind, current, humidity, salinity, etc.) datasets that contain regions of NaNs (IEEE standard representation for Not a Number) that represent land, i.e. geographic positions that do not have valid data. Embodiments of the present disclosure allow constraint of the error magnitude by a user specified threshold, where compression and error are inherent tradeoffs.

What is claimed is: 
     
       1. A method for compressing data, the method comprising:
 forming, using a compressor device, a mesh based on the data, wherein the mesh comprises a plurality of triangles; 
 tessellating, using the compressor device, the plurality of triangles to form a right-triangulated irregular network (RTIN) structure being capable of being fully reduced to two triangles, the RTIN structure including a plurality of points and a plurality of edges; 
 compressing, using the compressor device, the data using the RTIN structure; 
 producing, using the compressor device, a unique index number for every point within the RTIN structure; 
 determining, using the compressor device, whether a difference between each point in the RTIN structure and a corresponding point in the data exceeds an error threshold; and 
 for each point in the RTIN structure, if the difference between the point and the corresponding point in the data exceeds the error threshold, record the computed index value of the point in the RTIN structure and the value of that point in the data in a keep list. 
 
     
     
       2. The method of  claim 1 , wherein the mesh is a Delaunay mesh. 
     
     
       3. The method of  claim 1 , further comprising:
 receiving a query for a value of a queried point in the RTIN structure; 
 determining whether an index value of the queried point is in the keep list; and 
 returning a keep list value of the queried point in the keep list if the index value of the queried point is in the keep list. 
 
     
     
       4. The method of  claim 3 , further comprising:
 returning a value of the queried point in the RTIN structure if the index value of the queried point is [M] not in the keep list. 
 
     
     
       5. The method of  claim 1 , wherein compressing the data further comprises:
 (a) incrementing an iteration number; 
 (b) selecting a first subset of points from the plurality of points based on angles that edges of the plurality of edges form with the each of the plurality of points; 
 (c) for each of the points in the first subset, selecting one of the plurality of edges for deletion evaluation based on the iteration number and the selected point, the selected edge having an opposing edge of opposite orientation from the selected edge; 
 (d) locating a second subset of the plurality of points, the second subset including the points of the plurality of points along the selected edge; 
 (e) for each of the points in the first subset, removing the selected point and the opposing edge if the points of the second subset meet the pre-selected criteria; 
 (f) for each of the points in the first subset not removed in (e), marking the not-removed points as not available to be selected in (b); and 
 (g) repeating (a) through (f) until no points are found in (b). 
 
     
     
       6. The method of  claim 5 , further comprising:
 prior to removing the selected point:
 determining a first resulting interpolated length along an axis that will remain after the selected point is deleted, 
 determining whether a first difference between the first resulting interpolated length and a first corresponding length in the mesh exceeds the error threshold, 
 determining a second resulting interpolated length along an axis that will be removed after the selected point is deleted, 
 determining whether a second difference between the second resulting interpolated length and a second corresponding length in the mesh exceeds the error threshold, and 
 removing the point if neither the first difference nor the second difference exceeds the error threshold. 
 
 
     
     
       7. The method of  claim 6 , further comprising:
 determining that the point should not be removed if the first difference or the second difference exceeds the error threshold. 
 
     
     
       8. The method of  claim 7 , further comprising:
 if the selected point is not removed in (e):
 determining whether each point adjacent to the selected point corresponds to a not a number (NaN) value, and 
 removing the selected point if each point adjacent to the selected point corresponds to a not a number (NaN) value and the selected point corresponds to a NaN value. 
 
 
     
     
       9. The method of  claim 1 , further comprising:
 replacing not a number (NaN) values in the data with a mean value for a row containing the NaN value. 
 
     
     
       10. The method of  claim 1 , further comprising:
 replacing not a number (NaN) values in the data with a mean value for a layer containing the NaN value. 
 
     
     
       11. A device for compressing data, the device comprising:
 a memory storing data to be compressed; and 
 a compressor device configured to:
 form a mesh based on the data, wherein the mesh comprises a plurality of triangles, 
 tessellate the plurality of triangles to form a right-triangulated irregular network (RTIN) structure being capable of being fully reduced to two triangles, the RTIN structure including a plurality of points and a plurality of edges, 
 compress the data using the RTIN structure, 
 produce a unique index number for every point within the RTIN structure, 
 determine whether a difference between each point in the RTIN structure and a corresponding point in the data exceeds an error threshold, and 
 for each point in the RTIN structure, if the difference between the point and the corresponding point in the data exceeds the error threshold, record the computed index value of the point in the RTIN structure and the value of that point in the data in a keep list. 
 
 
     
     
       12. The device of  claim 11 , wherein the compressor device is further configured to:
 receive a query for a value of a queried point in the RTIN structure; 
 determine whether an index value of the queried point is in the keep list; and 
 return a keep list value of the queried point in the keep list if the index value of the queried point is in the keep list. 
 
     
     
       13. The device of  claim 11 , wherein the compressor device is further configured to:
 (a) increment an iteration number; 
 (b) select a first subset of points from the plurality of points based on angles that edges of the plurality of edges form with the each of the plurality of points; 
 (c) for each of the points in the first subset, select one of the plurality of edges for deletion evaluation based on the iteration number and the selected point, the selected edge having an opposing edge of opposite orientation from the selected edge; 
 (d) locate a second subset of the plurality of points, the second subset including the points of the plurality of points along the selected edge; 
 (e) for each of the points in the first subset, remove the selected point and the opposing edge if the points of the second subset meet the pre-selected criteria; 
 (f) for each of the points in the first subset not removed in (e), mark the not-removed points as not available to be selected in (b); and 
 (g) repeat (a) through (f) until no points are found in (b). 
 
     
     
       14. The device of  claim 13 , wherein the compressor device is further configured to:
 prior to removing the selected point:
 determine a first resulting interpolated length along an axis that will remain after the selected point is deleted, 
 determine whether a first difference between the first resulting interpolated length and a first corresponding length in the mesh exceeds the error threshold, 
 determine a second resulting interpolated length along an axis that will be removed after the selected point is deleted, 
 determine whether a second difference between the second resulting interpolated length and a second corresponding length in the mesh exceeds the error threshold, and 
 remove the point if neither the first difference nor the second difference exceeds the error threshold. 
 
 
     
     
       15. The device of  claim 14 , wherein the compressor device is further configured to:
 determine that the point should not be removed if the first difference or the second difference exceeds the error threshold. 
 
     
     
       16. The device of  claim 13 , wherein the compressor device is further configured to:
 if the selected point is not removed in (e):
 determine whether each point adjacent to the selected point corresponds to a not a number (NaN) value, and 
 remove the selected point if each point adjacent to the selected point corresponds to a not a number (NaN) value and the selected point corresponds to a NaN value. 
 
 
     
     
       17. The device of  claim 11 , wherein the compressor device is further configured to:
 replace not a number (NaN) values in the data with a mean value for a row containing the NaN value. 
 
     
     
       18. The device of  claim 11 , wherein the compressor device is further configured to:
 replace not a number (NaN) values in the data with a mean value for a layer containing the NaN value. 
 
     
     
       19. A method for compressing data, the method comprising:
 forming, using a compressor device, a mesh based on the data, wherein the mesh comprises a plurality of triangles; 
 tessellating, using the compressor device, the plurality of triangles to form a right-triangulated irregular network (RTIN) structure being capable of being fully reduced to two triangles, the RTIN structure including a plurality of points and a plurality of edges; 
 compressing, using the compressor device, the data using the RTIN structure; 
 producing, using the compressor device, a unique index number for every point within the RTIN structure; 
 determining, using the compressor device, whether a difference between each point in the RTIN structure and a corresponding point in the data exceeds an error threshold; 
 for each point in the RTIN structure, if the difference between the point and the corresponding point in the data exceeds the error threshold, record the computed index value of the point in the RTIN structure and the value of that point in the data in a keep list; 
 receiving a query for a value of a queried point in the RTIN structure; 
 determining whether an index value of the queried point is in the keep list; 
 returning a keep list value of the queried point in the keep list if the index value of the queried point is in the keep list; and 
 returning a value of the queried point in the RTIN structure if the index value of the queried point is not in the keep list. 
 
     
     
       20. The method of  claim 19 , wherein compressing the data further comprises:
 (a) incrementing an iteration number; 
 (b) selecting a first subset of points from the plurality of points based on angles that edges of the plurality of edges form with the each of the plurality of points; 
 (c) for each of the points in the first subset, selecting one of the plurality of edges for deletion evaluation based on the iteration number and the selected point, the selected edge having an opposing edge of opposite orientation from the selected edge; 
 (d) locating a second subset of the plurality of points, the second subset including the points of the plurality of points along the selected edge; 
 (e) for each of the points in the first subset, removing the selected point and the opposing edge if the points of the second subset meet the pre-selected criteria; 
 (f) for each of the points in the first subset not removed in (e), marking the not-removed points as not available to be selected in (b); and 
 (g) repeating (a) through (f) until no points are found in (b).