= 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 [wiki:FDORfcs 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 adding a in-memory Spatial Index to FDO Spatial project. 

== 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();
};

}}}

== Remarks ==

The API proposes 3 modes. This provides maximum flexibility for various scenarios.
For mode #2 and #3 the client code has to implement a segment visitor in order to retrieve a segment from the geomtry. 

The actual implementation will be the R-tree implementation found under Sqlite provider and developed by Traian Stanev. 

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