FDO RFC 64 - Enhance the secondary filter performance using in-memory spatial index

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	September 25, 2012
Last Modified	Dan Stoica September 25, 2012
Author	Dan Stoica
RFC Status	Not ready for review
Implementation Status	Prototype
Proposed Milestone	3.8.0.0
Assigned PSC guide(s)	Orest Halustchak
Voting History
+1
+0
-0
-1

Overview

This RFC is for enhancing the secondary filter performance in the FDO Spatial project. It leverages the in-memory Spatial Index implemented by FDO RFC 63.

Motivation

(from RFC 63) The motivation is the poor performance of the FDO secondary filter. The worst case is Polygon intersect Polygon due to the potential complexity of the filter polygon and the amount of candidate polygons. The algorithm used for each candidate polygon is:

1. check if any points of candidatePoly are inside filter polygon
2. check if any points of filterPoly are inside candidate polygon
3. do pairwise edge intersection

Note that all 3 steps are correct, all of them are necessary and point-in-polygon/segment-to-segment tests are tuned for performance. Meaning further fine tuning is not a solution. The root problem is that the filter polygon is traversed entirely for each step and multiple times and this RFC is addressing it.

Proposed Solution

The solution is to create a Spatial Index for the filter polygon where each segment of the polygon has an entry. This way all the steps 1-3 will benefit by limiting the segments to check to those in the area of interest. For example, the point-in-polygon test will run a spatial query using the X-ray bounding box as search area. Therefore, instead of traversing all the segments, only a few will be processed for X-ray intersections.

The proposal is to add a new public FdoSpatialUtility::Evaluate() method which takes a Spatial Index parameter. The reason the spatial index is owned by the caller is for performance reasons: the same geometry filter is used multiple times for each candidate geometry, and creating the spatial index each time is not optimal.

    /// \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 si2
    /// Input The spatial index associated with g2. A valid spatial index is not NULL
    /// and of type BySegmentsSingleFeature or BySegmentsMultipleFeatures (just one
    /// feature). If an invalid spatial index is provided, then this method will silently
    /// delegate to Evaluate(g1, op, g2, tolXY). 
    /// \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 the evaluation of spatial operation.

    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, FdoSpatialOperations op, FdoIGeometry* g2, FdoSpatialIndex* si2, double toleranceXY); 

Remarks

• the implementation of this new API will focus on FDO Polygons, MultiPolygons, CurvePolygons and MultiCurvePolygons as filter geometries.
• FdoExpressionEngineImp::ProcessSpatialCondition() will be changed to take advantage of this new API.

How to use this API

       // The filter geometry
       FdoPtr<FdoIGeometry> geomRight = ...

       FdoPtr<FdoFgfGeometryFactory> gf = FdoFgfGeometryFactory::GetInstance();
       FdoPtr<FdoByteArray> fgf = gf->GetFgf(geomRight);

       // Check the geometry type. Create a spatial index in case the type is Polygon or MultiPolygon
       // and it has a non-trivial number of segments (say over 400).
       FdoPtr<FdoSpatialIndex> si = NULL;
       try
       {
           si = FdoSpatialIndex::Create(FdoSpatialIndex_BySegmentsSingleFeature);
           si->InsertObject(0, fgf);
       }
       catch (FdoException* ex)
       {
           ex->Release();

           // Creation failed due to excessive number of parts or subparts
           // Try BySegmentsMultipleFeatures mode. It should succeed.
           si = FdoSpatialIndex::Create(FdoSpatialIndex_BySegmentsMultipleFeatures);
           si->InsertObject(0, fgf);
       }

       // Assume the spatial operation is FdoSpatialOperations_Intersects.
       // For every candidate geometry evaluate against the filter geometry...

       FdoPtr<FdoIGeometry> geomLeft = ... // The candidate geometry

       bool eval = FdoSpatialUtility::Evaluate(geomLeft, FdoSpatialOperations_Intersects, geomRight, si, 0.001);

       // Do something with the result and continue with the next candidate...

Managed FDO API

At this time there is no plan to update the FDO Managed Interfaces since the managed spatial index is not implemented yet.

Test Plan

Add unit tests to test the new API for polygons and multipolygons with the spatial index mode 2 and 3 (i.e. BySegmentsSingleFeature and BySegmentsMultipleFeatures):

• Fidelity tests for Contains, Crosses, Disjoint, Equals, Intersects, Overlaps, Touches, Within, CoveredBy, and Inside spatial operators.
• Performance test to compare Evaluate() with and without spatial index

Funding/Resources

Autodesk to provide resources/funding.