Skip to content

Commit

Permalink
Improve indexing strategy for snapping (fixes #12578)
Browse files Browse the repository at this point in the history 
Implemented a simple heuristic that should keep the number of cached
features per layer reasonable - and thus lower the amount of consumed
memory and CPU for big layers.
  • Loading branch information
@wonder-sk
wonder-sk committed Jan 27, 2016
1 parent 86307ff commit fa66583
Show file tree
Hide file tree
Showing 5 changed files with 144 additions and 43 deletions.
3 changes: 3 additions & 0 deletions python/core/qgspointlocator.sip
View file
Expand Up @@ -23,6 +23,9 @@ class QgsPointLocator : QObject
//! Get extent of the area point locator covers - if null then it caches the whole layer
//! @note added in QGIS 2.14
const QgsRectangle* extent() const;
//! Configure extent - if not null, it will index only that area
//! @note added in QGIS 2.14
void setExtent( const QgsRectangle* extent );

enum Type { Invalid, Vertex, Edge, Area, All };

Expand Down
15 changes: 11 additions & 4 deletions src/core/qgspointlocator.cpp
View file
Expand Up @@ -600,10 +600,7 @@ QgsPointLocator::QgsPointLocator( QgsVectorLayer* layer, const QgsCoordinateRefe
mTransform = new QgsCoordinateTransform( layer->crs(), *destCRS );
}

if ( extent )
{
mExtent = new QgsRectangle( *extent );
}
setExtent( extent );

mStorage = StorageManager::createNewMemoryStorageManager();

Expand All @@ -626,6 +623,16 @@ const QgsCoordinateReferenceSystem* QgsPointLocator::destCRS() const
return mTransform ? &mTransform->destCRS() : nullptr;
}

void QgsPointLocator::setExtent( const QgsRectangle* extent )
{
if ( extent )
{
mExtent = new QgsRectangle( *extent );
}

destroyIndex();
}


bool QgsPointLocator::init( int maxFeaturesToIndex )
{
Expand Down
3 changes: 3 additions & 0 deletions src/core/qgspointlocator.h
View file
Expand Up @@ -66,6 +66,9 @@ class CORE_EXPORT QgsPointLocator : public QObject
//! Get extent of the area point locator covers - if null then it caches the whole layer
//! @note added in QGIS 2.14
const QgsRectangle* extent() const { return mExtent; }
//! Configure extent - if not null, it will index only that area
//! @note added in QGIS 2.14
void setExtent( const QgsRectangle* extent );

enum Type
{
Expand Down
149 changes: 112 additions & 37 deletions src/core/qgssnappingutils.cpp
View file
Expand Up @@ -30,6 +30,7 @@ QgsSnappingUtils::QgsSnappingUtils( QObject* parent )
, mDefaultTolerance( 10 )
, mDefaultUnit( QgsTolerance::Pixels )
, mSnapOnIntersection( false )
, mHybridPerLayerFeatureLimit( 50000 )
, mIsIndexing( false )
{
connect( QgsMapLayerRegistry::instance(), SIGNAL( layersWillBeRemoved( QStringList ) ), this, SLOT( onLayersWillBeRemoved( QStringList ) ) );
Expand Down Expand Up @@ -68,7 +69,9 @@ void QgsSnappingUtils::clearAllLocators()

QgsPointLocator* QgsSnappingUtils::locatorForLayerUsingStrategy( QgsVectorLayer* vl, const QgsPoint& pointMap, double tolerance )
{
if ( willUseIndex( vl ) )
QgsRectangle aoi( pointMap.x() - tolerance, pointMap.y() - tolerance,
pointMap.x() + tolerance, pointMap.y() + tolerance );
if ( isIndexPrepared( vl, aoi ) )
return locatorForLayer( vl );
else
return temporaryLocatorForLayer( vl, pointMap, tolerance );
Expand All @@ -86,22 +89,20 @@ QgsPointLocator* QgsSnappingUtils::temporaryLocatorForLayer( QgsVectorLayer* vl,
return mTemporaryLocators.value( vl );
}

bool QgsSnappingUtils::willUseIndex( QgsVectorLayer* vl ) const
bool QgsSnappingUtils::isIndexPrepared( QgsVectorLayer* vl, const QgsRectangle& areaOfInterest )
{
if ( vl->geometryType() == QGis::NoGeometry )
if ( vl->geometryType() == QGis::NoGeometry || mStrategy == IndexNeverFull )
return false;
if ( mStrategy == IndexAlwaysFull )

QgsPointLocator* loc = locatorForLayer( vl );

if ( mStrategy == IndexAlwaysFull && loc->hasIndex() )
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
if ( mStrategy == IndexHybrid && loc->hasIndex() && ( !loc->extent() || loc->extent()->contains( areaOfInterest ) ) )
return true;
}

return false; // the index - even if it exists - is not suitable
}


Expand Down Expand Up @@ -207,6 +208,12 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QPoint& point, QgsPoin
return snapToMap( mMapSettings.mapToPixel().toMapCoordinates( point ), filter );
}

inline QgsRectangle _areaOfInterest( const QgsPoint& point, double tolerance )
{
return QgsRectangle( point.x() - tolerance, point.y() - tolerance,
point.x() + tolerance, point.y() + tolerance );
}

QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, QgsPointLocator::MatchFilter* filter )
{
if ( !mMapSettings.hasValidSettings() )
Expand All @@ -217,12 +224,12 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
if ( !mCurrentLayer || mDefaultType == 0 )
return QgsPointLocator::Match();

prepareIndex( QList<QgsVectorLayer*>() << mCurrentLayer );

// data from project
double tolerance = QgsTolerance::toleranceInProjectUnits( mDefaultTolerance, mCurrentLayer, mMapSettings, mDefaultUnit );
int type = mDefaultType;

prepareIndex( QList<LayerAndAreaOfInterest>() << qMakePair( mCurrentLayer, _areaOfInterest( pointMap, tolerance ) ) );

// use ad-hoc locator
QgsPointLocator* loc = locatorForLayerUsingStrategy( mCurrentLayer, pointMap, tolerance );
if ( !loc )
Expand All @@ -242,9 +249,12 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
}
else if ( mSnapToMapMode == SnapAdvanced )
{
QList<QgsVectorLayer*> layers;
QList<LayerAndAreaOfInterest> layers;
Q_FOREACH ( const LayerConfig& layerConfig, mLayers )
layers << layerConfig.layer;
{
double tolerance = QgsTolerance::toleranceInProjectUnits( layerConfig.tolerance, layerConfig.layer, mMapSettings, layerConfig.unit );
layers << qMakePair( layerConfig.layer, _areaOfInterest( pointMap, tolerance ) );
}
prepareIndex( layers );

QgsPointLocator::Match bestMatch;
Expand Down Expand Up @@ -276,18 +286,20 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
// data from project
double tolerance = QgsTolerance::toleranceInProjectUnits( mDefaultTolerance, nullptr, mMapSettings, mDefaultUnit );
int type = mDefaultType;
QgsRectangle aoi = _areaOfInterest( pointMap, tolerance );

QList<QgsVectorLayer*> layers;
QList<LayerAndAreaOfInterest> layers;
Q_FOREACH ( const QString& layerID, mMapSettings.layers() )
if ( QgsVectorLayer* vl = qobject_cast<QgsVectorLayer*>( QgsMapLayerRegistry::instance()->mapLayer( layerID ) ) )
layers << vl;
layers << qMakePair( vl, aoi );
prepareIndex( layers );

QgsPointLocator::MatchList edges; // for snap on intersection
QgsPointLocator::Match bestMatch;

Q_FOREACH ( QgsVectorLayer* vl, layers )
Q_FOREACH ( const LayerAndAreaOfInterest& entry, layers )
{
QgsVectorLayer* vl = entry.first;
if ( QgsPointLocator* loc = locatorForLayerUsingStrategy( vl, pointMap, tolerance ) )
{
_updateBestMatch( bestMatch, pointMap, loc, type, tolerance, filter );
Expand All @@ -307,18 +319,22 @@ QgsPointLocator::Match QgsSnappingUtils::snapToMap( const QgsPoint& pointMap, Qg
}


void QgsSnappingUtils::prepareIndex( const QList<QgsVectorLayer*>& layers )
void QgsSnappingUtils::prepareIndex( const QList<LayerAndAreaOfInterest>& layers )
{
if ( mIsIndexing )
return;
mIsIndexing = true;

// check if we need to build any index
QList<QgsVectorLayer*> layersToIndex;
Q_FOREACH ( QgsVectorLayer* vl, layers )
QList<LayerAndAreaOfInterest> layersToIndex;
Q_FOREACH ( const LayerAndAreaOfInterest& entry, layers )
{
if ( willUseIndex( vl ) && !locatorForLayer( vl )->hasIndex() )
layersToIndex << vl;
QgsVectorLayer* vl = entry.first;
if ( vl->geometryType() == QGis::NoGeometry || mStrategy == IndexNeverFull )
continue;

if ( !isIndexPrepared( vl, entry.second ) )
layersToIndex << entry;
}
if ( !layersToIndex.isEmpty() )
{
Expand All @@ -327,12 +343,61 @@ void QgsSnappingUtils::prepareIndex( const QList<QgsVectorLayer*>& layers )
t.start();
int i = 0;
prepareIndexStarting( layersToIndex.count() );
Q_FOREACH ( QgsVectorLayer* vl, layersToIndex )
Q_FOREACH ( const LayerAndAreaOfInterest& entry, layersToIndex )
{
QgsVectorLayer* vl = entry.first;
QTime tt;
tt.start();
if ( !locatorForLayer( vl )->init( mStrategy == IndexHybrid ? 1000000 : -1 ) )
mHybridNonindexableLayers.insert( vl->id() );
QgsPointLocator* loc = locatorForLayer( vl );
if ( mStrategy == IndexHybrid )
{
// first time the layer is used? - let's set an initial guess about indexing
if ( !mHybridMaxAreaPerLayer.contains( vl->id() ) )
{
int totalFeatureCount = vl->pendingFeatureCount();
if ( totalFeatureCount < mHybridPerLayerFeatureLimit )
{
// index the whole layer
mHybridMaxAreaPerLayer[vl->id()] = -1;
}
else
{
// estimate for how big area it probably makes sense to build partial index to not exceed the limit
// (we may change the limit later)
QgsRectangle layerExtent = mMapSettings.layerExtentToOutputExtent( vl, vl->extent() );
double totalArea = layerExtent.width() * layerExtent.height();
mHybridMaxAreaPerLayer[vl->id()] = totalArea * mHybridPerLayerFeatureLimit / totalFeatureCount / 4;
}
}

double indexReasonableArea = mHybridMaxAreaPerLayer[vl->id()];
if ( indexReasonableArea == -1 )
{
// we can safely index the whole layer
loc->init();
}
else
{
// use area as big as we think may fit into our limit
QgsPoint c = entry.second.center();
double halfSide = sqrt( indexReasonableArea ) / 2;
QgsRectangle rect( c.x() - halfSide, c.y() - halfSide,
c.x() + halfSide, c.y() + halfSide );
loc->setExtent( &rect );

// see if it's possible build index for this area
if ( !loc->init( mHybridPerLayerFeatureLimit ) )
{
// hmm that didn't work out - too many features!
// let's make the allowed area smaller for the next time
mHybridMaxAreaPerLayer[vl->id()] /= 4;
}
}

}
else // full index strategy
loc->init();

QgsDebugMsg( QString( "Index init: %1 ms (%2)" ).arg( tt.elapsed() ).arg( vl->id() ) );
prepareIndexProgress( ++i );
}
Expand Down Expand Up @@ -463,28 +528,38 @@ QString QgsSnappingUtils::dump()

Q_FOREACH ( const LayerConfig& layer, layers )
{
bool usingIndex = willUseIndex( layer.layer );

msg += QString( "layer : %1\n"
"config: %2 tolerance %3 %4\n" )
.arg( layer.layer->name() )
.arg( layer.type ).arg( layer.tolerance ).arg( layer.unit );

if ( usingIndex )
if ( mStrategy == IndexAlwaysFull || mStrategy == IndexHybrid )
{
QgsPointLocator* loc = locatorForLayer( layer.layer );
if ( loc )
if ( QgsPointLocator* loc = locatorForLayer( layer.layer ) )
{
QString extentStr, cachedGeoms;
QString extentStr, cachedGeoms, limit( "no max area" );
if ( const QgsRectangle* r = loc->extent() )
extentStr = " extent = " + r->toString();
{
extentStr = QString( " extent %1" ).arg( r->toString() );
}
else
extentStr = "full extent";
if ( loc->hasIndex() )
cachedGeoms = QString( "%1 feats" ).arg( loc->cachedGeometryCount() );
else
cachedGeoms = "not initialized";
msg += QString( "index : YES | %1 | %2\n" ).arg( cachedGeoms ).arg( extentStr );
if ( mStrategy == IndexHybrid )
{
if ( mHybridMaxAreaPerLayer.contains( layer.layer->id() ) )
{
double maxArea = mStrategy == IndexHybrid ? mHybridMaxAreaPerLayer[layer.layer->id()] : -1;
if ( maxArea != -1 )
limit = QString( "max area %1" ).arg( maxArea );
}
else
limit = "not evaluated";
}
msg += QString( "index : YES | %1 | %2 | %3\n" ).arg( cachedGeoms ).arg( extentStr ).arg( limit );
}
else
msg += QString( "index : ???\n" ); // should not happen
Expand Down Expand Up @@ -585,8 +660,8 @@ void QgsSnappingUtils::onLayersWillBeRemoved( const QStringList& layerIds )
// remove locators for layers that are going to be deleted
Q_FOREACH ( const QString& layerId, layerIds )
{
if ( mHybridNonindexableLayers.contains( layerId ) )
mHybridNonindexableLayers.remove( layerId );
if ( mHybridMaxAreaPerLayer.contains( layerId ) )
mHybridMaxAreaPerLayer.remove( layerId );

for ( LocatorsMap::iterator it = mLocators.begin(); it != mLocators.end(); )
{
Expand Down
17 changes: 15 additions & 2 deletions src/core/qgssnappingutils.h
View file
Expand Up @@ -172,10 +172,12 @@ 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 );

typedef QPair< QgsVectorLayer*, QgsRectangle > LayerAndAreaOfInterest;

//! find out whether the strategy would index such layer or just use a temporary locator
bool willUseIndex( QgsVectorLayer* vl ) const;
bool isIndexPrepared( QgsVectorLayer* vl, const QgsRectangle& areaOfInterest );
//! initialize index for layers where it makes sense (according to the indexing strategy)
void prepareIndex( const QList<QgsVectorLayer*>& layers );
void prepareIndex( const QList<LayerAndAreaOfInterest>& layers );

private:
// environment
Expand All @@ -199,6 +201,17 @@ class CORE_EXPORT QgsSnappingUtils : public QObject
LocatorsMap mTemporaryLocators;
//! list of layer IDs that are too large to be indexed (hybrid strategy will use temporary locators for those)
QSet<QString> mHybridNonindexableLayers;
//! a record for each layer seen:
//! - value -1 == it is small layer -> fully indexed
//! - value > 0 == maximum area (in map units) for which it may make sense to build index.
//! This means that index is built in area around the point with this total area, because
//! for a larger area the number of features will likely exceed the limit. When the limit
//! is exceeded, the maximum area is lowered to prevent that from happening.
//! When requesting snap in area that is not currently indexed, layer's index is destroyed
//! and a new one is built in the different area.
QHash<QString, double> mHybridMaxAreaPerLayer;
//! if using hybrid strategy, how many features of one layer may be indexed (to limit amount of consumed memory)
int mHybridPerLayerFeatureLimit;

//! internal flag that an indexing process is going on. Prevents starting two processes in parallel.
bool mIsIndexing;
Expand Down

0 comments on commit fa66583

Please sign in to comment.