Go to content Go to navigation and search

Home

Current Oracle Spatial Blog Articles


Search

Browse

RSS / Atom

Email me

textpattern

Creative Commons License
All Blog Articles, Data Models and Free Source Code by Simon Greener, The SpatialDB Advisor is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Application of Delaunay Triangulation and Inverse Distance Weighting (IDW) in Oracle for Soils Interpolation

Monday March 19 2012 at 11:01

Keywordsdelaunay inverse distance weight idw oracle sdo_geometry grid cell interpolation
Summary

This article shows how the ability to create vector Delaunay cells and grids inside a database can be applied to solving real world problems. An Inverse Distance Weight algorithm is also used along with 3×3 cell “smoothing” of interpolated values to reach a final result.

The need to be able to create and use Delaunay triangles (or voronoi diagrams) inside a database is something not often heard. In addition, neither is Z interpolation of grid cell values using Delaunay triangles in consort with an Inverse Distance Weighted (IDW) algorithm.

“Why would you want to?” is a common cry.

And, for many years I would have agreed with you but recently two things intersected in a most unexpected way.

1. SC4O API Project

In the SC4O project, I decided to expose JTS’s ability to create Delaunay triangles (and Voronoi cells) from a set of input vertices (I have seen talk of the need for this in the PostGIS discussion list but no solution, integrated into the PostGIS API is yet available). I have also exposed the ability to interpolate Z values from a Delaunay triangle. These exposed functions are:

  1. define defaultSchema='&1'
  2. ...
  3. CREATE OR REPLACE package SC4O
  4. AUTHID CURRENT_USER
  5. AS
  6. ...
  7.   /**
  8.   * ST_DelaunayTriangles
  9.   * Method for creating a delaunay triangulation from a geometry input (eg multipoints)
  10.   *
  11.   * @param p_geometry    : mdsys.sdo_geometry : Single sdo_geometry object from whose vertices the delaunay triangles will be build.
  12.   * @param p_tolerance   : number             : Snapping tolerance which will be used to improved the robustness of the triangulation computation.
  13.   * @param p_precision   : Number             : number of decimal places of precision when comparing ordinates.
  14.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  15.   * @history Simon Greener, February 2012, Original Coding
  16.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  17.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  18.   */
  19.   FUNCTION ST_DelaunayTriangles(p_geometry  IN mdsys.sdo_geometry,
  20.                                 p_tolerance IN NUMBER,
  21.                                 p_precision IN NUMBER)
  22.     RETURN mdsys.sdo_geometry
  23.            Deterministic;
  24. .
  25.  /**
  26.   * ST_DelaunayTriangles
  27.   * Method for creating a delaunay triangulation from a geometry input (eg multipoints)
  28.   *
  29.   * @param p_resultSet   : Ref Cursor : Selection of sdo_geometry objects from whose vertices the Delaunay Triangles will be built
  30.   * @param p_tolerance   : number     : Snapping tolerance which will be used to improved the robustness of the triangulation computation.
  31.   * @param p_precision   : Number     : number of decimal places of precision when comparing ordinates.
  32.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  33.   * @history Simon Greener, February 2012, Original Coding
  34.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  35.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  36.   */
  37.   FUNCTION ST_DelaunayTriangles(p_resultSet IN &&defaultSchema..SC4O.refcur_t,
  38.                                 p_tolerance IN NUMBER,
  39.                                 p_precision IN NUMBER)
  40.     RETURN mdsys.sdo_geometry
  41.            Deterministic;
  42. .
  43.  /**
  44.   * ST_DelaunayTriangles
  45.   * Method for creating a delaunay triangulation from a geometry input (eg multipoints)
  46.   *
  47.   * @param p_geomset     : sdo_geometry_array : Array of sdo_geometry objects from whose vertices the delaunay triangles will be build.
  48.   * @param p_tolerance   : number             : Snapping tolerance which will be used to improved the robustness of the triangulation computation.
  49.   * @param p_precision   : Number             : number of decimal places of precision when comparing ordinates.
  50.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  51.   * @history Simon Greener, February 2012, Original Coding
  52.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  53.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  54.   */
  55.   FUNCTION ST_DelaunayTriangles(p_geomset   IN mdsys.sdo_geometry_array,
  56.                                 p_tolerance IN NUMBER,
  57.                                 p_precision IN NUMBER)
  58.     RETURN mdsys.sdo_geometry
  59.            Deterministic;
  60. .
  61.   /**
  62.   * ST_Voronoi
  63.   * Method for creating a Voronoi diagram from a geometry input (eg multipoints)
  64.   *
  65.   * @param p_geometry    : mdsys.sdo_geometry : Single geometry containing source points from whom the voronoi will be built.
  66.   * @param p_tolerance   : number             : Snapping tolerance which will be used to improved the robustness of the computation.
  67.   * @param p_precision   : Number             : number of decimal places of precision when comparing ordinates.
  68.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  69.   * @history Simon Greener, February 2012, Original Coding
  70.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  71.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  72.   */
  73.   FUNCTION ST_Voronoi(p_geometry  IN mdsys.sdo_geometry,
  74.                       p_tolerance IN NUMBER,
  75.                       p_precision IN NUMBER)
  76.     RETURN mdsys.sdo_geometry
  77.            Deterministic;
  78. .          
  79.  /**
  80.   * ST_Voronoi
  81.   * Method for creating a Voronoi diagram from a selection of geometry objects.
  82.   *
  83.   * @param p_resultSet   : Ref Cursor : Selection (cursor) of sdo_geometry objects from whose vertices the voronoi will be built.
  84.   * @param p_tolerance   : number     : Snapping tolerance which will be used to improved the robustness of the triangulation computation.
  85.   * @param p_precision   : Number     : number of decimal places of precision when comparing ordinates.
  86.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  87.   * @history Simon Greener, February 2012, Original Coding
  88.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  89.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  90.   */
  91.   FUNCTION ST_Voronoi(p_resultSet IN &&defaultSchema..SC4O.refcur_t,
  92.                       p_tolerance IN NUMBER,
  93.                       p_precision IN NUMBER)
  94.     RETURN mdsys.sdo_geometry
  95.            Deterministic;
  96. .
  97.  /**
  98.   * ST_Voronoi
  99.   * Method for creating a Voronoi diagram from an array of geometry objects.
  100.   *
  101.   * @param p_geomset     : sdo_geometry_array : Array of sdo_geometry objects from whose points the voronoi will be built.
  102.   * @param p_tolerance   : number             : Snapping tolerance which will be used to improved the robustness of the triangulation computation.
  103.   * @param p_precision   : Number             : number of decimal places of precision when comparing ordinates.
  104.   * @return SDO_GEOMETRY : Collection of Polygon geometries.
  105.   * @history Simon Greener, February 2012, Original Coding
  106.   * @copyright  : Licensed under a Creative Commons Attribution-Share Alike 2.5 Australia License.
  107.   *               http://creativecommons.org/licenses/by-sa/2.5/au/
  108.   */
  109.   FUNCTION ST_Voronoi(p_geomset   IN mdsys.sdo_geometry_array,
  110.                       p_tolerance IN NUMBER,
  111.                       p_precision IN NUMBER)
  112.     RETURN mdsys.sdo_geometry
  113.            Deterministic;
  114. ...
  115.    /**
  116.     * ST_InterpolateZ
  117.     * @param p_point : mdsys.sdo_geometry : Point for which Z ordinate's value is to be computed
  118.     * @param p_geom1 : mdsys.sdo_geometry : First corner geometry 3D point
  119.     * @param p_geom2 : mdsys.sdo_geometry : Second corner geometry 3D point
  120.     * @param p_geom3 : mdsys.sdo_geometry : Third corner geometry 3D point
  121.     * @return Number : Result of Interpolation
  122.     * @throws SQLException
  123.     * @history Simon Greener, March 2012, Original Coding
  124.     */
  125.    FUNCTION ST_InterpolateZ(p_point IN mdsys.sdo_geometry,
  126.                             p_geom1 IN mdsys.sdo_geometry,
  127.                             p_geom2 IN mdsys.sdo_geometry,
  128.                             p_geom3 IN mdsys.sdo_geometry)
  129.     RETURN NUMBER Deterministic;
  130. .
  131.    /**
  132.      * ST_InterpolateZ
  133.      * @param _point         : STRUCT : Point for which Z ordinate's value is to be computed
  134.      * @param _facet         : STRUCT : 3 vertex triangular polygon
  135.      * @return double        : Result of Interpolation
  136.      * @throws SQLException
  137.      * @history Simon Greener, March 2012, Original Coding
  138.      */
  139.    FUNCTION ST_InterpolateZ(p_point IN mdsys.sdo_geometry,
  140.                             p_facet IN mdsys.sdo_geometry)
  141.     RETURN mdsys.sdo_geometry Deterministic;
  142. ...
  143. END SC4O;

An example of some sample points being turned into a set of Delaunay triangles can be seen here:

2. Customer Question

Someone (now a customer) contacted me asking if I could help build a set of tools inside PostgeSQL/PostGIS for the interpolation/extrapolation of observed values at regular sample points throughout agricultural fields.

The reason the customer contacted me is that he had seen my articles on gridding vector polygons in PostGIS and wondered if this gridding could be extended to include interpolation to code each created grid cell with a value calculated from a set of sample points.

The field, and values observed at each sample point (I only include 4 out of all the variables: Potassium, Phosphorus, Ph and Sodium) are shown in the following diagram.

Bringing both Together

Having thought about it I first looked at the new ST_Raster capabilities of PostGIS 2.0. It has enormous promise (I could create the raster, assign the sample point values the associated cell but…) except for one thing: there is no ability to do any interpolation in the current system through which I could take the limited sample point values and compute and assign values for the other grid cells. It may be my lack of ability with raster processing (likely) but looking at ST_Raster’s ST_MapAlgebraFctNgb didn’t convince me that it would help with the interpolation: I kept coming back to the vector nature of the problem space.

To solve the problem I first needed to (Oracle first, later PostGIS).

  1. Loaded field border polygons into a single Oracle table;
  2. Loaded sample points and P, K etc values (as attributes) into a single Oracle table;
  3. Exposed and loaded the JTS Delaunay Java into the database and created a PL/SQL wrapper over it;
  4. Exposed and loaded JTS’s Triangle.interpolateZ(geometry) into the database and created a PL/SQL wrapper over it (geometry can be a single point or a multipoint object);
  5. Modified my TESSELATE.RegularGrid() PL/SQL function to return simple points instead of/or along with an optimised rectangle that describes a single grid.

Then, to solve the problem (via SQL) I did the following:

  1. Created Delaunay triangles from the sample points with the Z ordinate being the measured value (eg K);
  2. Created grid cells that cover the field border polygons;
  3. Used JTS’s InterpolateZ to calculate and assign a grid cell value (eg K) to each grid cell that falls within or on a Delaunay triangle;
  4. Used an Inverse Distance Weighted (IDW) algorithm (pure SQL sum/count group by) to assign a variable value to each grid cell that falls outside the Delaunay triangles but using the nearest grid cell values assigned in the previous step;
  5. Finally, “smoothed” the grid by applying a 3×3 window over the now populated grid cells.

All the above was done using vector processing.

The following 4 images show the result of interpolating and assigning the Potassium (K), Phosphorus (P), Ph and Sodium (Na) observed values across the whole sampled areas.

Potassim Ph Phosphorus Sodium

The following query gives one an idea of the number of (10×10 meter) cells created.

  1. SELECT CASE WHEN GROUPING(triangle) = 1
  2.             THEN 'Total'
  3.             WHEN triangle = 'Y'
  4.             THEN 'Inside Delaunay - InterpolateZ'
  5.             ELSE 'Outside Delaunay - IDW'
  6.          END AS CellReport,
  7.        COUNT(*),
  8.        SUM(sdo_geom.sdo_Area(cell,0.005)) AS sq_m,
  9.        MIN(smoothed_K) AS iMin,
  10.        MAX(smoothed_K) AS iMax
  11.   FROM GIS.field_iterp_k
  12.  GROUP BY rollup(triangle);
  13. -- Results
  14. CELLREPORT                     COUNT(*) SQ_M    IMIN  IMAX                  
  15. ------------------------------ -------- ------- ----- -----
  16. Outside Delaunay - IDW         3579     357900  227.8 399.1                  
  17. Inside Delaunay - InterpolateZ 6637     663700  214.6 397.8                  
  18. Total                          10216    1021600 214.6 399.1

This sort of processing can be executed at any one of three levels in a solutions architecture: data, application, client.

The customer is currently doing this processing using a collection of open source software from a variety of projects glued together via a scripting language.

When the ability to do this processing is available at the data tier (ie inside the database) then what we see is something that tightly links the creation of source data to associated computed data. Databases offer a variety of mechanisms for tightly integrating the two. For example, the creation of new field (polygon) and sample data can drive, automatically, the creation of the derived data either via database triggers (probably linked to an asynchronous script) or through technologies like materialized views. Thus, if an agricultural scientist noted that they had entered the value for a sample variable incorrectly (eg K) then any update to that value in the database could automatically fire the derived data generation. No one needs to remember to re-run a client script or middle tier application program.

Anyone interested in the solution please contact me directly.

Creative Commons License

post this at del.icio.uspost this at Diggpost this at Technoratipost this at Redditpost this at Farkpost this at Yahoo! my webpost this at Windows Livepost this at Google Bookmarkspost this to Twitter

Comment [3]

Thankss share.

— a games · 27 March 2012, 03:02 · #

Hi
I need a 3d solution for making DEM in oracle and 3d viewer for show 3d objects like Dem & building that store in oracle spatial.
Can you help us.
Tahnks.
Behanm Aryafar

— Behnam · 1 May 2013, 22:36 · #

Behanm,

This article is about how you can create DEMs as grids. The delaunay triangles form the basis of a TIN (Triangulated Irregular Network) which is often used in 3D applications to create a surface mesh but because the sample points don’t cover the entire area, the gridding and IDW calculations are needed to get a reasonable extrapolation.

Note that though the article doesn’t take sample points with Z or Elevation values but it could do.

To create a DEM you would need sample points and then some algorithms/software that could create you a surface grid or TIN. This could be loaded into Oracle’s SDO_TIN structures. 3D objects like Buildings can be loaded into Oracle Solids using software like FME or CAD software. It may be that some open source software supports the creation of SDO_TIN or Solid objects in Oracle.

I don’t know of any software capable of direct visualisation of TIN and Solid data from Oracle but they do exist – perhaps FME or one of the GIS or CAD vendors.

regards
SIMon

— Simon Greener · 4 May 2013, 13:32 · #