| Version 8 (modified by , 12 years ago) ( diff ) |
|---|
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:
- check if any points of candidatePoly are inside filter polygon
- check if any points of filterPoly are inside candidate polygon
- 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 #
///
/// In Mode #3 a exception will be thrown in case the encoding fails. In this case
/// Mode #2 can be used instead.
///
/// \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
/// Erases an entry in the spatial index given the id and a bounding box
///
/// \remarks
/// In Mode #2 removes all the entries related to the feature identifier.
/// In Mode #3 the spatial index will be emptied.
///
/// \param featId
/// Input The feature identifier.
/// \param ext
/// Input The bounding box of the feature. It may be NULL in which case
/// the spatial index total extents will be used.
///
/// \return
/// Returns Nothing
///
FDO_SPATIAL_API void EraseObject(FdoInt64 featId, FdoIEnvelope *ext);
/// \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.
- This API is a wrapper over the R-tree implementation located in the Sqlite provider and developed by Traian Stanev.
- The location of this API will be FDO Spatial.
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.
Note:
See TracWiki
for help on using the wiki.
