FDO RFC 64 - Enhance 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 June 13, 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 enhance secondary filter performance in 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 Evaluate() method to 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 for 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 si1
    /// Input The spatial index associated with g1. 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 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
    /// 
    /// \return
    /// Returns the evaluation of spatial operation.
    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, FdoSpatialIndex* si1, FdoSpatialOperations op, FdoIGeometry* g2, double toleranceXY); 

Remarks

How to use this API

The following code illustrates how to use the Spatial Index and the spatial index iterator.

    FdoPtr<FdoSpatialIndex> si;

    FdoPtr<FdoFgfGeometryFactory> gf = FdoFgfGeometryFactory::GetInstance();
  
    /*************************** Test Polygon *************************/
    FdoStringP geomText = L"POLYGON ((0 0, 5 0, 5 5, 0 5, 0 0), (1 1, 2 2, 2 1, 1 1), (3 3, 4 4, 4 3, 3 3))";
 
    FdoPtr<FdoIGeometry> geom = gf->CreateGeometry(geomText);
    FdoPtr<FdoByteArray> ba = gf->GetFgf(geom);

    // Mode #1: FdoSpatialIndex_ByGeometriesBoundingBox
    si = FdoSpatialIndex::Create(FdoSpatialIndex_ByGeometriesBoundingBox);

    // Insert the geometry
    si->InsertObject(777, ba);

    // Query the SI
    FdoSpatialIndexIterator iter1(si, 1, 1, 2, 2);

    FdoInt32 iPart, iSubpart, iSegment;
    FdoInt64 marker = 0;

    // Get the results
    while (marker = iter1.GetNextObject())
    {
	FdoInt64 fid = marker; // not encoded
	// ... do stuff   	
    }
	
    // Mode #2: FdoSpatialIndex_BySegmentsMultipleFeatures
    si = FdoSpatialIndex::Create(FdoSpatialIndex_BySegmentsMultipleFeatures);
    si->InsertObject(777, ba);

    FdoSpatialIndexIterator iter2(si, 1, 1, 2, 2);

    while (marker = iter2.GetNextObject())
    {
	FdoInt32 fid;
	si->DecodeMarker(marker, fid, iSegment);
	// ... do stuff
    }
	
    // Mode #3: FdoSpatialIndex_BySegmentsSingleFeature
    si = FdoSpatialIndex::Create(FdoSpatialIndex_BySegmentsSingleFeature);
    si->InsertObject(0, ba); // FeatId = 0

    FdoSpatialIndexIterator iter3(si, 1, 1, 2, 2);

    while (marker = iter3.GetNextObject())
    {
	si->DecodeMarker(marker, iPart, iSubpart, iSegment);
        // ... do stuff
    }

Managed FDO API

The FDO Managed Interfaces will be updated if required in a similar manner to reflect the proposed changes.

Test Plan

• Add unit test to test the API in all modes and primary filtering with boundary conditions.

Funding/Resources

Autodesk to provide resources/funding.