FDO RFC 63 - 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	May 18, 2012
Last Modified	Dan Stoica May 18, 2012
Author	Dan Stoica
RFC Status	For review
Implementation Status	Prototype
Proposed Milestone	3.7.0.0
Assigned PSC guide(s)	Greg Boone
Voting History
+1
+0
-0
-1

Overview

This RFC is for ....

Motivation

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.

This RFC describes the Spatial Index API. The implementation of the FDO secondary filter using the Spatial Index will be the topic of a separate RFC.

/// \ingroup (enums)
/// \brief
/// FdoSpatialIndexMode is an enumeration of the types of the Spatial Index,
/// representing the granularity.
enum FdoSpatialIndexMode
{
    /// Mode #1 - Regular Spatial Index: one entry in the rtree for the entire geometry
    FdoSpatialIndex_ByGeometriesBoundingBox = 0,

    /// Mode #2 - The geometries are broken into segments and each segment has an entry in the rtree.
    /// The segment index is contiguous over parts and subparts.
    FdoSpatialIndex_BySegmentsMultipleFeatures = 1,

    /// Mode #3 - Just one geometry is allowed. The geometry is broken into segments 
    /// and each segment has an entry in the rtree. The part and subpart are encoded to allow 
    /// for sorting and fast processing.
    FdoSpatialIndex_BySegmentsSingleFeature = 2
};

/// \brief
/// Spatial Index class.
class FdoSpatialIndex : public FdoIDisposable
{
    friend class FdoSpatialIndexIterator;

public:
    /// \brief
    /// Creates a Spatial Index instance
    ///
    /// \param mode 
    /// Input Type of the spatial index
    ///
    /// \return
    /// Returns A spatial index instance
    /// 
    FDO_SPATIAL_API static FdoSpatialIndex* Create(FdoSpatialIndexMode mode = FdoSpatialIndex_ByGeometriesBoundingBox); 

    /// \brief
    /// Retrieves the Spatial index mode set at creation time
    ///
    /// \return
    /// Returns the Spatial index mode set at creation
    /// 
    FDO_SPATIAL_API FdoSpatialIndexMode GetMode();

    /// \brief
    /// Inserts a feature into the spatial index given a bounding box
    ///
    /// \remarks
    /// Applies only for Mode #1. The Featid is not encoded.
    ///
    /// \param featId 
    /// Input The feature identifier
    /// \param featId 
    /// Input A bounding box
    /// 
    /// \return
    /// Returns Nothing
    /// 
    FDO_SPATIAL_API void InsertObject(FdoInt64 featId, FdoIEnvelope *ext);

    /// \brief
    /// Inserts a feature into the spatial index given a bounding box
    ///
    /// \remarks
    /// Applies for Mode #2 and #3. The Featid is encoded as follows:
    /// Mode #2: 
    ///      32 bits (0-31)  - 1-based featId # 
    ///      32 bits (32-63) - vertex # (contiguous)
    ///
    /// Mode #3:
    ///		 0 bits          - featId # (will be ignored)
    ///      16 bits (0-15)  - part # (for multi-features) max. 65534
    ///      16 bits (16-31) - subpart # (e.g. polygons with interior rings) max 65534
    ///      32 bits (32-63) - vertex # 
    /// 
    /// \param featId 
    /// Input The feature identifier
    /// \param featId 
    /// Input A geometry in FGF format
    /// 
    /// \return
    /// Returns Nothing
    /// 
    FDO_SPATIAL_API void InsertObject(FdoInt32 featId, FdoByteArray* fgfArray);

    /// \brief
    /// Returns the extent of the spatial index
    ///
    /// \return
    /// Returns The extents of the spatial index
    /// 
    FDO_SPATIAL_API FdoIEnvelope* GetTotalExtent();

    /// \brief
    /// Decodes a marker returned by the Spatial index iterator.
    /// Applies only for Mode #2, BySegmentsMultipleFeatures.
    ///
    /// \param marker
    /// Input A marker returned by the Spatial index iterator 
    /// \param featId 
    /// Output The featId 
    /// \param iVertex 
    /// Output The index of the segment in the original geometry, 1-based
    ///
    /// \return
    /// Returns Nothing
    /// 
    FDO_SPATIAL_API void     DecodeMarker(FdoInt64 marker, FdoInt32 &featId, FdoInt32 &iSegment);

    /// \brief
    /// Decodes a marker returned by the Spatial index iterator.
    /// Applies only for Mode #3, BySegmentsSingleFeature.
    ///
    /// \param marker
    /// Input A marker returned by the Spatial index iterator 
    /// \param iPart 
    /// Output The index of the part in a multi-geometry, e.g. a polygon # in a multi-polygon 
    /// \param iSubPart
    /// Output The index of the subpart in a geometry, e.g. a ring # in a polygon 
    /// \param iVertex 
    /// Output The index of the segment in the sub-part, 1-based
    ///
    /// \return
    /// Returns Nothing
    /// 
    FDO_SPATIAL_API void     DecodeMarker(FdoInt64 marker, FdoInt32 &iPart, FdoInt32 &iSubPart, FdoInt32 &iSegment);

/// \cond DOXYGEN-IGNORE
    virtual void Dispose();
/// \endcond
    
protected:
    // Constructor
    FdoSpatialIndex(FdoSpatialIndexMode mode = FdoSpatialIndex_ByGeometriesBoundingBox); 

    virtual ~FdoSpatialIndex();
};

/// \brief
/// Spatial Index Iterator class
class FdoSpatialIndexIterator
{
public:
    /// \brief
    /// Creates a Spatial Index Iterator instance
    ///
    /// \param si 
    /// Input A Spatial Index instance
    /// \param minx
    /// Input The minimim X of the bounding box representing the search area
    /// \param miny
    /// Input The minimim Y of the bounding box representing the search area
    /// \param maxx
    /// Input The maximum X of the bounding box representing the search area
    /// \param maxy
    /// Input The maximum Y of the bounding box representing the search area
    ///
    /// \return
    /// Returns A Spatial Index Iterator instance
    /// 
    FDO_SPATIAL_API FdoSpatialIndexIterator(FdoSpatialIndex* si, double minx, double miny, double maxx, double maxy);

	/// \brief
	/// Iterator over the features selected in the the search area
	///
	/// \return
    /// Returns an encoded marker. Zero (0) return value stands for the end of fetch
    /// 
    FDO_SPATIAL_API FdoInt64 GetNextObject();

    FDO_SPATIAL_API ~FdoSpatialIndexIterator();
};

How to use this API

The following code illustrates how to

Managed FDO API

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

Test Plan

• Enhance the unit tests and add roundtripping fidelity tests for !FdoInt16, !FdoInt32 and !FdoInt64 properties.

Funding/Resources

Autodesk to provide resources/funding.