qgsmeshspatialindex.cpp

Go to the documentation of this file.

/***************************************************************************
    qgsmeshspatialindex.cpp
    -----------------------
    begin                : January 2019
    copyright            : (C) 2019 by Peter Petrik
    email                : zilolv at gmail dot com
 ***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/
 
#include "qgsmeshspatialindex.h"
 
#include <memory>
#include <spatialindex/SpatialIndex.h>
 
#include "qgsfeedback.h"
#include "qgslogger.h"
#include "qgsrectangle.h"
#include "qgsspatialindexutils.h"
 
#include <QMutex>
#include <QMutexLocker>
#include <QString>
 
using namespace Qt::StringLiterals;
 
using namespace SpatialIndex;

 
static Region faceToRegion( const QgsMesh &mesh, int id, bool &ok )
{
  const QgsMeshFace face = mesh.face( id );
 
  if ( face.isEmpty() )
  {
    ok = false;
    return Region();
  }
 
  const QVector<QgsMeshVertex> &vertices = mesh.vertices;
 
  double xMinimum = vertices[face[0]].x();
  double yMinimum = vertices[face[0]].y();
  double xMaximum = vertices[face[0]].x();
  double yMaximum = vertices[face[0]].y();
 
  for ( int i = 1; i < face.size(); ++i )
  {
    xMinimum = std::min( vertices[face[i]].x(), xMinimum );
    yMinimum = std::min( vertices[face[i]].y(), yMinimum );
    xMaximum = std::max( vertices[face[i]].x(), xMaximum );
    yMaximum = std::max( vertices[face[i]].y(), yMaximum );
  }
 
  double pt1[2] = { xMinimum, yMinimum };
  double pt2[2] = { xMaximum, yMaximum };
 
  ok = true;
  return SpatialIndex::Region( pt1, pt2, 2 );
}
 
static Region edgeToRegion( const QgsMesh &mesh, int id, bool &ok )
{
  const QgsMeshEdge edge = mesh.edge( id );
  const QgsMeshVertex firstVertex = mesh.vertices[edge.first];
  const QgsMeshVertex secondVertex = mesh.vertices[edge.second];
  const double xMinimum = std::min( firstVertex.x(), secondVertex.x() );
  const double yMinimum = std::min( firstVertex.y(), secondVertex.y() );
  const double xMaximum = std::max( firstVertex.x(), secondVertex.x() );
  const double yMaximum = std::max( firstVertex.y(), secondVertex.y() );
  double pt1[2] = { xMinimum, yMinimum };
  double pt2[2] = { xMaximum, yMaximum };
  ok = true;
  return SpatialIndex::Region( pt1, pt2, 2 );
}

class QgisMeshVisitor : public SpatialIndex::IVisitor
{
  public:
    explicit QgisMeshVisitor( QList<int> &list )
      : mList( list )
    {}
 
    void visitNode( const INode &n ) override { Q_UNUSED( n ) }
 
    void visitData( const IData &d ) override { mList.append( static_cast<int>( d.getIdentifier() ) ); }
 
    void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
 
  private:
    QList<int> &mList;
};

class QgsMeshSpatialIndexCopyVisitor : public SpatialIndex::IVisitor
{
  public:
    explicit QgsMeshSpatialIndexCopyVisitor( SpatialIndex::ISpatialIndex *newIndex )
      : mNewIndex( newIndex )
    {}
 
    void visitNode( const INode &n ) override { Q_UNUSED( n ) }
 
    void visitData( const IData &d ) override
    {
      SpatialIndex::IShape *shape = nullptr;
      d.getShape( &shape );
      mNewIndex->insertData( 0, nullptr, *shape, d.getIdentifier() );
      delete shape;
    }
 
    void visitData( std::vector<const IData *> &v ) override { Q_UNUSED( v ) }
 
  private:
    SpatialIndex::ISpatialIndex *mNewIndex = nullptr;
};
 

class QgsMeshIteratorDataStream : public IDataStream
{
  public:
    explicit QgsMeshIteratorDataStream( const QgsMesh &mesh, int featuresCount, std::function<Region( const QgsMesh &mesh, int id, bool &ok )> featureToRegionFunction, QgsFeedback *feedback = nullptr )
      : mMesh( mesh )
      , mFeaturesCount( featuresCount )
      , mFeatureToRegionFunction( std::move( featureToRegionFunction ) )
      , mFeedback( feedback )
    {
      readNextEntry();
    }
 
    ~QgsMeshIteratorDataStream() override {}

    IData *getNext() override
    {
      if ( mFeedback && mFeedback->isCanceled() )
        return nullptr;
 
      RTree::Data *ret = mNextData.release();
      readNextEntry();
      return ret;
    }

    bool hasNext() override { return nullptr != mNextData.get(); }

    uint32_t size() override { return static_cast<uint32_t>( mFeaturesCount ); }

    void rewind() override { mIterator = 0; }
 
  protected:
    void readNextEntry()
    {
      SpatialIndex::Region r;
      while ( mIterator < mFeaturesCount )
      {
        bool ok = false;
        r = mFeatureToRegionFunction( mMesh, mIterator, ok );
        if ( ok )
        {
          mNextData = std::make_unique<RTree::Data>( 0, nullptr, r, mIterator );
          ++mIterator;
          return;
        }
        else
        {
          ++mIterator;
          continue;
        }
      }
    }
 
  private:
    int mIterator = 0;
    const QgsMesh &mMesh;
    int mFeaturesCount = 0;
    std::function<Region( const QgsMesh &mesh, int id, bool &ok )> mFeatureToRegionFunction;
    std::unique_ptr<RTree::Data> mNextData;
    QgsFeedback *mFeedback = nullptr;
};

class QgsMeshSpatialIndexData : public QSharedData
{
  public:
    QgsMeshSpatialIndexData() { initTree(); }

    explicit QgsMeshSpatialIndexData( const QgsMesh &fi, QgsFeedback *feedback, QgsMesh::ElementType elementType )
    {
      switch ( elementType )
      {
        case QgsMesh::ElementType::Edge:
        {
          QgsMeshIteratorDataStream fids( fi, fi.edgeCount(), edgeToRegion, feedback );
          initTree( &fids );
        }
        break;
        case QgsMesh::ElementType::Face:
        {
          QgsMeshIteratorDataStream fids( fi, fi.faceCount(), faceToRegion, feedback );
          initTree( &fids );
        }
        break;
        default:
          // vertices are not supported
          Q_ASSERT( false );
          break;
      }
    }
 
    QgsMeshSpatialIndexData( const QgsMeshSpatialIndexData &other )
      : QSharedData( other )
    {
      const QMutexLocker locker( &other.mMutex );
 
      initTree();
 
      // copy R-tree data one by one (is there a faster way??)
      double low[] = { std::numeric_limits<double>::lowest(), std::numeric_limits<double>::lowest() };
      double high[] = { std::numeric_limits<double>::max(), std::numeric_limits<double>::max() };
      const SpatialIndex::Region query( low, high, 2 );
      QgsMeshSpatialIndexCopyVisitor visitor( mRTree.get() );
      other.mRTree->intersectsWithQuery( query, visitor );
    }
 
    ~QgsMeshSpatialIndexData() = default;
 
    QgsMeshSpatialIndexData &operator=( const QgsMeshSpatialIndexData &rh ) = delete;
 
    void initTree( IDataStream *inputStream = nullptr )
    {
      // for now only memory manager
      mStorage.reset( StorageManager::createNewMemoryStorageManager() );
 
      // R-Tree parameters
      const double fillFactor = 0.7;
      const unsigned int indexCapacity = 10;
      const unsigned int leafCapacity = 10;
      const unsigned int dimension = 2;
      const RTree::RTreeVariant variant = RTree::RV_RSTAR;
 
      // create R-tree
      SpatialIndex::id_type indexId;
 
      if ( inputStream && inputStream->hasNext() )
        mRTree.reset( RTree::createAndBulkLoadNewRTree( RTree::BLM_STR, *inputStream, *mStorage, fillFactor, indexCapacity, leafCapacity, dimension, variant, indexId ) );
      else
        mRTree.reset( RTree::createNewRTree( *mStorage, fillFactor, indexCapacity, leafCapacity, dimension, variant, indexId ) );
    }

    std::unique_ptr<SpatialIndex::IStorageManager> mStorage;

    std::unique_ptr<SpatialIndex::ISpatialIndex> mRTree;
 
    mutable QMutex mMutex;
};

 
QgsMeshSpatialIndex::QgsMeshSpatialIndex()
{
  d = new QgsMeshSpatialIndexData;
}
 
QgsMeshSpatialIndex::QgsMeshSpatialIndex( const QgsMesh &mesh, QgsFeedback *feedback, QgsMesh::ElementType elementType )
  : mElementType( elementType )
{
  d = new QgsMeshSpatialIndexData( mesh, feedback, elementType );
}
 
QgsMeshSpatialIndex::QgsMeshSpatialIndex( const QgsMeshSpatialIndex &other ) //NOLINT
  : mElementType( other.mElementType )
  , d( other.d )
{}
 
QgsMeshSpatialIndex::QgsMeshSpatialIndex( QgsMeshSpatialIndex &&other ) //NOLINT
  : mElementType( other.mElementType )
  , d( std::move( other.d ) )
{}
 
QgsMeshSpatialIndex::~QgsMeshSpatialIndex() = default; //NOLINT
 
QgsMeshSpatialIndex &QgsMeshSpatialIndex::operator=( const QgsMeshSpatialIndex &other )
{
  if ( this != &other )
  {
    mElementType = other.mElementType;
    d = other.d;
  }
  return *this;
}
 
QgsMeshSpatialIndex &QgsMeshSpatialIndex::operator=( QgsMeshSpatialIndex &&other )
{
  if ( this != &other )
  {
    mElementType = std::move( other.mElementType );
    d = std::move( other.d );
  }
  return *this;
}
 
QList<int> QgsMeshSpatialIndex::intersects( const QgsRectangle &rect ) const
{
  QList<int> list;
  if ( rect.isNull() )
    return list;
 
  QgisMeshVisitor visitor( list );
 
  const SpatialIndex::Region r = QgsSpatialIndexUtils::rectangleToRegion( rect );
 
  const QMutexLocker locker( &d->mMutex );
  d->mRTree->intersectsWithQuery( r, visitor );
 
  return list;
}
 
QList<int> QgsMeshSpatialIndex::nearestNeighbor( const QgsPointXY &point, int neighbors ) const
{
  QList<int> list;
  QgisMeshVisitor visitor( list );
 
  double pt[2] = { point.x(), point.y() };
  const Point p( pt, 2 );
 
  const QMutexLocker locker( &d->mMutex );
  d->mRTree->nearestNeighborQuery( static_cast<uint32_t>( neighbors ), p, visitor );
 
  return list;
}
 
QgsMesh::ElementType QgsMeshSpatialIndex::elementType() const
{
  return mElementType;
}
 
void QgsMeshSpatialIndex::addFace( int faceIndex, const QgsMesh &mesh )
{
  if ( mesh.face( faceIndex ).isEmpty() )
    return;
 
  bool ok = false;
  const SpatialIndex::Region r( faceToRegion( mesh, faceIndex, ok ) );
  if ( !ok )
    return;
 
  const QMutexLocker locker( &d.constData()->mMutex );
 
  try
  {
    d.constData()->mRTree->insertData( 0, nullptr, r, faceIndex );
  }
  catch ( Tools::Exception &e )
  {
    Q_UNUSED( e )
    QgsDebugError( u"Tools::Exception caught: "_s.arg( e.what().c_str() ) );
  }
  catch ( const std::exception &e )
  {
    Q_UNUSED( e )
    QgsDebugError( u"std::exception caught: "_s.arg( e.what() ) );
  }
  catch ( ... )
  {
    QgsDebugError( u"unknown spatial index exception caught"_s );
  }
}
 
void QgsMeshSpatialIndex::removeFace( int faceIndex, const QgsMesh &mesh )
{
  if ( mesh.face( faceIndex ).isEmpty() )
    return;
  const QMutexLocker locker( &d.constData()->mMutex );
  bool ok = false;
  d.constData()->mRTree->deleteData( faceToRegion( mesh, faceIndex, ok ), faceIndex );
}