[feature][processing] Port and optimization of Random points in exten…

…t algorithm to C++
qgis · Nov 26, 2019 · a75436c · a75436c
1 parent d034812
commit a75436c
Show file tree

Hide file tree

Showing 4 changed files with 253 additions and 0 deletions.
diff --git a/src/analysis/CMakeLists.txt b/src/analysis/CMakeLists.txt
@@ -94,6 +94,7 @@ SET(QGIS_ANALYSIS_SRCS
   processing/qgsalgorithmpointslayerfromtable.cpp
   processing/qgsalgorithmprojectpointcartesian.cpp
   processing/qgsalgorithmpromotetomultipart.cpp
+  processing/qgsalgorithmrandompointsextent.cpp
   processing/qgsalgorithmrasterlayeruniquevalues.cpp
   processing/qgsalgorithmrasterlogicalop.cpp
   processing/qgsalgorithmrasterize.cpp

diff --git a/src/analysis/processing/qgsalgorithmrandompointsextent.cpp b/src/analysis/processing/qgsalgorithmrandompointsextent.cpp
@@ -0,0 +1,180 @@
+/***************************************************************************
+                         qgsalgorithmrandompointsextent.cpp
+                         ---------------------
+    begin                : November 2019
+    copyright            : (C) 2019 by Clemens Raffler
+    email                : clemens dot raffler 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.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+//Disclaimer: The algorithm optimizes the original Random points in extent algorithm, (C) Alexander Bruy, 2014
+
+#include "qgsalgorithmrandompointsextent.h"
+#include "random"
+
+///@cond PRIVATE
+
+QString QgsRandomPointsExtentAlgorithm::name() const
+{
+  return QStringLiteral( "randompointsinextent" );
+}
+
+QString QgsRandomPointsExtentAlgorithm::displayName() const
+{
+  return QObject::tr( "Random points in extent" );
+}
+
+QStringList QgsRandomPointsExtentAlgorithm::tags() const
+{
+  return QObject::tr( "random,points,extent,create" ).split( ',' );
+}
+
+QString QgsRandomPointsExtentAlgorithm::group() const
+{
+  return QObject::tr( "Vector creation" );
+}
+
+QString QgsRandomPointsExtentAlgorithm::groupId() const
+{
+  return QStringLiteral( "vectorcreation" );
+}
+
+void QgsRandomPointsExtentAlgorithm::initAlgorithm( const QVariantMap & )
+{
+  addParameter( new QgsProcessingParameterExtent( QStringLiteral( "EXTENT" ), QObject::tr( "Input extent" ) ) );
+  addParameter( new QgsProcessingParameterNumber( QStringLiteral( "NUM_POINTS" ), QStringLiteral( "Number of points" ), QgsProcessingParameterNumber::Integer, 1, false, 1 ) );
+  addParameter( new QgsProcessingParameterCrs( QStringLiteral( "CRS" ), QObject::tr( "Target CRS" ), QStringLiteral( "ProjectCrs" ) ) );
+  addParameter( new QgsProcessingParameterDistance( QStringLiteral( "MIN_DISTANCE" ), QObject::tr( "Minimum distance between points" ), 0, QStringLiteral( "CRS" ), true, 0 ) );
+  addParameter( new QgsProcessingParameterNumber( QStringLiteral( "MAX_ATTEMPTS" ), QStringLiteral( "Maximum number of attempts given the minimum distance" ), QgsProcessingParameterNumber::Integer, 200, true, 1 ) );
+  addParameter( new QgsProcessingParameterFeatureSink( QStringLiteral( "OUTPUT" ), QObject::tr( "Random points" ), QgsProcessing::TypeVectorPoint ) );
+}
+
+QString QgsRandomPointsExtentAlgorithm::shortHelpString() const
+{
+  return QObject::tr( "This algorithm creates a new point layer with a given "
+                      "number of random points, all of them within a given extent. "
+                      "A distance factor can be specified, to avoid points being "
+                      "too close to each other. If the minimum distance between points "
+                      " makes it impossible to create new points, either "
+                      " distance can be decreased or the maximum number of attempts may be "
+                      " increased."
+                    );
+}
+
+QgsRandomPointsExtentAlgorithm *QgsRandomPointsExtentAlgorithm::createInstance() const
+{
+  return new QgsRandomPointsExtentAlgorithm();
+}
+
+bool QgsRandomPointsExtentAlgorithm::prepareAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback * )
+{
+  mCrs = parameterAsCrs( parameters, QStringLiteral( "CRS" ), context );
+  mExtent = parameterAsExtent( parameters, QStringLiteral( "EXTENT" ), context, mCrs );
+  mNumPoints = parameterAsInt( parameters, QStringLiteral( "NUM_POINTS" ), context );
+  mDistance = parameterAsDouble( parameters, QStringLiteral( "MIN_DISTANCE" ), context );
+  mMaxAttempts = parameterAsInt( parameters, QStringLiteral( "MAX_ATTEMPTS" ), context );
+
+  return true;
+}
+
+QVariantMap QgsRandomPointsExtentAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
+{
+
+  QgsFields fields = QgsFields();
+  fields.append( QgsField( QStringLiteral( "id" ), QVariant::LongLong ) );
+
+  QString dest;
+  std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral( "OUTPUT" ), context, dest, fields, QgsWkbTypes::Point, mCrs ) );
+  if ( !sink )
+    throw QgsProcessingException( invalidSinkError( parameters, QStringLiteral( "OUTPUT" ) ) );
+
+  //initialize random engine
+  std::random_device random_device;
+  std::mt19937 mersenne_twister( random_device() );
+
+  std::uniform_real_distribution<double> x_distribution( mExtent.xMinimum(), mExtent.xMaximum() );
+  std::uniform_real_distribution<double> y_distribution( mExtent.yMinimum(), mExtent.yMaximum() );
+
+  if ( mDistance == 0 )
+  {
+    int i = 0;
+    while ( i < mNumPoints )
+    {
+      if ( feedback && feedback->isCanceled() )
+        break;
+
+      double rx = x_distribution( random_device );
+      double ry = y_distribution( random_device );
+
+      QgsFeature f = QgsFeature( i );
+
+      f.setGeometry( QgsGeometry( new QgsPoint( rx, ry ) ) );
+      f.setAttributes( QgsAttributes() << i );
+      sink->addFeature( f, QgsFeatureSink::FastInsert );
+      i++;
+      feedback->setProgress( static_cast<int>( static_cast<double>( i ) / static_cast<double>( mNumPoints ) * 100 ) );
+    }
+  }
+  else
+  {
+    std::unique_ptr<QgsSpatialIndex> index( new QgsSpatialIndex() );
+    int distCheckIterations = 0;
+
+    int i = 0;
+    while ( i < mNumPoints )
+    {
+      if ( feedback && feedback->isCanceled() )
+        break;
+
+      double rx = x_distribution( random_device );
+      double ry = y_distribution( random_device );
+
+      QgsGeometry randomPointGeom = QgsGeometry( new QgsPoint( rx, ry ) );
+
+      //check if new random point is inside searching distance to existing points
+      QList<QgsFeatureId> neighbors = index->nearestNeighbor( randomPointGeom, 1, mDistance );
+      if ( neighbors.size() == 0 )
+      {
+        QgsFeature f = QgsFeature( i );
+        f.setAttributes( QgsAttributes() << i );
+        f.setGeometry( randomPointGeom );
+        index->addFeature( f );
+        sink->addFeature( f, QgsFeatureSink::FastInsert );
+        i++;
+        distCheckIterations = 0; //reset distCheckIterations if a point is added
+        feedback->setProgress( static_cast<int>( static_cast<double>( i ) / static_cast<double>( mNumPoints ) * 100 ) );
+      }
+      else
+      {
+        if ( distCheckIterations == mMaxAttempts )
+        {
+          throw QgsProcessingException( QObject::tr( "%1 of %2 points have been successfully created, but no more random points could be found "
+                                        " due to the given minimum distance between points. Either choose a larger extent, "
+                                        "lower the minimum distance between points or try increasing the number "
+                                        "of attempts for searching new points." ).arg( i ).arg( mNumPoints ) );
+        }
+        else
+        {
+          distCheckIterations++;
+          continue; //retry with new point
+        }
+
+      }
+    }
+  }
+
+  QVariantMap outputs;
+  outputs.insert( QStringLiteral( "OUTPUT" ), dest );
+
+  return outputs;
+}
+
+///@endcond
diff --git a/src/analysis/processing/qgsalgorithmrandompointsextent.h b/src/analysis/processing/qgsalgorithmrandompointsextent.h
@@ -0,0 +1,70 @@
+/***************************************************************************
+                         qgsalgorithmrandompointsextent.h
+                         ---------------------
+    begin                : November 2019
+    copyright            : (C) 2019 by Clemens Raffler
+    email                : clemens dot raffler 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.                                   *
+ *                                                                         *
+ ***************************************************************************/
+
+
+//Disclaimer: The algorithm optimizes the original Random points in extent algorithm, (C) Alexander Bruy, 2014
+
+#ifndef QGSALGORITHMRANDOMPOINTSEXTENT_H
+#define QGSALGORITHMRANDOMPOINTSEXTENT_H
+
+#define SIP_NO_FILE
+
+#include "qgis_sip.h"
+#include "qgsprocessingalgorithm.h"
+#include "qgsapplication.h"
+
+///@cond PRIVATE
+
+/**
+ * Native random points in extent creation algorithm.
+ */
+class QgsRandomPointsExtentAlgorithm : public QgsProcessingAlgorithm
+{
+  public:
+
+    QgsRandomPointsExtentAlgorithm() = default;
+    void initAlgorithm( const QVariantMap &configuration = QVariantMap() ) override;
+    QIcon icon() const override { return QgsApplication::getThemeIcon( QStringLiteral( "/algorithms/mAlgorithmRandomPointsWithinExtent.svg" ) ); }
+    QString svgIconPath() const override { return QgsApplication::iconPath( QStringLiteral( "/algorithms/mAlgorithmRandomPointsWithinExtent.svg" ) ); }
+    QString name() const override;
+    QString displayName() const override;
+    QStringList tags() const override;
+    QString group() const override;
+    QString groupId() const override;
+    QString shortHelpString() const override;
+    QgsRandomPointsExtentAlgorithm *createInstance() const override SIP_FACTORY;
+
+  protected:
+    bool prepareAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback * ) override;
+    QVariantMap processAlgorithm( const QVariantMap &parameters,
+                                  QgsProcessingContext &context,
+                                  QgsProcessingFeedback *feedback ) override;
+
+
+  private:
+    QgsRectangle mExtent;
+    int mNumPoints;
+    double mDistance;
+    int mMaxAttempts;
+    QgsCoordinateReferenceSystem mCrs;
+
+};
+
+
+///@endcond PRIVATE
+
+#endif // QGSALGORITHMRANDOMPOINTSEXTENT_H
diff --git a/src/analysis/processing/qgsnativealgorithms.cpp b/src/analysis/processing/qgsnativealgorithms.cpp
@@ -88,6 +88,7 @@
 #include "qgsalgorithmpointslayerfromtable.h"
 #include "qgsalgorithmprojectpointcartesian.h"
 #include "qgsalgorithmpromotetomultipart.h"
+#include "qgsalgorithmrandompointsextent.h"
 #include "qgsalgorithmrasterlayeruniquevalues.h"
 #include "qgsalgorithmrasterlogicalop.h"
 #include "qgsalgorithmrasterize.h"
@@ -260,6 +261,7 @@ void QgsNativeAlgorithms::loadAlgorithms()
   addAlgorithm( new QgsPointsLayerFromTableAlgorithm() );
   addAlgorithm( new QgsProjectPointCartesianAlgorithm() );
   addAlgorithm( new QgsPromoteToMultipartAlgorithm() );
+  addAlgorithm( new QgsRandomPointsExtentAlgorithm() );
   addAlgorithm( new QgsRasterLayerUniqueValuesReportAlgorithm() );
   addAlgorithm( new QgsRasterLayerZonalStatsAlgorithm() );
   addAlgorithm( new QgsRasterLogicalAndAlgorithm() );