wiki:FDORfc49

FDO RFC 49 - API change to pass tolerance in evaluate spatial operations

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

Status

RFC Template Version1.0
Submission DateJun. 02 2010
Last ModifiedRomica Dascalescu (June 15, 2010)
AuthorRomica Dascalescu, Gavin Cramer, Dan Stoica
ContibutorsOrest Halustchak
RFC StatusAdopted
Implementation StatusPending
Proposed Milestone3.6.0.0
Assigned PSC guide(s)Greg Boone
Voting HistoryJuly 13, 2010
+1Greg Boone, Traian Stanev, Orest Halustchak, Jackie Ng, Haris Kurtagic
+0Jason Birch
-0
-1

Motivation

Using a default hard-coded tolerance in spatial operation evaluation, user can get wrong results.

Overview

Spatial queries are evaluated using a default hard-coded value (see below the used values). The issue is for certain spatial contexts we might miss features or find more features than we should. The tolerance should be set by the user when the data base is created (at create spatial context time) and use that value in spatial queries.

	/// These numbers are very small and provide
	/// the tolerance needed for "exact" computations,
	/// i.e. CAD style non-FDO geometry intersection.
        ///
	#define EPSILON 1e-10
	#define NEGEPSILON -EPSILON
	#define SQREPSILON 1e-20

Here we try to change the FDO API for spatial evaluation (FdoSpatialUtility - FDOSpatial.dll) used by providers like SQLite, SDF, SHP and not providers like KingOracle or SQL Spatial Server where the spatial evaluation is done on the server side.

The idea behind this RFC is to add support in FDO API for passing the tolerance into the spatial utility. FDO has already support for tolerances, so users can provide them when a new spatial context is created. Also those values can later be obtained using a spatial context reader. Each class in FDO has a dedicated spatial context reader. The provider can get those tolerances (XY and Z) by getting the spatial context of the class before running the spatial evaluation. If the spatial condition is a 2D evaluation the Z tolerance will be ignored.

Proposed Solution

We need to add a few new functions to allow user to pass tolerances. In case caller uses the default functions (without tolerances) the default tolerance will be used 1e-10 and valid range is > 0. If an invalid value is provided, the default then will be used. We can modify SQLite and possible SDF providers only, rest of the providers will remain unchanged and if needed will be changed later. All internal functions from spatial FDO module will be updated to add extra parameters for tolerance.

	/// \brief
	/// Spatial Utility Class.
        ///
	class FdoSpatialUtility
	{
	public:
	    /// \brief
	    /// Evaluates if two FDO geometric objects spatially interact with each other 
            /// based on a user supplied spatial operator. For example: Contains, Crosses, 
            /// Disjoint, Equals, Intersects, Overlaps, Touches, Within, CoveredBy, Inside, 
            /// EnvelopeIntersects.
	    /// 
	    /// \param g1 
	    /// Input Left hand Geometry to Evaluate
	    /// \param op 
	    /// Input The spatial operation to apply to the left and right hand geometries 
            /// \param g2 
	    /// Input Right hand Geometry to Evaluate
	    /// 
	    /// \param toleranceXY
	    /// Input XY tolerance to evaluate the spatial condition
	    /// Default tolerance used is 1e-10. Valid range is >0 
	    /// If an invalid value is provided, the default then will be used
	    /// 
	    /// \param toleranceZ
	    /// Input Z tolerance to evaluate the spatial condition in case we have 3D geometries
	    /// Default tolerance used is 1e-10. Valid range is >0
	    /// If an invalid value is provided, the default then will be used
	    /// 
	    /// \return
	    /// Returns the evaluation of spatial operation.
	    /// 
	    /// Existing Function
	    /// 
	    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, 
                                                 FdoSpatialOperations op, 
                                                 FdoIGeometry* g2); 
	    /// 
	    /// New Additional Functions
	    /// 
	    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, 
                                                 FdoSpatialOperations op, 
                                                 FdoIGeometry* g2, 
                                                 double toleranceXY); 

	    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, 
                                                 FdoSpatialOperations op, 
                                                 FdoIGeometry* g2, 
                                                 double toleranceXY, 
                                                 double toleranceZ); 
	    /// \brief
	    /// Tests whether a point is within a ring or not.
	    /// 
	    /// \param ring 
	    /// Input Ring to test
	    /// \param x 
	    /// Input X ordinate.
	    /// \param y 
	    /// Input Y ordinate.
	    /// \param toleranceXY
	    /// Input XY tolerance to evaluate the spatial condition
	    /// Default tolerance used is 1e-10. Valid range is >0
	    /// If an invalid value is provided, the default then will be used
	    /// 
	    /// \return
	    /// Returns TRUE if the point is within ring or on its boundary, FALSE otherwise.
	    /// 
	    /// Existing Function
	    /// 
	    FDO_SPATIAL_API static bool PointInRing(FdoILinearRing* ring, 
                                                    double x,
                                                    double y,
                                                    bool* isOnBoundary = NULL);
	    /// 
	    /// New Additional Function
	    /// 
	    FDO_SPATIAL_API static bool PointInRing(FdoILinearRing* ring, 
                                                    double x,
                                                    double y,
                                                    double toleranceXY,
                                                    bool* isOnBoundary = NULL);

	    /// \brief
	    /// Tests whether a point is within a polygon (including its islands) or not.
	    /// 
	    /// \param poly 
	    /// Input Polygon to test
	    /// \param x 
	    /// Input X ordinate.
	    /// \param y 
	    /// Input Y ordinate.
	    /// \param toleranceXY
	    /// Input XY tolerance to evaluate the spatial condition
	    /// Default tolerance used is 1e-10. Valid range is >0
	    /// If an invalid value is provided, the default then will be used
	    /// 
	    /// \return
	    /// Returns TRUE if the point is within polygon or on its boundary, FALSE otherwise.
	    /// 
	    /// Existing Function
	    /// 
	    FDO_SPATIAL_API static bool PointInPolygon(FdoIPolygon* poly,
                                                       double x,
                                                       double y,
                                                       bool* isOnIntBoundary = NULL,
                                                       bool* isOnExtBoundary = NULL);
	    /// 
	    /// New Additional Function
	    /// 
	    FDO_SPATIAL_API static bool PointInPolygon(FdoIPolygon* poly,
                                                       double x,
                                                       double y,
                                                       double toleranceXY,
                                                       bool* isOnIntBoundary = NULL,
                                                       bool* isOnExtBoundary = NULL);

Managed FDO API

The FDO Managed Interfaces will be updated in a similar manner to reflect the proposed C++ API changes.

New functions will be added in managed API to be able to pass special tolerances when needed.

public ref class SpatialUtility sealed
{
public:

    /// 
    /// Existing Function
    /// 
     static System::Boolean Evaluate(NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g1, NAMESPACE_OSGEO_FDO_FILTER::SpatialOperations op, NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g2);

    /// \brief
    /// 
    /// New Additional Functions
    /// 
    /// Evaluates if two FDO geometric objects spatially interact with each other based on a user supplied spatial operator.
    /// For example: Contains, Crosses, Disjoint, Equals, Intersects, Overlaps, Touches, Within, CoveredBy, Inside, EnvelopeIntersects.
    /// 
    /// \param g1 
    /// Input Left hand Geometry to Evaluate
    /// \param op 
    /// Input The spatial operation to apply to the left and right hand geometries 
    /// \param g2 
    /// Input Right hand Geometry to Evaluate
    /// \param toleranceXY 
    /// Input tolerance to used to compare XY coordinates
    /// Default tolerance used is 1e-10. Valid range is >0
    /// If an invalid value is provided, the default then will be used
    /// 
    /// \param toleranceZ
    /// Input tolerance to used to compare Z coordinate
    /// Default tolerance used is 1e-10. Valid range is >0
    /// If an invalid value is provided, the default then will be used
    /// 
    /// \return
    /// Returns The tesselated Geometry.
    /// 
    static System::Boolean Evaluate(NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g1, NAMESPACE_OSGEO_FDO_FILTER::SpatialOperations op, NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g2, double toleranceXY);
    static System::Boolean Evaluate(NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g1, NAMESPACE_OSGEO_FDO_FILTER::SpatialOperations op, NAMESPACE_OSGEO_GEOMETRY::IGeometry^ g2, double toleranceXY, double toleranceZ);

    /// 
    /// Existing Functions
    /// 
    static System::Boolean PointInRing( NAMESPACE_OSGEO_GEOMETRY::ILinearRing^ ring, System::Double coordinateX, System::Double coordinateY);
    static System::Boolean PointInRing( NAMESPACE_OSGEO_GEOMETRY::ILinearRing^ ring, System::Double coordinateX, System::Double coordinateY, System::Boolean% isOnBoundary);

    /// \brief
    /// 
    /// New Additional Functions
    /// 
    /// Tests whether a point is within a ring or not.
    /// 
    /// \param ring 
    /// Input Ring to test
    /// \param coordinateX 
    /// Input X ordinate.
    /// \param coordinateY 
    /// Input Y ordinate.
    /// \param toleranceXY 
    /// Input tolerance to used to compare XY coordinates
    /// Default tolerance used is 1e-10. Valid range is >0
    /// If an invalid value is provided, the default then will be used
    /// 
    /// \return
    /// Returns TRUE if the point is within ring or on its boundary, FALSE otherwise.
    /// 
    static System::Boolean PointInRing( NAMESPACE_OSGEO_GEOMETRY::ILinearRing^ ring, System::Double coordinateX, System::Double coordinateY, double toleranceXY);
    static System::Boolean PointInRing( NAMESPACE_OSGEO_GEOMETRY::ILinearRing^ ring, System::Double coordinateX, System::Double coordinateY, double toleranceXY, System::Boolean% isOnBoundary);

    /// 
    /// Existing Functions
    /// 
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY);
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY, System::Boolean% isOnExtBoundary);
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY, System::Boolean% isOnExtBoundary, System::Boolean% isOnInBoundary);

    /// \brief
    /// Tests whether a point is within a polygon (including its islands) or not.
    /// 
    /// New Additional Functions
    /// 
    /// \param polygon 
    /// Input Polygon to test
    /// \param coordinateX 
    /// Input X ordinate.
    /// \param coordinateY 
    /// Input Y ordinate.
    /// \param toleranceXY 
    /// Input tolerance to used to compare XY coordinates
    /// Default tolerance used is 1e-10. Valid range is >0
    /// If an invalid value is provided, the default then will be used
    /// 
    /// \return
    /// Returns TRUE if the point is within polygon or on its boundary, FALSE otherwise.
    /// 
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY, double toleranceXY);
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY, double toleranceXY, System::Boolean% isOnExtBoundary);
    static System::Boolean PointInPolygon(NAMESPACE_OSGEO_GEOMETRY::IPolygon^ polygon, System::Double coordinateX, System::Double coordinateY, double toleranceXY, System::Boolean% isOnExtBoundary, System::Boolean% isOnInBoundary);
}

Provider Implementation

Initially, the changes identified by this RFC are needed for the SQLite Provider. Other provider developers can provide support for these values on an as-needed basis. However, no change is required in other providers. The SQLite Provider will be changed in order to be able to store those tolerances. Right now the provider keeps just a few values for spatial context like srid, name, WKT, auth_Text, auth_srid. Tolerances will be added to that list. Older versions of the SQLite provider will ignore those new columns, and the new provider in case will not find these tolerances, will use the default values. Each provider will handle tolerances as they want. This RFC will not force providers to use the tolerance from spatial context (even that should be the right thing to do).

This RFC will just add to the spatial FDO functions two new parameters, having as default values the values used till now (hard-coded values) in order to make possible that some providers which cares about tolerance to be able to use it.

FDO spatial API had no way to pass tolerances and it used an internal hard-coded one making impossible for providers like SQLite to evaluate spatial queries having a certain tolerance.

Test Plan

Run existing FDO core unit tests and expand SQLite unit tests to test the proposed enhancements defined above.

Funding/Resources?

Autodesk to provide resources / funding.

Last modified 7 years ago Last modified on Jul 20, 2010 11:00:56 AM