[processing] port nearest neighbour analysis algorithm to C++ and add

test
qgis · Dec 9, 2019 · df3e801 · df3e801
1 parent eec0ac0
commit df3e801
Show file tree

Hide file tree

Showing 8 changed files with 221 additions and 166 deletions.
diff --git a/python/plugins/processing/algs/help/qgis.yaml b/python/plugins/processing/algs/help/qgis.yaml
@@ -236,12 +236,6 @@ qgis:minimumboundinggeometry: >
 qgis:multiparttosingleparts: >
   This algorithm takes a vector layer with multipart geometries and generates a new one in which all geometries contain a single part. Features with multipart geometries are divided in as many different features as parts the geometry contain, and the same attributes are used for each of them.
 
-qgis:nearestneighbouranalysis: >
-  This algorithm performs nearest neighbor analysis for a point layer.
-
-  Output is generated as an html file with the computed statistical values.
-
-
 qgis:numberofuniquevaluesinclasses: >
   This algorithm counts the different values that appear in a specified attributes for features of the same class.
 

diff --git a/python/plugins/processing/algs/qgis/NearestNeighbourAnalysis.py b/python/plugins/processing/algs/qgis/NearestNeighbourAnalysis.py
diff --git a/python/plugins/processing/algs/qgis/QgisAlgorithmProvider.py b/python/plugins/processing/algs/qgis/QgisAlgorithmProvider.py
@@ -60,7 +60,6 @@
 from .LinesToPolygons import LinesToPolygons
 from .MeanAndStdDevPlot import MeanAndStdDevPlot
 from .MinimumBoundingGeometry import MinimumBoundingGeometry
-from .NearestNeighbourAnalysis import NearestNeighbourAnalysis
 from .PointDistance import PointDistance
 from .PointsDisplacement import PointsDisplacement
 from .PointsFromLines import PointsFromLines
@@ -151,7 +150,6 @@ def getAlgs(self):
                 LinesToPolygons(),
                 MeanAndStdDevPlot(),
                 MinimumBoundingGeometry(),
-                NearestNeighbourAnalysis(),
                 PointDistance(),
                 PointsDisplacement(),
                 PointsFromLines(),

diff --git a/python/plugins/processing/tests/testdata/expected/nearest_neighbour_analysis.html b/python/plugins/processing/tests/testdata/expected/nearest_neighbour_analysis.html
@@ -0,0 +1,7 @@
+<html><head><meta http-equiv="Content-Type" content="text/html;charset=utf-8"/></head><body>
+<p>Observed mean distance: 188537.08110294046</p>
+<p>Expected mean distance: 1.33333333333</p>
+<p>Nearest neighbour index: 141402.81082720537</p>
+<p>Number of points: 9</p>
+<p>Z-Score: 811534.72696972766</p>
+</body></html>
diff --git a/src/analysis/CMakeLists.txt b/src/analysis/CMakeLists.txt
@@ -84,6 +84,7 @@ SET(QGIS_ANALYSIS_SRCS
   processing/qgsalgorithmminimumenclosingcircle.cpp
   processing/qgsalgorithmmultiparttosinglepart.cpp
   processing/qgsalgorithmmultiringconstantbuffer.cpp
+  processing/qgsalgorithmnearestneighbouranalysis.cpp
   processing/qgsalgorithmoffsetlines.cpp
   processing/qgsalgorithmorderbyexpression.cpp
   processing/qgsalgorithmorientedminimumboundingbox.cpp

diff --git a/src/analysis/processing/qgsalgorithmnearestneighbouranalysis.cpp b/src/analysis/processing/qgsalgorithmnearestneighbouranalysis.cpp
@@ -0,0 +1,155 @@
+/***************************************************************************
+                         qgsalgorithmnearestneighbouranalysis.cpp
+                         ---------------------
+    begin                : December 2019
+    copyright            : (C) 2019 by Alexander Bruy
+    email                : alexander dot bruy 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 "qgsalgorithmnearestneighbouranalysis.h"
+#include "qgsapplication.h"
+
+///@cond PRIVATE
+
+QString QgsNearestNeighbourAnalysisAlgorithm::name() const
+{
+  return QStringLiteral( "nearestneighbouranalysis" );
+}
+
+QString QgsNearestNeighbourAnalysisAlgorithm::displayName() const
+{
+  return QObject::tr( "Nearest neighbour analysis" );
+}
+
+QStringList QgsNearestNeighbourAnalysisAlgorithm::tags() const
+{
+  return QObject::tr( "point,node,vertex,nearest,neighbour,distance" ).split( ',' );
+}
+
+QString QgsNearestNeighbourAnalysisAlgorithm::group() const
+{
+  return QObject::tr( "Vector analysis" );
+}
+
+QString QgsNearestNeighbourAnalysisAlgorithm::groupId() const
+{
+  return QStringLiteral( "vectoranalysis" );
+}
+
+QString QgsNearestNeighbourAnalysisAlgorithm::shortHelpString() const
+{
+  return QObject::tr( "This algorithm performs nearest neighbor analysis for a point layer.\n\n"
+                      "Output is generated as an html file with the computed statistical values." );
+}
+
+QString QgsNearestNeighbourAnalysisAlgorithm::svgIconPath() const
+{
+  return QgsApplication::iconPath( QStringLiteral( "/algorithms/mAlgorithmNearestNeighbour.svg" ) );
+}
+
+QIcon QgsNearestNeighbourAnalysisAlgorithm::icon() const
+{
+  return QgsApplication::getThemeIcon( QStringLiteral( "/algorithms/mAlgorithmNearestNeighbour.svg" ) );
+}
+
+QgsNearestNeighbourAnalysisAlgorithm *QgsNearestNeighbourAnalysisAlgorithm::createInstance() const
+{
+  return new QgsNearestNeighbourAnalysisAlgorithm();
+}
+
+void QgsNearestNeighbourAnalysisAlgorithm::initAlgorithm( const QVariantMap & )
+{
+  addParameter( new QgsProcessingParameterFeatureSource( QStringLiteral( "INPUT" ), QObject::tr( "Input layer" ), QList< int >() << QgsProcessing::TypeVectorPoint ) );
+  addParameter( new QgsProcessingParameterFileDestination( QStringLiteral( "OUTPUT_HTML_FILE" ), QObject::tr( "Nearest neighbour" ),
+                QObject::tr( "HTML files (*.html *.HTML)" ), QVariant(), true ) );
+  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "OBSERVED_MD" ), QObject::tr( "Observed mean distance" ) ) );
+  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "EXPECTED_MD" ), QObject::tr( "Expected mean distance" ) ) );
+  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "NN_INDEX" ), QObject::tr( "Nearest neighbour index" ) ) );
+  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "POINT_COUNT" ), QObject::tr( "Number of points" ) ) );
+  addOutput( new QgsProcessingOutputNumber( QStringLiteral( "Z_SCORE" ), QObject::tr( "Z-score" ) ) );
+}
+
+QVariantMap QgsNearestNeighbourAnalysisAlgorithm::processAlgorithm( const QVariantMap &parameters, QgsProcessingContext &context, QgsProcessingFeedback *feedback )
+{
+  std::unique_ptr< QgsProcessingFeatureSource > source( parameterAsSource( parameters, QStringLiteral( "INPUT" ), context ) );
+  if ( !source )
+    throw QgsProcessingException( invalidSourceError( parameters, QStringLiteral( "INPUT" ) ) );
+
+  QString outputFile = parameterAsFileOutput( parameters, QStringLiteral( "OUTPUT_HTML_FILE" ), context );
+
+  QgsSpatialIndex spatialIndex( *source, feedback );
+  QgsDistanceArea da;
+  da.setSourceCrs( source->sourceCrs(), context.transformContext() );
+  da.setEllipsoid( context.project()->ellipsoid() );
+
+  double step = source->featureCount() ? 100.0 / source->featureCount() : 1;
+  QgsFeatureIterator it = source->getFeatures( QgsFeatureRequest().setSubsetOfAttributes( QList< int >() ) );
+
+  QgsFeatureRequest request;
+  QgsFeature neighbour;
+  double sumDist = 0.0;
+  double area = source->sourceExtent().width() * source->sourceExtent().height();
+
+  int i = 0;
+  QgsFeature f;
+  while ( it.nextFeature( f ) )
+  {
+    if ( feedback->isCanceled() )
+    {
+      break;
+    }
+
+    QgsFeatureId neighbourId = spatialIndex.nearestNeighbor( f.geometry().asPoint(), 2 ).at( 1 );
+    request.setFilterFid( neighbourId ).setSubsetOfAttributes( QList< int >() );
+    source->getFeatures( request ).nextFeature( neighbour );
+    sumDist += da.measureLine( neighbour.geometry().asPoint(), f.geometry().asPoint() );
+
+    i++;
+    feedback->setProgress( i * step );
+  }
+
+  int count = source->featureCount() > 0 ? source->featureCount() : 1;
+  double observedDistance = sumDist / count;
+  double expectedDistance = 0.5 / std::sqrt( count / area );
+  double nnIndex = observedDistance / expectedDistance;
+  double se = 0.26136 / std::sqrt( std::pow( count, 2 ) / area );
+  double zScore = ( observedDistance - expectedDistance ) / se;
+
+  QVariantMap outputs;
+  outputs.insert( QStringLiteral( "OBSERVED_MD" ), observedDistance );
+  outputs.insert( QStringLiteral( "EXPECTED_MD" ), expectedDistance );
+  outputs.insert( QStringLiteral( "NN_INDEX" ), nnIndex );
+  outputs.insert( QStringLiteral( "POINT_COUNT" ), count );
+  outputs.insert( QStringLiteral( "Z_SCORE" ), zScore );
+
+  if ( !outputFile.isEmpty() )
+  {
+    QFile file( outputFile );
+    if ( file.open( QIODevice::WriteOnly | QIODevice::Text ) )
+    {
+      QTextStream out( &file );
+      out << QStringLiteral( "<html><head><meta http-equiv=\"Content-Type\" content=\"text/html;charset=utf-8\"/></head><body>\n" );
+      out << QObject::tr( "<p>Observed mean distance: %1</p>\n" ).arg( observedDistance, 0, 'f', 11 );
+      out << QObject::tr( "<p>Expected mean distance: %1</p>\n" ).arg( expectedDistance, 0, 'f', 11 );
+      out << QObject::tr( "<p>Nearest neighbour index: %1</p>\n" ).arg( nnIndex, 0, 'f', 11 );
+      out << QObject::tr( "<p>Number of points: %1</p>\n" ).arg( count );
+      out << QObject::tr( "<p>Z-Score: %1</p>\n" ).arg( zScore, 0, 'f', 11 );
+      out << QStringLiteral( "</body></html>" );
+
+      outputs.insert( QStringLiteral( "OUTPUT_HTML_FILE" ), outputFile );
+    }
+  }
+
+  return outputs;
+}
+
+///@endcond