QgsSnappingUtils: improvements of the hybrid indexing strategy

wonder-sk · wonder-sk · commit cad3173d6ec5 · 2015-01-23T14:30:46.000+07:00
Instead of calculating feature count (which may add extra overhead),
let's directly try to build index for layers. Only when a certain limit
of features is reached (currently 1 million), the indexing is cancelled
and layer is marked as non-indexable.
diff --git a/python/core/qgspointlocator.sip b/python/core/qgspointlocator.sip
@@ -16,8 +16,14 @@ class QgsPointLocator : QObject
 
     enum Type { Invalid, Vertex, Edge, Area, All };
 
-    /** Prepare the index for queries. Does nothing if the index already exists */
-    void init();
+    /** Prepare the index for queries. Does nothing if the index already exists.
+     * If the number of features is greater than the value of maxFeaturesToIndex, creation of index is stopped
+     * to make sure we do not run out of memory. If maxFeaturesToIndex is -1, no limits are used. Returns
+     * false if the creation of index has been prematurely stopped due to the limit of features, otherwise true */
+    bool init( int maxFeaturesToIndex = -1 );
+
+    /** Indicate whether the data have been already indexed */
+    bool hasIndex() const;
 
     struct Match
     {
diff --git a/src/core/qgspointlocator.cpp b/src/core/qgspointlocator.cpp
@@ -595,23 +595,27 @@ QgsPointLocator::~QgsPointLocator()
 }
 
 
-void QgsPointLocator::init()
+bool QgsPointLocator::init( int maxFeaturesToIndex )
 {
-  if ( !mRTree )
-    rebuildIndex();
+  return hasIndex() ? true : rebuildIndex( maxFeaturesToIndex );
+}
+
+bool QgsPointLocator::hasIndex() const
+{
+  return mRTree != 0;
 }
 
 
 
-void QgsPointLocator::rebuildIndex()
+bool QgsPointLocator::rebuildIndex( int maxFeaturesToIndex )
 {
   destroyIndex();
 
   QLinkedList<RTree::Data*> dataList;
   QgsFeature f;
   QGis::GeometryType geomType = mLayer->geometryType();
   if ( geomType == QGis::NoGeometry )
-    return; // nothing to index
+    return true; // nothing to index
 
   QgsFeatureRequest request;
   request.setSubsetOfAttributes( QgsAttributeList() );
@@ -623,6 +627,7 @@ void QgsPointLocator::rebuildIndex()
     request.setFilterRect( rect );
   }
   QgsFeatureIterator fi = mLayer->getFeatures( request );
+  int indexedCount = 0;
   while ( fi.nextFeature( f ) )
   {
     if ( !f.geometry() )
@@ -634,6 +639,14 @@ void QgsPointLocator::rebuildIndex()
     SpatialIndex::Region r( rect2region( f.geometry()->boundingBox() ) );
     dataList << new RTree::Data( 0, 0, r, f.id() );
     mGeoms[f.id()] = new QgsGeometry( *f.geometry() );
+    ++indexedCount;
+
+    if ( maxFeaturesToIndex != -1 && indexedCount > maxFeaturesToIndex )
+    {
+      qDeleteAll( dataList );
+      destroyIndex();
+      return false;
+    }
   }
 
   // R-Tree parameters
@@ -645,11 +658,12 @@ void QgsPointLocator::rebuildIndex()
   SpatialIndex::id_type indexId;
 
   if ( dataList.isEmpty() )
-    return; // no features
+    return true; // no features
 
   QgsPointLocator_Stream stream( dataList );
   mRTree = RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, stream, *mStorage, fillFactor, indexCapacity,
            leafCapacity, dimension, variant, indexId );
+  return true;
 }
 
 
diff --git a/src/core/qgspointlocator.h b/src/core/qgspointlocator.h
@@ -59,8 +59,14 @@ class CORE_EXPORT QgsPointLocator : public QObject
 
     enum Type { Invalid = 0, Vertex = 1, Edge = 2, Area = 4, All = Vertex | Edge | Area };
 
-    /** Prepare the index for queries. Does nothing if the index already exists */
-    void init();
+    /** Prepare the index for queries. Does nothing if the index already exists.
+     * If the number of features is greater than the value of maxFeaturesToIndex, creation of index is stopped
+     * to make sure we do not run out of memory. If maxFeaturesToIndex is -1, no limits are used. Returns
+     * false if the creation of index has been prematurely stopped due to the limit of features, otherwise true */
+    bool init( int maxFeaturesToIndex = -1 );
+
+    /** Indicate whether the data have been already indexed */
+    bool hasIndex() const;
 
     struct Match
     {
@@ -149,7 +155,7 @@ class CORE_EXPORT QgsPointLocator : public QObject
 
 
   protected:
-    void rebuildIndex();
+    bool rebuildIndex( int maxFeaturesToIndex = -1 );
     void destroyIndex();
 
   private slots:
diff --git a/src/core/qgssnappingutils.cpp b/src/core/qgssnappingutils.cpp
@@ -67,17 +67,10 @@ void QgsSnappingUtils::clearAllLocators()
 
 QgsPointLocator* QgsSnappingUtils::locatorForLayerUsingStrategy( QgsVectorLayer* vl, const QgsPoint& pointMap, double tolerance )
 {
-  if ( mStrategy == IndexAlwaysFull )
+  if ( willUseIndex( vl ) )
     return locatorForLayer( vl );
-  else if ( mStrategy == IndexNeverFull )
+  else
     return temporaryLocatorForLayer( vl, pointMap, tolerance );
-  else // Hybrid
-  {
-    if ( vl->pendingFeatureCount() > 1000000 )
-      return temporaryLocatorForLayer( vl, pointMap, tolerance );
-    else
-      return locatorForLayer( vl );
-  }
 }
 
 QgsPointLocator* QgsSnappingUtils::temporaryLocatorForLayer( QgsVectorLayer* vl, const QgsPoint& pointMap, double tolerance )
@@ -92,6 +85,22 @@ QgsPointLocator* QgsSnappingUtils::temporaryLocatorForLayer( QgsVectorLayer* vl,
   return mTemporaryLocators.value( vl );
 }
 
+bool QgsSnappingUtils::willUseIndex( QgsVectorLayer* vl ) const
+{
+  if ( mStrategy == IndexAlwaysFull )
+    return true;
+  else if ( mStrategy == IndexNeverFull )
+    return false;
+  else
+  {
+    if ( mHybridNonindexableLayers.contains( vl->id() ) )
+      return false;
+
+    // if the layer is too big, the locator will later stop indexing it after reaching a threshold
+    return true;
+  }
+}
+
 
 static QgsPointLocator::Match _findClosestSegmentIntersection( const QgsPoint& pt, const QgsPointLocator::MatchList& segments )
 {
@@ -204,6 +213,8 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
     if ( !mCurrentLayer )
       return QgsPointLocator::Match();
 
+    prepareIndex( QList<QgsVectorLayer*>() << mCurrentLayer );
+
     // data from project
     double tolerance = QgsTolerance::toleranceInMapUnits( mDefaultTolerance, mMapSettings, mDefaultUnit );
     int type = mDefaultType;
@@ -227,6 +238,11 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
   }
   else if ( mSnapToMapMode == SnapAdvanced )
   {
+    QList<QgsVectorLayer*> layers;
+    foreach ( const LayerConfig& layerConfig, mLayers )
+      layers << layerConfig.layer;
+    prepareIndex( layers );
+
     QgsPointLocator::Match bestMatch;
     QgsPointLocator::MatchList edges; // for snap on intersection
     double maxSnapIntTolerance = 0;
@@ -257,15 +273,17 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
     double tolerance = QgsTolerance::toleranceInMapUnits( mDefaultTolerance, mMapSettings, mDefaultUnit );
     int type = mDefaultType;
 
+    QList<QgsVectorLayer*> layers;
+    foreach( const QString& layerID, mMapSettings.layers() )
+      if ( QgsVectorLayer* vl = qobject_cast<QgsVectorLayer*>( QgsMapLayerRegistry::instance()->mapLayer( layerID ) ) )
+        layers << vl;
+    prepareIndex( layers );
+
     QgsPointLocator::MatchList edges; // for snap on intersection
     QgsPointLocator::Match bestMatch;
 
-    foreach( const QString& layerID, mMapSettings.layers() )
+    foreach( QgsVectorLayer* vl, layers )
     {
-      QgsVectorLayer* vl = qobject_cast<QgsVectorLayer*>( QgsMapLayerRegistry::instance()->mapLayer( layerID ) );
-      if ( !vl )
-        continue;
-
       if ( QgsPointLocator* loc = locatorForLayerUsingStrategy( vl, pointMap, tolerance ) )
       {
         _updateBestMatch( bestMatch, pointMap, loc, type, tolerance, filter );
@@ -285,6 +303,31 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
 }
 
 
+void QgsSnappingUtils::prepareIndex( const QList<QgsVectorLayer*>& layers )
+{
+  // check if we need to build any index
+  QList<QgsVectorLayer*> layersToIndex;
+  foreach( QgsVectorLayer* vl, layers )
+  {
+    if ( willUseIndex( vl ) && !locatorForLayer( vl )->hasIndex() )
+      layersToIndex << vl;
+  }
+  if ( layersToIndex.isEmpty() )
+    return;
+
+  // build indexes
+  QTime t; t.start();
+  foreach ( QgsVectorLayer* vl, layersToIndex )
+  {
+    QTime tt; tt.start();
+    if ( !locatorForLayer( vl )->init( mStrategy == IndexHybrid ? 1000000 : -1 ) )
+      mHybridNonindexableLayers.insert( vl->id() );
+    QgsDebugMsg( QString( "Index init: %1 ms (%2)" ).arg( tt.elapsed() ).arg( vl->id() ) );
+  }
+  QgsDebugMsg( QString( "Prepare index total: %1 ms" ).arg( t.elapsed() ) );
+}
+
+
 QgsPointLocator::Match QgsSnappingUtils::snapToCurrentLayer( const QPoint& point, int type, QgsPointLocator::MatchFilter* filter )
 {
   if ( !mCurrentLayer )
diff --git a/src/core/qgssnappingutils.h b/src/core/qgssnappingutils.h
@@ -139,6 +139,11 @@ class CORE_EXPORT QgsSnappingUtils : public QObject
     //! return a temporary locator with index only for a small area (will be replaced by another one on next request)
     QgsPointLocator* temporaryLocatorForLayer( QgsVectorLayer* vl, const QgsPoint& pointMap, double tolerance );
 
+    //! find out whether the strategy would index such layer or just use a temporary locator
+    bool willUseIndex( QgsVectorLayer* vl ) const;
+    //! initialize index for layers where it makes sense (according to the indexing strategy)
+    void prepareIndex( const QList<QgsVectorLayer*>& layers );
+
   private:
     // environment
     QgsMapSettings mMapSettings;
@@ -159,6 +164,8 @@ class CORE_EXPORT QgsSnappingUtils : public QObject
     LocatorsMap mLocators;
     //! temporary locators (indexing just a part of layers). owned by the instance
     LocatorsMap mTemporaryLocators;
+    //! list of layer IDs that are too large to be indexed (hybrid strategy will use temporary locators for those)
+    QSet<QString> mHybridNonindexableLayers;
 };
 
 
