[pal] Optimise checks of conflicts between curved label candidates

qgis · Apr 5, 2021 · 9cabb1c · 9cabb1c
1 parent 6e46fa7
commit 9cabb1c
Show file tree

Hide file tree

Showing 4 changed files with 94 additions and 35 deletions.
diff --git a/src/core/pal/labelposition.cpp b/src/core/pal/labelposition.cpp
@@ -268,29 +268,29 @@ bool LabelPosition::isInConflict( const LabelPosition *lp ) const
     return false; // always overlaping itself !
 
   if ( !nextPart() && !lp->nextPart() )
-    return isInConflictSinglePart( lp );
-  else
-    return isInConflictMultiPart( lp );
-}
-
-bool LabelPosition::isInConflictSinglePart( const LabelPosition *lp ) const
-{
-  if ( qgsDoubleNear( alpha, 0 ) && qgsDoubleNear( lp->alpha, 0 ) )
   {
-    // simple case -- both candidates are oriented to axis, so shortcut with easy calculation
-    return boundingBoxIntersects( lp );
+    if ( qgsDoubleNear( alpha, 0 ) && qgsDoubleNear( lp->alpha, 0 ) )
+    {
+      // simple case -- both candidates are oriented to axis, so shortcut with easy calculation
+      return boundingBoxIntersects( lp );
+    }
   }
 
-  if ( !mGeos )
-    createGeosGeom();
+  return isInConflictMultiPart( lp );
+}
+
+bool LabelPosition::isInConflictMultiPart( const LabelPosition *lp ) const
+{
+  if ( !mMultipartGeos )
+    createMultiPartGeosGeom();
 
-  if ( !lp->mGeos )
-    lp->createGeosGeom();
+  if ( !lp->mMultipartGeos )
+    lp->createMultiPartGeosGeom();
 
   GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
   try
   {
-    bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
+    bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedMultiPartGeom(), lp->mMultipartGeos ) == 1 );
     return result;
   }
   catch ( GEOSException &e )
@@ -299,26 +299,8 @@ bool LabelPosition::isInConflictSinglePart( const LabelPosition *lp ) const
     QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
     return false;
   }
-}
 
-bool LabelPosition::isInConflictMultiPart( const LabelPosition *lp ) const
-{
-  // check all parts against all parts of other one
-  const LabelPosition *tmp1 = this;
-  while ( tmp1 )
-  {
-    // check tmp1 against parts of other label
-    const LabelPosition *tmp2 = lp;
-    while ( tmp2 )
-    {
-      if ( tmp1->isInConflictSinglePart( tmp2 ) )
-        return true;
-      tmp2 = tmp2->nextPart();
-    }
-
-    tmp1 = tmp1->nextPart();
-  }
-  return false; // no conflict found
+  return false;
 }
 
 int LabelPosition::partCount() const
@@ -432,6 +414,45 @@ void LabelPosition::insertIntoIndex( PalRtree<LabelPosition> &index )
   index.insert( this, QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
 }
 
+
+void LabelPosition::createMultiPartGeosGeom() const
+{
+  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
+
+  std::vector< const GEOSGeometry * > geometries;
+  const LabelPosition *tmp1 = this;
+  while ( tmp1 )
+  {
+    const GEOSGeometry *partGeos = tmp1->geos();
+    if ( !GEOSisEmpty_r( geosctxt, partGeos ) )
+      geometries.emplace_back( partGeos );
+    tmp1 = tmp1->nextPart();
+  }
+
+  const std::size_t partCount = geometries.size();
+  GEOSGeometry **geomarr = new GEOSGeometry*[ partCount ];
+  for ( std::size_t i = 0; i < partCount; ++i )
+  {
+    geomarr[i ] = GEOSGeom_clone_r( geosctxt, geometries[i] );
+  }
+
+  mMultipartGeos = GEOSGeom_createCollection_r( geosctxt, GEOS_MULTIPOLYGON, geomarr, partCount );
+  delete [] geomarr;
+}
+
+const GEOSPreparedGeometry *LabelPosition::preparedMultiPartGeom() const
+{
+  if ( !mMultipartGeos )
+    createMultiPartGeosGeom();
+
+  if ( !mMultipartPreparedGeos )
+  {
+    mMultipartPreparedGeos = GEOSPrepare_r( QgsGeos::getGEOSHandler(), mMultipartGeos );
+  }
+  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
@@ -303,6 +303,13 @@ namespace pal
        */
       void insertIntoIndex( PalRtree<LabelPosition> &index );
 
+      /**
+       * Returns a prepared GEOS representation of all label parts as a multipolygon.
+       *
+       * \since QGIS 3.20
+       */
+      const GEOSPreparedGeometry *preparedMultiPartGeom() const;
+
     protected:
 
       int id;
@@ -349,7 +356,11 @@ namespace pal
        */
       double polygonIntersectionCostForParts( PointSet *polygon ) const;
 
-      bool isInConflictSinglePart( const LabelPosition *lp ) const;
+      /**
+       * Creates a GEOS representation of all label parts as a multipolygon.
+       */
+      void createMultiPartGeosGeom() const;
+
       bool isInConflictMultiPart( const LabelPosition *lp ) const;
 
       LabelPosition &operator=( const LabelPosition & ) = delete;

diff --git a/src/core/pal/pointset.cpp b/src/core/pal/pointset.cpp
@@ -172,6 +172,18 @@ void PointSet::invalidateGeos()
     GEOSPreparedGeom_destroy_r( geosctxt, mGeosPreparedBoundary );
     mGeosPreparedBoundary = nullptr;
   }
+
+  if ( mMultipartPreparedGeos )
+  {
+    GEOSPreparedGeom_destroy_r( geosctxt, mMultipartPreparedGeos );
+    mMultipartPreparedGeos = nullptr;
+  }
+  if ( mMultipartGeos )
+  {
+    GEOSGeom_destroy_r( geosctxt, mMultipartGeos );
+    mMultipartGeos = nullptr;
+  }
+
   mPreparedGeom = nullptr;
   mLength = -1;
   mArea = -1;
@@ -194,6 +206,17 @@ PointSet::~PointSet()
     mGeosPreparedBoundary = nullptr;
   }
 
+  if ( mMultipartPreparedGeos )
+  {
+    GEOSPreparedGeom_destroy_r( geosctxt, mMultipartPreparedGeos );
+    mMultipartPreparedGeos = nullptr;
+  }
+  if ( mMultipartGeos )
+  {
+    GEOSGeom_destroy_r( geosctxt, mMultipartGeos );
+    mMultipartGeos = nullptr;
+  }
+
   deleteCoords();
 }
 

diff --git a/src/core/pal/pointset.h b/src/core/pal/pointset.h
@@ -231,6 +231,7 @@ namespace pal
       void deleteCoords();
       void createGeosGeom() const;
       const GEOSPreparedGeometry *preparedGeom() const;
+
       void invalidateGeos();
 
       double xmin = std::numeric_limits<double>::max();
@@ -243,6 +244,9 @@ namespace pal
       mutable const GEOSPreparedGeometry *mGeosPreparedBoundary = nullptr;
       mutable const GEOSPreparedGeometry *mPreparedGeom = nullptr;
 
+      mutable GEOSGeometry *mMultipartGeos = nullptr;
+      mutable const GEOSPreparedGeometry *mMultipartPreparedGeos = nullptr;
+
       PointSet &operator= ( const PointSet & ) = delete;
 
   };