Branch data     Line data    Source code

       1                 :            : /***************************************************************************
       2                 :            :                          qgsalgorithmdeleteduplicategeometries.cpp
       3                 :            :                          -----------------------------------------
       4                 :            :     begin                : December 2019
       5                 :            :     copyright            : (C) 2019 by Nyall Dawson
       6                 :            :     email                : nyall dot dawson at gmail dot com
       7                 :            :  ***************************************************************************/
       8                 :            : 
       9                 :            : /***************************************************************************
      10                 :            :  *                                                                         *
      11                 :            :  *   This program is free software; you can redistribute it and/or modify  *
      12                 :            :  *   it under the terms of the GNU General Public License as published by  *
      13                 :            :  *   the Free Software Foundation; either version 2 of the License, or     *
      14                 :            :  *   (at your option) any later version.                                   *
      15                 :            :  *                                                                         *
      16                 :            :  ***************************************************************************/
      17                 :            : 
      18                 :            : #include "qgsalgorithmdeleteduplicategeometries.h"
      19                 :            : #include "qgsvectorlayer.h"
      20                 :            : #include "qgsgeometryengine.h"
      21                 :            : 
      22                 :            : ///@cond PRIVATE
      23                 :            : 
      24                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::name() const
      25                 :            : {
      26                 :          0 :   return QStringLiteral( "deleteduplicategeometries" );
      27                 :            : }
      28                 :            : 
      29                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::displayName() const
      30                 :            : {
      31                 :          0 :   return QObject::tr( "Delete duplicate geometries" );
      32                 :            : }
      33                 :            : 
      34                 :          0 : QStringList QgsDeleteDuplicateGeometriesAlgorithm::tags() const
      35                 :            : {
      36                 :          0 :   return QObject::tr( "drop,remove,same,points,coincident,overlapping,filter" ).split( ',' );
      37                 :          0 : }
      38                 :            : 
      39                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::group() const
      40                 :            : {
      41                 :          0 :   return QObject::tr( "Vector general" );
      42                 :            : }
      43                 :            : 
      44                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::groupId() const
      45                 :            : {
      46                 :          0 :   return QStringLiteral( "vectorgeneral" );
      47                 :            : }
      48                 :            : 
      49                 :          0 : void QgsDeleteDuplicateGeometriesAlgorithm::initAlgorithm( const QVariantMap & )
      50                 :            : {
      51                 :          0 :   addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "INPUT" ), QObject::tr( "Input layer" ) ) );
      52                 :          0 :   addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Cleaned" ) ) );
      53                 :          0 :   addOutput( new QgsProcessingOutputNumber( QStringLiteral( "RETAINED_COUNT" ), QObject::tr( "Count of retained records" ) ) );
      54                 :          0 :   addOutput( new QgsProcessingOutputNumber( QStringLiteral( "DUPLICATE_COUNT" ), QObject::tr( "Count of discarded duplicate records" ) ) );
      55                 :          0 : }
      56                 :            : 
      57                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::shortHelpString() const
      58                 :            : {
      59                 :          0 :   return QObject::tr( "This algorithm finds duplicated geometries and removes them.\n\nAttributes are not checked, "
      60                 :            :                       "so in case two features have identical geometries but different attributes, only one of "
      61                 :            :                       "them will be added to the result layer." );
      62                 :            : }
      63                 :            : 
      64                 :          0 : QString QgsDeleteDuplicateGeometriesAlgorithm::shortDescription() const
      65                 :            : {
      66                 :          0 :   return QObject::tr( "Finds duplicated geometries in a layer and removes them." );
      67                 :            : }
      68                 :            : 
      69                 :          0 : QgsDeleteDuplicateGeometriesAlgorithm *QgsDeleteDuplicateGeometriesAlgorithm::createInstance() const
      70                 :            : {
      71                 :          0 :   return new QgsDeleteDuplicateGeometriesAlgorithm();
      72                 :            : }
      73                 :            : 
      74                 :          0 : bool QgsDeleteDuplicateGeometriesAlgorithm::prepareAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback * )
      75                 :            : {
      76                 :          0 :   mSource.reset( parameterAsSource( parameters, QStringLiteral( "INPUT" ), context ) );
      77                 :          0 :   if ( !mSource )
      78                 :          0 :     throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "INPUT" ) ) );
      79                 :            : 
      80                 :          0 :   return true;
      81                 :          0 : }
      82                 :            : 
      83                 :          0 : QVariantMap QgsDeleteDuplicateGeometriesAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
      84                 :            : {
      85                 :          0 :   QString destId;
      86                 :          0 :   std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, destId, mSource->fields(),
      87                 :          0 :                                           mSource->wkbType(), mSource->sourceCrs() ) );
      88                 :          0 :   if ( !sink )
      89                 :          0 :     throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
      90                 :            : 
      91                 :          0 :   QgsFeatureIterator it = mSource->getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QgsAttributeList() ) );
      92                 :            : 
      93                 :          0 :   double step = mSource->featureCount() > 0 ? 100.0 / mSource->featureCount() : 0;
      94                 :          0 :   QHash< QgsFeatureId, QgsGeometry > geometries;
      95                 :          0 :   QSet< QgsFeatureId > nullGeometryFeatures;
      96                 :          0 :   long current = 0;
      97                 :          0 :   QgsSpatialIndex index( it, [&]( const QgsFeature & f ) ->bool
      98                 :            :   {
      99                 :          0 :     if ( feedback->isCanceled() )
     100                 :          0 :       return false;
     101                 :            : 
     102                 :          0 :     if ( !f.hasGeometry() )
     103                 :            :     {
     104                 :          0 :       nullGeometryFeatures.insert( f.id() );
     105                 :          0 :     }
     106                 :            :     else
     107                 :            :     {
     108                 :          0 :       geometries.insert( f.id(), f.geometry() );
     109                 :            :     }
     110                 :            : 
     111                 :            :     // overall this loop takes about 10% of time
     112                 :          0 :     current++;
     113                 :          0 :     feedback->setProgress( 0.10 * current * step );
     114                 :          0 :     return true;
     115                 :          0 :   } );
     116                 :            : 
     117                 :          0 :   QgsFeature f;
     118                 :            : 
     119                 :            :   // start by assuming everything is unique, and chop away at this list
     120                 :          0 :   QHash< QgsFeatureId, QgsGeometry > uniqueFeatures = geometries;
     121                 :          0 :   current = 0;
     122                 :          0 :   long removed = 0;
     123                 :            : 
     124                 :          0 :   for ( auto it = geometries.constBegin(); it != geometries.constEnd(); ++it )
     125                 :            :   {
     126                 :          0 :     const QgsFeatureId featureId = it.key();
     127                 :          0 :     const QgsGeometry geometry = it.value();
     128                 :            : 
     129                 :          0 :     if ( feedback->isCanceled() )
     130                 :          0 :       break;
     131                 :            : 
     132                 :          0 :     if ( !uniqueFeatures.contains( featureId ) )
     133                 :            :     {
     134                 :            :       // feature was already marked as a duplicate
     135                 :          0 :     }
     136                 :            :     else
     137                 :            :     {
     138                 :          0 :       const QList<QgsFeatureId> candidates = index.intersects( geometry.boundingBox() );
     139                 :            : 
     140                 :          0 :       for ( const QgsFeatureId candidateId : candidates )
     141                 :            :       {
     142                 :          0 :         if ( candidateId == featureId )
     143                 :          0 :           continue;
     144                 :            : 
     145                 :          0 :         if ( !uniqueFeatures.contains( candidateId ) )
     146                 :            :         {
     147                 :            :           // candidate already marked as a duplicate (not sure if this is possible,
     148                 :            :           // since it would mean the current feature would also have to be a duplicate!
     149                 :            :           // but let's be safe!)
     150                 :          0 :           continue;
     151                 :            :         }
     152                 :          0 :         else if ( geometry.isGeosEqual( geometries.value( candidateId ) ) )
     153                 :            :         {
     154                 :            :           // candidate is a duplicate of feature
     155                 :          0 :           uniqueFeatures.remove( candidateId );
     156                 :          0 :           removed++;
     157                 :          0 :         }
     158                 :            :       }
     159                 :          0 :     }
     160                 :            : 
     161                 :          0 :     current++;
     162                 :          0 :     feedback->setProgress( 0.80 * current * step + 10 ); // takes about 80% of time
     163                 :          0 :   }
     164                 :            : 
     165                 :            :   // now, fetch all the feature attributes for the unique features only
     166                 :            :   // be super-smart and don't re-fetch geometries
     167                 :          0 :   QSet< QgsFeatureId > outputFeatureIds = qgis::listToSet( uniqueFeatures.keys() );
     168                 :          0 :   outputFeatureIds.unite( nullGeometryFeatures );
     169                 :          0 :   step = outputFeatureIds.empty() ? 1 : 100.0 / outputFeatureIds.size();
     170                 :            : 
     171                 :          0 :   QgsFeatureRequest request = QgsFeatureRequest().setFilterFids( outputFeatureIds ).setFlags( QgsFeatureRequest::NoGeometry );
     172                 :          0 :   it = mSource->getFeatures( request );
     173                 :          0 :   current = 0;
     174                 :          0 :   while ( it.nextFeature( f ) )
     175                 :            :   {
     176                 :          0 :     if ( feedback->isCanceled() )
     177                 :          0 :       break;
     178                 :            : 
     179                 :            :     // use already fetched geometry
     180                 :          0 :     if ( !nullGeometryFeatures.contains( f.id() ) )
     181                 :            :     {
     182                 :          0 :       f.setGeometry( uniqueFeatures.value( f.id() ) );
     183                 :          0 :     }
     184                 :          0 :     sink->addFeature( f, QgsFeatureSink::FastInsert );
     185                 :            : 
     186                 :          0 :     current++;
     187                 :          0 :     feedback->setProgress( 0.10 * current * step + 90 ); // takes about 10% of time
     188                 :            :   }
     189                 :            : 
     190                 :          0 :   feedback->pushInfo( QObject::tr( "%1 duplicate features removed" ).arg( removed ) );
     191                 :            : 
     192                 :          0 :   QVariantMap outputs;
     193                 :          0 :   outputs.insert( QStringLiteral( "OUTPUT" ), destId );
     194                 :          0 :   outputs.insert( QStringLiteral( "DUPLICATE_COUNT" ), static_cast< long long >( removed ) );
     195                 :          0 :   outputs.insert( QStringLiteral( "RETAINED_COUNT" ), outputFeatureIds.size() );
     196                 :          0 :   return outputs;
     197                 :          0 : }
     198                 :            : 
     199                 :            : ///@endcond