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 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 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

Managed FDO API

At this time there is plan to update the FDO Managed Interfaces.

Test Plan

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

Funding/Resources

Autodesk to provide resources/funding.