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 adding an in-memory Spatial Index to the 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
enum FdoSpatialIndexMode
{
    /// Mode #1 - Regular Spatial Index: one entry in the SI for the entire geometry
    FdoSpatialIndex_ByGeometriesBoundingBox = 0,

    /// Mode #2 - The geometries are broken into segments and each segment has an entry in the SI.
    /// 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 SI. 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 ext 
    /// 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 geometry
    ///
    /// \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) - 1-based segment # (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) - 1-based segment # 
    /// 
    /// \param featId 
    /// Input The feature identifier
    /// \param fgfArray 
    /// 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 usage modes. This provides maximum flexibility for various scenarios.
• Mode 1 implements a regular spatial index, very performant
• For mode 2 and 3 the client code has to implement a segment visitor in order to retrieve a segment from the geometry.
• 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 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.