Branch data     Line data    Source code

       1                 :            : /***************************************************************************
       2                 :            :   qgsgenericspatialindex.h
       3                 :            :   ------------------------
       4                 :            :   Date                 : December 2019
       5                 :            :   Copyright            : (C) 2019 by Nyall Dawson
       6                 :            :   Email                : nyall dot dawson at gmail dot com
       7                 :            :  ***************************************************************************
       8                 :            :  *                                                                         *
       9                 :            :  *   This program is free software; you can redistribute it and/or modify  *
      10                 :            :  *   it under the terms of the GNU General Public License as published by  *
      11                 :            :  *   the Free Software Foundation; either version 2 of the License, or     *
      12                 :            :  *   (at your option) any later version.                                   *
      13                 :            :  *                                                                         *
      14                 :            :  ***************************************************************************/
      15                 :            : 
      16                 :            : #ifndef QGSGENERICSPATIALINDEX_H
      17                 :            : #define QGSGENERICSPATIALINDEX_H
      18                 :            : 
      19                 :            : #include "qgis_core.h"
      20                 :            : #include "qgsspatialindexutils.h"
      21                 :            : #include "qgslogger.h"
      22                 :            : 
      23                 :            : #include <memory>
      24                 :            : #include <QMutex>
      25                 :            : #include <QString>
      26                 :            : 
      27                 :            : #define SIP_NO_FILE
      28                 :            : 
      29                 :            : #include <functional>
      30                 :            : #include <spatialindex/SpatialIndex.h>
      31                 :            : 
      32                 :            : class QgsRectangle;
      33                 :            : 
      34                 :            : /**
      35                 :            :  * \ingroup core
      36                 :            :  * \class QgsGenericSpatialIndex
      37                 :            :  *
      38                 :            :  * \brief A generic rtree spatial index based on a libspatialindex backend.
      39                 :            :  *
      40                 :            :  * \note Not available in Python bindings.
      41                 :            :  * \since QGIS 3.12
      42                 :            :  */
      43                 :            : template <typename T>
      44                 :          0 : class QgsGenericSpatialIndex
      45                 :            : {
      46                 :            :   public:
      47                 :            : 
      48                 :            :     /**
      49                 :            :      * Constructor for QgsGenericSpatialIndex.
      50                 :            :      */
      51                 :          0 :     QgsGenericSpatialIndex()
      52                 :            :     {
      53                 :          0 :       mStorageManager.reset( SpatialIndex::StorageManager::createNewMemoryStorageManager() );
      54                 :          0 :       mRTree = createSpatialIndex( *mStorageManager );
      55                 :          0 :     }
      56                 :            : 
      57                 :            :     /**
      58                 :            :      * Inserts new \a data into the spatial index, with the specified \a bounds.
      59                 :            :      *
      60                 :            :      * Ownership of \a data is not transferred, and it is the caller's responsibility to ensure that
      61                 :            :      * it exists for the lifetime of the spatial index.
      62                 :            :      */
      63                 :          0 :     bool insert( T *data, const QgsRectangle &bounds )
      64                 :            :     {
      65                 :          0 :       SpatialIndex::Region r( QgsSpatialIndexUtils::rectangleToRegion( bounds ) );
      66                 :            : 
      67                 :          0 :       QMutexLocker locker( &mMutex );
      68                 :            : 
      69                 :          0 :       qint64 id = mNextId++;
      70                 :          0 :       mIdToData.insert( id, data );
      71                 :          0 :       mDataToId.insert( data, id );
      72                 :            :       try
      73                 :            :       {
      74                 :          0 :         mRTree->insertData( 0, nullptr, r, static_cast< qint64 >( id ) );
      75                 :          0 :         return true;
      76                 :          0 :       }
      77                 :            :       catch ( Tools::Exception &e )
      78                 :            :       {
      79                 :          0 :         Q_UNUSED( e )
      80                 :          0 :         QgsDebugMsg( QStringLiteral( "Tools::Exception caught: " ).arg( e.what().c_str() ) );
      81                 :          0 :       }
      82                 :            :       catch ( const std::exception &e )
      83                 :            :       {
      84                 :          0 :         Q_UNUSED( e )
      85                 :          0 :         QgsDebugMsg( QStringLiteral( "std::exception caught: " ).arg( e.what() ) );
      86                 :          0 :       }
      87                 :            :       catch ( ... )
      88                 :            :       {
      89                 :          0 :         QgsDebugMsg( QStringLiteral( "unknown spatial index exception caught" ) );
      90                 :          0 :       }
      91                 :            : 
      92                 :          0 :       return false;
      93                 :          0 :     }
      94                 :            : 
      95                 :            :     /**
      96                 :            :      * Removes existing \a data from the spatial index, with the specified \a bounds.
      97                 :            :      *
      98                 :            :      * \a data is not deleted, and it is the caller's responsibility to ensure that
      99                 :            :      * it is appropriately cleaned up.
     100                 :            :      */
     101                 :          0 :     bool remove( T *data, const QgsRectangle &bounds )
     102                 :            :     {
     103                 :          0 :       SpatialIndex::Region r = QgsSpatialIndexUtils::rectangleToRegion( bounds );
     104                 :            : 
     105                 :          0 :       QMutexLocker locker( &mMutex );
     106                 :            : 
     107                 :          0 :       const qint64 id = mDataToId.value( data, 0 );
     108                 :          0 :       if ( id == 0 )
     109                 :          0 :         return false;
     110                 :            : 
     111                 :            :       // TODO: handle exceptions
     112                 :          0 :       bool res = mRTree->deleteData( r, id );
     113                 :          0 :       mDataToId.remove( data );
     114                 :          0 :       mIdToData.remove( id );
     115                 :          0 :       return res;
     116                 :          0 :     }
     117                 :            : 
     118                 :            :     /**
     119                 :            :      * Performs an intersection check against the index, for data intersecting the specified \a bounds.
     120                 :            :      *
     121                 :            :      * The \a callback function will be called once for each matching data object encountered.
     122                 :            :      */
     123                 :          0 :     bool intersects( const QgsRectangle &bounds, const std::function< bool( T *data )> &callback ) const
     124                 :            :     {
     125                 :          0 :       GenericIndexVisitor<T> visitor( callback, mIdToData );
     126                 :          0 :       SpatialIndex::Region r = QgsSpatialIndexUtils::rectangleToRegion( bounds );
     127                 :            : 
     128                 :          0 :       QMutexLocker locker( &mMutex );
     129                 :          0 :       mRTree->intersectsWithQuery( r, visitor );
     130                 :            :       return true;
     131                 :          0 :     }
     132                 :            : 
     133                 :            :     /**
     134                 :            :      * Returns TRUE if the index contains no items.
     135                 :            :      */
     136                 :          0 :     bool isEmpty( ) const
     137                 :            :     {
     138                 :          0 :       QMutexLocker locker( &mMutex );
     139                 :          0 :       return mIdToData.isEmpty();
     140                 :          0 :     }
     141                 :            : 
     142                 :            :   private:
     143                 :            : 
     144                 :          0 :     std::unique_ptr< SpatialIndex::ISpatialIndex > createSpatialIndex( SpatialIndex::IStorageManager &storageManager )
     145                 :            :     {
     146                 :            :       // R-Tree parameters
     147                 :          0 :       constexpr double fillFactor = 0.7;
     148                 :          0 :       constexpr unsigned long indexCapacity = 10;
     149                 :          0 :       constexpr unsigned long leafCapacity = 10;
     150                 :          0 :       constexpr unsigned long dimension = 2;
     151                 :          0 :       constexpr SpatialIndex::RTree::RTreeVariant variant = SpatialIndex::RTree::RV_RSTAR;
     152                 :            : 
     153                 :            :       // create R-tree
     154                 :            :       SpatialIndex::id_type indexId;
     155                 :          0 :       return std::unique_ptr< SpatialIndex::ISpatialIndex >( SpatialIndex::RTree::createNewRTree( storageManager, fillFactor, indexCapacity,
     156                 :            :              leafCapacity, dimension, variant, indexId ) );
     157                 :            :     }
     158                 :            : 
     159                 :            :     std::unique_ptr< SpatialIndex::IStorageManager > mStorageManager;
     160                 :            :     std::unique_ptr< SpatialIndex::ISpatialIndex > mRTree;
     161                 :            : 
     162                 :            :     mutable QMutex mMutex;
     163                 :            : 
     164                 :          0 :     qint64 mNextId = 1;
     165                 :            :     QHash< qint64, T * > mIdToData;
     166                 :            :     QHash< T *, qint64 > mDataToId;
     167                 :            : 
     168                 :            :     template <typename TT>
     169                 :          0 :     class GenericIndexVisitor : public SpatialIndex::IVisitor
     170                 :            :     {
     171                 :            :       public:
     172                 :          0 :         explicit GenericIndexVisitor( const std::function< bool( TT *data )> &callback, const QHash< qint64, TT * > &data )
     173                 :          0 :           : mCallback( callback )
     174                 :          0 :           , mData( data )
     175                 :          0 :         {}
     176                 :            : 
     177                 :          0 :         void visitNode( const SpatialIndex::INode &n ) override
     178                 :          0 :         { Q_UNUSED( n ) }
     179                 :            : 
     180                 :          0 :         void visitData( const SpatialIndex::IData &d ) override
     181                 :            :         {
     182                 :          0 :           qint64 id = d.getIdentifier();
     183                 :          0 :           T *data = mData.value( id );
     184                 :          0 :           mCallback( data );
     185                 :          0 :         }
     186                 :            : 
     187                 :          0 :         void visitData( std::vector<const SpatialIndex::IData *> &v ) override
     188                 :          0 :         { Q_UNUSED( v ) }
     189                 :            : 
     190                 :            :       private:
     191                 :            :         const std::function< bool( TT *data )> &mCallback;
     192                 :            :         QHash< qint64, TT * > mData;
     193                 :            :     };
     194                 :            : 
     195                 :            : };
     196                 :            : 
     197                 :            : #endif // QGSGENERICSPATIALINDEX_H