FDO RFC 39 - Spatial operator combinations support

This page contains an change request (RFC) for the FDO Open Source project. More FDO RFCs can be found on the RFCs page.

Status

RFC Template Version	(1.0)
Submission Date	June 08, 2009
Last Modified	Dan StoicaTimestamp
Author	Dan Stoica, Orest Halustchak
RFC Status	adopted
Implementation Status	pending
Proposed Milestone	3.5.0.0
Assigned PSC guide(s)	Greg Boone
Voting History
+1	Greg, Traian, Jackie, Orest
+0	Jason
-0
-1

Overview

This RFC is for adding spatial operator combinations support (the RELATE spatial operator).

Motivation

Along with the standard named spatial operators which FDO already supports, OGC specifies the Relate predicate based on the pattern matrix which has the advantage that clients can test for a large number of spatial relationships and fine tune the particular relationship being tested; This pattern matrix is called the Extended Nine-Intersection Model (DE-9IM); see Reference [1].

This model has been adopted by MS SqlServer 2008 and PostGIS databases following the OGC syntax; see References [3], [4]. Example:

STRelate('T*FF*') for 'Within'

Oracle also supports Relate and DE-9IM model but in more readable form; see Reference [2]. Example:

SDO_RELATE(... 'mask=touch+coveredby') = 'TRUE';

Proposed Solution

Supporting Relate implies providing the ability to generate DE-9IM strings based on a OR mask. Note it is not possible to generate an unambiguous OR mask given a DE-9IM string.

Obviously generating valid strings for spatial operation combinations in DE-9IM form is not convenient for the user and this task must be accomplished internally by FDO. In turn, FDO will present the user the list of available named operators which can be combined in a bitmapped mask.

A number of changes in FDO are proposed:

1) Add new !FdoSpatialOperations_Relate to FdoSpatialOperations enumeration.

2) Assign values to FdoSpatialOperations so they can be bitmapped:

enum FdoSpatialOperations
{
    FdoSpatialOperations_EnvelopeIntersects = 0x0000, 
    FdoSpatialOperations_Relate     = 0x0001,  
    FdoSpatialOperations_Contains   = 0x0002,
    FdoSpatialOperations_Crosses    = 0x0004,
    FdoSpatialOperations_Disjoint   = 0x0008,
    FdoSpatialOperations_Equals     = 0x0010,
    FdoSpatialOperations_Intersects = 0x0020,
    FdoSpatialOperations_Overlaps   = 0x0040,
    FdoSpatialOperations_Touches    = 0x0080,
    FdoSpatialOperations_Within     = 0x0100,
    FdoSpatialOperations_CoveredBy  = 0x0200, 
    FdoSpatialOperations_Inside     = 0x0400
};

3) Enhance FdoSpatialCondition class to handle a bitmapped mask of spatial operators. Avoid creating a new set of constructors just for RELATE, by adding an extra optional parameter to the existing constructors. Add setter and getter for the mask.

class FdoSpatialCondition : public FdoGeometricCondition
{
...
    /// \param relateMask 
    /// Input bitmapped FdoSpatialOperations mask for the RELATE spatial operation
    /// 
    /// \return
    /// Returns FdoSpatialCondition
    /// Throws "Invalid parameter" exception in case relateMask > 0 and the operation is not RELATE
    /// 

    FDO_API static FdoSpatialCondition* Create(FdoIdentifier* propertyName, FdoSpatialOperations operation, FdoExpression* geometry, FdoInt32 relateMask = -1);

////\\\\ NOTE: the same extra optional parameter will be added to all the constructors.

    /// Sets the bitmapped value of combined spatial operator(s) for RELATE usage.
    /// Throws "Invalid parameter" exception in case:
    ///     value > 0 and the spatial operation is not RELATE
    ///     value <= 0 and the spatial operation is RELATE
    ///     value is not a valid bitmapped FdoSpatialOperations mask

    FDO_API void SetRelateMask( FdoInt32 value );

    /// Gets the bitmapped value of combined spatial operators. 

    FDO_API FdoInt32 GetRelateMask();
}

4) Provide a common implementation for computing the pattern matrix in FdoSpatialUtility class. The matrixes for individual operations are available on the OGC site. Given a combination of operators, the method will perform an OR operation for each element of the matrix, interatively for each matrix involved.

class FdoSpatialUtility
{
...
    /// \brief
    /// Computes the pattern matrix DE-9IM compliant. 
    /// See the Extended Nine-Intersection Model (DE-9IM) of the spatial operation at
    /// http://portal.opengeospatial.org/files/?artifact_id=18241 , section 6.1.15. 
    /// 
    /// \param value 
    /// Input the bitmapped mask of FdoSpatialOperations.
    /// 
    /// \return
    /// Returns a valid 9 characters string representing the pattern matrix.
    /// Returns NULL in case the input is invalid.
    /// Example: 'T*F**F***' is returned for 'Within' spatial operation
    /// 
    FDO_API static FdoString* Get9IMPatternMatrix(FdoInt32 value);

Implications

The actual implementation of the RELATE operator in the providers is easy. First, retrieve

      FdoSpatialCondition*  pFilter = ...
      FdoSpatialOperations op = pFilter->GetOperation();
      if ( op == FdoSpatialOperations_Relate )
      {
          Int32  mask = pFilter->GetRelateMask();
          ...
      }

Depending on the provider the coding will be different:

1. RDBMS providers supporting natively the RELATE spatial operator can implement the new API by examining the mask:

a) SqlServerSpatial or PostGIS providers need the string pattern matrix to pass it as input for STRelate() and ST_Relate() respectively:

     FdoString* matrix = FdoSpatialUtility::Get9IMPatternMatrix( mask );

     // Build the SQL like: STRelate(' + matrix +');

b) An Oracle provider will inspect the bitmapped mask and extract the spatial operators to build the SQL like:

     SDO_RELATE(... 'mask=touch+coveredby') = 'TRUE';

2) The providers not supporting natively RELATE will need to expand the RELATE filter into a OR filter with multiple basic spatial operations.

Test Plan

• create a test datastore with various geometry types and various types of spatial interaction. Good examples can be found in [1].
  
• test Relate with invalid masks. Exceptions should be thrown.
  
• test Relate queries with just one spatial operator. The results should match those from queries with named operators (i.e. existing style)
  
• test Relate with different spatial operation combinations. Manually validate the results.
  

Funding/Resources

Autodesk to provide resources / funding.

Referencies

[1] OpenGIS® Implementation Specification for Geographic information - Simple feature access - Part 1: Common architecture - Extended Nine, 6.1.15.2 The Dimensionally Extended Nine-Intersection Model (DE-9IM)
[2] ​http://download-west.oracle.com/docs/cd/B19306_01/appdev.102/b14255/sdo_operat.htm#i78531 - Oracle SDO_RELATE() operator
[3] ​http://msdn.microsoft.com/en-us/library/bb933915.aspx - SqlServer2008 STRelate() operator
[4] ​http://postgis.refractions.net/download/postgis-1.3.6.pdf - PostGIS ST_Relate() operator