Changes between Version 1 and Version 2 of FDORfc64


Ignore:
Timestamp:
09/24/12 08:45:11 (12 years ago)
Author:
danstoica
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • FDORfc64

    v1 v2  
    1 = FDO RFC 64 - In-memory Spatial Index =
     1= FDO RFC 64 - Enhance secondary filter performance using in-memory spatial index =
    22
    33This page contains an change request (RFC) for the FDO Open Source project. 
    … …  
    88 
    99||RFC Template Version||(1.0)||
    10 ||Submission Date|| June 13, 2012 ||
     10||Submission Date|| September 25, 2012 ||
    1111||Last Modified|| Dan Stoica June 13, 2012 ||
    1212||Author||Dan Stoica||
    13 ||RFC Status||Adopted||
     13||RFC Status||Not ready for review||
    1414||Implementation Status||Prototype||
    1515||Proposed Milestone||3.8.0.0||
    … …  
    2323== Overview ==
    2424
    25 This RFC is for adding an in-memory Spatial Index to the FDO Spatial project.
     25This RFC is for enhance secondary filter performance in FDO Spatial project. It leverages the in-memory Spatial Index implemented by FDO RFC 63.
    2626
    2727== Motivation ==
    2828
     29(from RFC 63)
    2930The 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:
    3031
    … …  
    3940The 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.
    4041
    41 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.
     42The proposal is to add a new Evaluate() method to 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 for multiple times, for each candidate geometry, and creating the spatial index each time is not optimal.
     43
    4244
    4345
    4446{{{
    45 /// \ingroup (enums)
    46 /// \brief
    47 /// FdoSpatialIndexMode is an enumeration of the types of the Spatial Index
    48 enum FdoSpatialIndexMode
    49 {
    50     /// Mode #1 - Regular Spatial Index: one entry in the SI for the entire geometry
    51     FdoSpatialIndex_ByGeometriesBoundingBox = 0,
    52 
    53     /// Mode #2 - The geometries are broken into segments and each segment has an entry in the SI.
    54     /// The segment index is contiguous over parts and subparts.
    55     FdoSpatialIndex_BySegmentsMultipleFeatures = 1,
    56 
    57     /// Mode #3 - Just one geometry is allowed. The geometry is broken into segments
    58     /// and each segment has an entry in the SI. The part and subpart are encoded to allow
    59     /// for sorting and fast processing.
    60     FdoSpatialIndex_BySegmentsSingleFeature = 2
    61 };
    62 
    63 /// \brief
    64 /// Spatial Index class.
    65 class FdoSpatialIndex : public FdoIDisposable
    66 {
    67     friend class FdoSpatialIndexIterator;
    68 
    69 public:
    7047    /// \brief
    71     /// Creates a Spatial Index instance
    72     ///
    73     /// \param mode
    74     /// Input Type of the spatial index
    75     ///
    76     /// \return
    77     /// Returns A spatial index instance
     48    /// Evaluates if two FDO geometric objects spatially interact with each other
     49    /// based on a user supplied spatial operator. For example: Contains, Crosses,
     50    /// Disjoint, Equals, Intersects, Overlaps, Touches, Within, CoveredBy, Inside,
     51    /// EnvelopeIntersects.
    7852    ///
    79     FDO_SPATIAL_API static FdoSpatialIndex* Create(FdoSpatialIndexMode mode = FdoSpatialIndex_ByGeometriesBoundingBox);
    80 
    81     /// \brief
    82     /// Retrieves the Spatial index mode set at creation time
    83     ///
    84     /// \return
    85     /// Returns the Spatial index mode set at creation
    86     ///
    87     FDO_SPATIAL_API FdoSpatialIndexMode GetMode();
    88 
    89     /// \brief
    90     /// Inserts a feature into the spatial index given a bounding box
    91     ///
    92     /// \remarks
    93     /// Applies only for Mode #1. The objectId is not encoded.
    94     ///
    95     /// \param objectId
    96     /// Input The object identifier
    97     /// \param ext
    98     /// Input A bounding box
     53    /// \param g1
     54    /// Input Left hand Geometry to Evaluate
     55    /// \param si1
     56    /// Input The spatial index associated with g1. A valid spatial index is not NULL
     57    /// and of type BySegmentsSingleFeature or BySegmentsMultipleFeatures (just one
     58    /// feature). If an invalid spatial index is provided, then this method will silently
     59    /// delegate to Evaluate(g1, op, g2, tolXY).
     60    /// \param op
     61    /// Input The spatial operation to apply to the left and right hand geometries
     62    /// \param g2
     63    /// Input Right hand Geometry to Evaluate
     64    /// \param toleranceXY
     65    /// Input XY tolerance to evaluate the spatial condition
     66    /// Default tolerance used is 1e-10. Valid range is >0
     67    /// If an invalid value is provided, the default then will be used
    9968    ///
    10069    /// \return
    101     /// Returns Nothing
    102     ///
    103     FDO_SPATIAL_API void InsertObject(FdoInt64 objectId, FdoIEnvelope *ext);
    104 
    105     /// \brief
    106     /// Inserts a feature into the spatial index given a geometry
    107     ///
    108     /// \remarks
    109     /// Applies for Mode #2 and #3. The objectId is encoded as follows:
    110     /// Mode #2:
    111     ///      32 bits (0-31)  - 1-based object identifier
    112     ///      32 bits (32-63) - 1-based segment # (contiguous)
    113     ///
    114     /// Mode #3:
    115     ///      0 bits          - object identifier (will be ignored)
    116     ///      16 bits (0-15)  - part # (for multi-features) max. 65534
    117     ///      16 bits (16-31) - subpart # (e.g. polygons with interior rings) max 65534
    118     ///      32 bits (32-63) - 1-based segment #
    119     ///
    120     /// In Mode #3 a exception will be thrown in case the encoding fails. In this case
    121     /// Mode #2 can be used instead.
    122     ///
    123     /// \param objectId
    124     /// Input The object identifier
    125     /// \param fgfArray
    126     /// Input A geometry in FGF format
    127     ///
    128     /// \return
    129     /// Returns Nothing
    130     ///
    131     FDO_SPATIAL_API void InsertObject(FdoInt32 objectId, FdoByteArray* fgfArray);
    132 
    133     /// \brief
    134     /// Erases an entry in the spatial index given the id and a bounding box
    135     ///
    136     /// \remarks
    137     /// In Mode #2 removes all the entries related to the feature identifier.
    138     /// In Mode #3 the spatial index will be emptied.
    139     ///
    140     /// \param objectId
    141     /// Input The object identifier.
    142     /// \param ext
    143     /// Input The bounding box of the feature. It may be NULL in which case
    144     /// the spatial index total extents will be used.
    145     ///
    146     /// \return
    147     /// Returns Nothing
    148     ///
    149     FDO_SPATIAL_API void EraseObject(FdoInt64 objectId, FdoIEnvelope *ext);
    150 
    151     /// \brief
    152     /// Returns the extent of the spatial index
    153     ///
    154     /// \return
    155     /// Returns The extents of the spatial index
    156     ///
    157     FDO_SPATIAL_API FdoIEnvelope* GetTotalExtent();
    158 
    159     /// \brief
    160     /// Decodes a marker returned by the Spatial index iterator.
    161     /// Applies only for Mode #2, BySegmentsMultipleFeatures.
    162     ///
    163     /// \param marker
    164     /// Input A marker returned by the Spatial index iterator
    165     /// \param objectId
    166     /// Output The object identifier
    167     /// \param iVertex
    168     /// Output The index of the segment in the original geometry, 1-based
    169     ///
    170     /// \return
    171     /// Returns Nothing
    172     ///
    173     FDO_SPATIAL_API void     DecodeMarker(FdoInt64 marker, FdoInt32 &objectId, FdoInt32 &iSegment);
    174 
    175     /// \brief
    176     /// Decodes a marker returned by the Spatial index iterator.
    177     /// Applies only for Mode #3, BySegmentsSingleFeature.
    178     ///
    179     /// \param marker
    180     /// Input A marker returned by the Spatial index iterator
    181     /// \param iPart
    182     /// Output The index of the part in a multi-geometry, e.g. a polygon # in a multi-polygon
    183     /// \param iSubPart
    184     /// Output The index of the subpart in a geometry, e.g. a ring # in a polygon
    185     /// \param iVertex
    186     /// Output The index of the segment in the sub-part, 1-based
    187     ///
    188     /// \return
    189     /// Returns Nothing
    190     ///
    191     FDO_SPATIAL_API void     DecodeMarker(FdoInt64 marker, FdoInt32 &iPart, FdoInt32 &iSubPart, FdoInt32 &iSegment);
    192 
    193 /// \cond DOXYGEN-IGNORE
    194     virtual void Dispose();
    195 /// \endcond
    196    
    197 protected:
    198     // Constructor
    199     FdoSpatialIndex(FdoSpatialIndexMode mode = FdoSpatialIndex_ByGeometriesBoundingBox);
    200 
    201     virtual ~FdoSpatialIndex();
    202 };
    203 
    204 /// \brief
    205 /// Spatial Index Iterator class
    206 class FdoSpatialIndexIterator
    207 {
    208 public:
    209     /// \brief
    210     /// Creates a Spatial Index Iterator instance
    211     ///
    212     /// \param si
    213     /// Input A Spatial Index instance
    214     /// \param minx
    215     /// Input The minimim X of the bounding box representing the search area
    216     /// \param miny
    217     /// Input The minimim Y of the bounding box representing the search area
    218     /// \param maxx
    219     /// Input The maximum X of the bounding box representing the search area
    220     /// \param maxy
    221     /// Input The maximum Y of the bounding box representing the search area
    222     ///
    223     /// \return
    224     /// Returns A Spatial Index Iterator instance
    225     ///
    226     FDO_SPATIAL_API FdoSpatialIndexIterator(FdoSpatialIndex* si, double minx, double miny, double maxx, double maxy);
    227 
    228         /// \brief
    229         /// Iterator over the features selected in the the search area
    230         ///
    231         /// \return
    232     /// Returns an encoded marker. Zero (0) return value stands for the end of fetch
    233     ///
    234     FDO_SPATIAL_API FdoInt64 GetNextObject();
    235 
    236     FDO_SPATIAL_API ~FdoSpatialIndexIterator();
    237 };
     70    /// Returns the evaluation of spatial operation.
     71    FDO_SPATIAL_API static bool Evaluate(FdoIGeometry* g1, FdoSpatialIndex* si1, FdoSpatialOperations op, FdoIGeometry* g2, double toleranceXY);
    23872
    23973}}}
    24074
     75
    24176== Remarks ==
    24277
    243 * The API proposes 3 usage modes. This provides maximum versatility for various scenarios.
    244 * Mode 1 implements a regular spatial index, very performant.
    245 * For mode 2 and 3 the client code has to implement a segment visitor in order to retrieve a segment from the geometry.
    246 * This API is a wrapper over the R-tree implementation located in the Sqlite provider and developed by Traian Stanev.
    247 * The location of this API will be FDO Spatial.
    24878
    24979== How to use this API ==