[pal] Cache results of determining whether two label candidates

conflict This can be costly to calculate, and during the labeling solution we regularly test the same pair of label candidates for conflicts multiple times. By caching the first result we gain a big speed bump for complex labeling problems.
qgis · Apr 7, 2021 · 86334fc · 86334fc
1 parent 0c0a9e5
commit 86334fc
Show file tree

Hide file tree

Showing 6 changed files with 72 additions and 16 deletions.
diff --git a/src/core/pal/labelposition.cpp b/src/core/pal/labelposition.cpp
@@ -452,7 +452,6 @@ const GEOSPreparedGeometry *LabelPosition::preparedMultiPartGeom() const
   return mMultipartPreparedGeos;
 }
 
-
 double LabelPosition::getDistanceToPoint( double xp, double yp ) const
 {
   //first check if inside, if so then distance is -1

diff --git a/src/core/pal/labelposition.h b/src/core/pal/labelposition.h
@@ -310,6 +310,24 @@ namespace pal
        */
       const GEOSPreparedGeometry *preparedMultiPartGeom() const;
 
+      /**
+       * Returns the global ID for the candidate, which is unique for a single run of the pal
+       * labelling engine.
+       *
+       * A return value of 0 means that the ID has not been assigned.
+       *
+       * \see setGlobalId()
+       */
+      long long globalId() const { return mGlobalId; }
+
+      /**
+       * Sets the global \a id for the candidate, which is unique for a single run of the pal
+       * labelling engine.
+       *
+       * \see globalId()
+       */
+      void setGlobalId( long long id ) { mGlobalId = id; }
+
     protected:
 
       int id;
@@ -338,6 +356,7 @@ namespace pal
 
     private:
 
+      long long mGlobalId = 0;
       std::unique_ptr< LabelPosition > mNextPart;
 
       double mCost;

diff --git a/src/core/pal/pal.cpp b/src/core/pal/pal.cpp
@@ -197,6 +197,7 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
         for ( std::unique_ptr< LabelPosition > &candidate : candidates )
         {
           candidate->insertIntoIndex( allCandidatesFirstRound );
+          candidate->setGlobalId( mNextCandidateId++ );
         }
 
         std::sort( candidates.begin(), candidates.end(), CostCalculator::candidateSortGrow );
@@ -220,6 +221,7 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
         {
           // if we are displaying all labels, we throw the default candidate in too
           unplacedPosition->insertIntoIndex( allCandidatesFirstRound );
+          unplacedPosition->setGlobalId( mNextCandidateId++ );
           candidates.emplace_back( std::move( unplacedPosition ) );
 
           // valid features are added to fFeats
@@ -445,9 +447,9 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
 
         // lookup for overlapping candidate
         lp->getBoundingBox( amin, amax );
-        prob->allCandidatesIndex().intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp]( const LabelPosition * lp2 )->bool
+        prob->allCandidatesIndex().intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
         {
-          if ( lp->isInConflict( lp2 ) )
+          if ( candidatesAreConflicting( lp.get(), lp2 ) )
           {
             lp->incrementNumOverlaps();
           }
@@ -550,6 +552,22 @@ void Pal::setPlacementVersion( QgsLabelingEngineSettings::PlacementEngineVersion
   mPlacementVersion = placementVersion;
 }
 
+bool Pal::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
+{
+  // we cache the value -- this can be costly to calculate, and we check this multiple times
+  // per candidate during the labeling problem solving
+
+  // conflicts are commutative - so we always store them in the cache using the smaller id as the first element of the key pair
+  auto key = qMakePair( std::min( lp1->globalId(), lp2->globalId() ), std::max( lp1->globalId(), lp2->globalId() ) );
+  auto it = mCandidateConflicts.constFind( key );
+  if ( it != mCandidateConflicts.constEnd() )
+    return *it;
+
+  const bool res = lp1->isInConflict( lp2 );
+  mCandidateConflicts.insert( key, res );
+  return res;
+}
+
 int Pal::getMinIt()
 {
   return mTabuMaxIt;

diff --git a/src/core/pal/pal.h b/src/core/pal/pal.h
@@ -241,6 +241,11 @@ namespace pal
        */
       int globalCandidatesLimitPolygon() const { return mGlobalCandidatesLimitPolygon; }
 
+      /**
+       * Returns TRUE if a labelling candidate \a lp1 conflicts with \a lp2.
+       */
+      bool candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const;
+
     private:
 
       std::unordered_map< QgsAbstractLabelProvider *, std::unique_ptr< Layer > > mLayers;
@@ -259,6 +264,9 @@ namespace pal
       int mTenure = 10;
       double mCandListSize = 0.2;
 
+      long long mNextCandidateId = 1;
+      mutable QHash< QPair< long long, long long >, bool > mCandidateConflicts;
+
       /**
        * \brief show partial labels (cut-off by the map canvas) or not
        */

diff --git a/src/core/pal/problem.cpp b/src/core/pal/problem.cpp
@@ -112,9 +112,9 @@ void Problem::reduce()
               lp2->getBoundingBox( amin, amax );
 
               mNbOverlap -= lp2->getNumOverlaps();
-              mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2]( const LabelPosition * lp ) -> bool
+              mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2, this]( const LabelPosition * lp ) -> bool
               {
-                if ( lp2->isInConflict( lp ) )
+                if ( candidatesAreConflicting( lp2, lp ) )
                 {
                   const_cast< LabelPosition * >( lp )->decrementNumOverlaps();
                   lp2->decrementNumOverlaps();
@@ -137,7 +137,7 @@ void Problem::reduce()
   delete[] ok;
 }
 
-void ignoreLabel( const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelPosition > &candidatesIndex )
+void Problem::ignoreLabel( const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelPosition > &candidatesIndex )
 {
   if ( list.isIn( lp->getId() ) )
   {
@@ -146,9 +146,9 @@ void ignoreLabel( const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelP
     double amin[2];
     double amax[2];
     lp->getBoundingBox( amin, amax );
-    candidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &list]( const LabelPosition * lp2 )->bool
+    candidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &list, this]( const LabelPosition * lp2 )->bool
     {
-      if ( lp2->getId() != lp->getId() && list.isIn( lp2->getId() ) && lp2->isInConflict( lp ) )
+      if ( lp2->getId() != lp->getId() && list.isIn( lp2->getId() ) && candidatesAreConflicting( lp2, lp ) )
       {
         list.decreaseKey( lp2->getId() );
       }
@@ -215,9 +215,9 @@ void Problem::init_sol_falp()
     lp->getBoundingBox( amin, amax );
 
     std::vector< const LabelPosition * > conflictingPositions;
-    mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions]( const LabelPosition * lp2 ) ->bool
+    mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions, this]( const LabelPosition * lp2 ) ->bool
     {
-      if ( lp->isInConflict( lp2 ) )
+      if ( candidatesAreConflicting( lp, lp2 ) )
       {
         conflictingPositions.emplace_back( lp2 );
       }
@@ -253,9 +253,9 @@ void Problem::init_sol_falp()
           lp->getBoundingBox( amin, amax );
 
 
-          mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp]( const LabelPosition * lp2 )->bool
+          mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
           {
-            if ( lp->isInConflict( lp2 ) )
+            if ( candidatesAreConflicting( lp, lp2 ) )
             {
               lp->incrementNumOverlaps();
             }
@@ -277,6 +277,11 @@ void Problem::init_sol_falp()
   }
 }
 
+bool Problem::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
+{
+  return  pal->candidatesAreConflicting( lp1, lp2 );
+}
+
 inline Chain *Problem::chain( int seed )
 {
   int lid;
@@ -338,7 +343,7 @@ inline Chain *Problem::chain( int seed )
             lp->getBoundingBox( amin, amax );
             mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, &currentChain, this]( const LabelPosition * lp2 ) -> bool
             {
-              if ( lp2->isInConflict( lp ) )
+              if ( candidatesAreConflicting( lp2, lp ) )
               {
                 const int feat = lp2->getProblemFeatureId();
 
@@ -618,9 +623,9 @@ void Problem::chain_search()
           LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
           old->removeFromIndex( mActiveCandidatesIndex );
           old->getBoundingBox( amin, amax );
-          mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old]( const LabelPosition * lp ) ->bool
+          mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old, this]( const LabelPosition * lp ) ->bool
           {
-            if ( old->isInConflict( lp ) )
+            if ( candidatesAreConflicting( old, lp ) )
             {
               ok[lp->getProblemFeatureId()] = false;
             }
@@ -717,7 +722,7 @@ void Problem::solution_cost()
       lp->getBoundingBox( amin, amax );
       mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
       {
-        if ( lp->isInConflict( lp2 ) )
+        if ( candidatesAreConflicting( lp, lp2 ) )
         {
           mSol.totalCost += mInactiveCost[lp2->getProblemFeatureId()] + lp2->cost();
         }

diff --git a/src/core/pal/problem.h b/src/core/pal/problem.h
@@ -45,6 +45,7 @@ namespace pal
 
   class LabelPosition;
   class Label;
+  class PriorityQueue;
 
   /**
    * \class pal::Sol
@@ -155,6 +156,11 @@ namespace pal
 
     private:
 
+      /**
+       * Returns TRUE if a labelling candidate \a lp1 conflicts with \a lp2.
+       */
+      bool candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const;
+
       /**
        * Total number of layers containing labels
        */
@@ -225,6 +231,7 @@ namespace pal
       Pal *pal = nullptr;
 
       void solution_cost();
+      void ignoreLabel( const LabelPosition *lp, pal::PriorityQueue &list, PalRtree<LabelPosition> &candidatesIndex );
   };
 
 } // namespace