QGIS API Documentation  3.27.0-Master (11ef3e5184)
qgsclassificationjenks.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsclassificationjenks.h
3  ---------------------
4  begin : September 2019
5  copyright : (C) 2019 by Denis Rouzaud
6  email : [email protected]
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 #include <limits>
17 #include "qgsclassificationjenks.h"
18 #include "qgsapplication.h"
19 
20 #if QT_VERSION >= QT_VERSION_CHECK(5, 15, 0)
21 #include <QRandomGenerator>
22 #endif
23 
26 {
27 
28 }
29 
31 {
32  return QObject::tr( "Natural Breaks (Jenks)" );
33 }
34 
36 {
37  return QStringLiteral( "Jenks" );
38 }
39 
41 {
43  copyBase( c );
44  return c;
45 }
46 
48 {
49  return QgsApplication::getThemeIcon( "classification_methods/mClassificationNaturalBreak.svg" );
50 }
51 
52 
53 QList<double> QgsClassificationJenks::calculateBreaks( double &minimum, double &maximum,
54  const QList<double> &values, int nclasses )
55 {
56  // Jenks Optimal (Natural Breaks) algorithm
57  // Based on the Jenks algorithm from the 'classInt' package available for
58  // the R statistical prgramming language, and from Python code from here:
59  // http://danieljlewis.org/2010/06/07/jenks-natural-breaks-algorithm-in-python/
60  // and is based on a JAVA and Fortran code available here:
61  // https://stat.ethz.ch/pipermail/r-sig-geo/2006-March/000811.html
62 
63  // Returns class breaks such that classes are internally homogeneous while
64  // assuring heterogeneity among classes.
65 
66  if ( values.isEmpty() )
67  return QList<double>();
68 
69  if ( nclasses <= 1 )
70  {
71  return QList<double>() << maximum;
72  }
73 
74  if ( nclasses >= values.size() )
75  {
76  return values;
77  }
78 
79  QVector<double> sample;
80  QVector<double> sorted;
81 
82  // if we have lots of values, we need to take a random sample
83  if ( values.size() > mMaximumSize )
84  {
85  // for now, sample at least maximumSize values or a 10% sample, whichever
86  // is larger. This will produce a more representative sample for very large
87  // layers, but could end up being computationally intensive...
88 
89  sample.resize( std::max( mMaximumSize, static_cast<int>( values.size() ) / 10 ) );
90 
91  QgsDebugMsgLevel( QStringLiteral( "natural breaks (jenks) sample size: %1" ).arg( sample.size() ), 2 );
92  QgsDebugMsgLevel( QStringLiteral( "values:%1" ).arg( values.size() ), 2 );
93 
94  sample[ 0 ] = minimum;
95  sample[ 1 ] = maximum;
96 
97  sorted = values.toVector();
98  std::sort( sorted.begin(), sorted.end() );
99 
100  int j = -1;
101 
102  // loop through all values in initial array
103  // skip the first value as it is a minimum one
104  // skip the last value as that one is a maximum one
105  // and those are already in the sample as items 0 and 1
106  for ( int i = 1; i < sorted.size() - 2; i++ )
107  {
108  if ( ( i * ( mMaximumSize - 2 ) / ( sorted.size() - 2 ) ) > j )
109  {
110  j++;
111  sample[ j + 2 ] = sorted[ i ];
112  }
113  }
114  }
115  else
116  {
117  sample = values.toVector();
118  }
119 
120  const int n = sample.size();
121 
122  // sort the sample values
123  std::sort( sample.begin(), sample.end() );
124 
125  QVector< QVector<int> > matrixOne( n + 1 );
126  QVector< QVector<double> > matrixTwo( n + 1 );
127 
128  for ( int i = 0; i <= n; i++ )
129  {
130  matrixOne[i].resize( nclasses + 1 );
131  matrixTwo[i].resize( nclasses + 1 );
132  }
133 
134  for ( int i = 1; i <= nclasses; i++ )
135  {
136  matrixOne[0][i] = 1;
137  matrixOne[1][i] = 1;
138  matrixTwo[0][i] = 0.0;
139  for ( int j = 2; j <= n; j++ )
140  {
141  matrixTwo[j][i] = std::numeric_limits<double>::max();
142  }
143  }
144 
145  for ( int l = 2; l <= n; l++ )
146  {
147  double s1 = 0.0;
148  double s2 = 0.0;
149  int w = 0;
150 
151  double v = 0.0;
152 
153  for ( int m = 1; m <= l; m++ )
154  {
155  const int i3 = l - m + 1;
156 
157  const double val = sample[ i3 - 1 ];
158 
159  s2 += val * val;
160  s1 += val;
161  w++;
162 
163  v = s2 - ( s1 * s1 ) / static_cast< double >( w );
164  const int i4 = i3 - 1;
165  if ( i4 != 0 )
166  {
167  for ( int j = 2; j <= nclasses; j++ )
168  {
169  if ( matrixTwo[l][j] >= v + matrixTwo[i4][j - 1] )
170  {
171  matrixOne[l][j] = i4;
172  matrixTwo[l][j] = v + matrixTwo[i4][j - 1];
173  }
174  }
175  }
176  }
177  matrixOne[l][1] = 1;
178  matrixTwo[l][1] = v;
179  }
180 
181  QVector<double> breaks( nclasses );
182  breaks[nclasses - 1] = sample[n - 1];
183 
184  for ( int j = nclasses, k = n; j >= 2; j-- )
185  {
186  const int id = matrixOne[k][j] - 1;
187  breaks[j - 2] = sample[id];
188  k = matrixOne[k][j] - 1;
189  }
190 
191  return breaks.toList();
192 }
static QIcon getThemeIcon(const QString &name, const QColor &fillColor=QColor(), const QColor &strokeColor=QColor())
Helper to get a theme icon.
QgsClassificationJenks is an implementation of QgsClassificationMethod for natural breaks based on Je...
QgsClassificationMethod * clone() const override
Returns a clone of the method.
QIcon icon() const override
The icon of the method.
QString name() const override
The readable and translate name of the method.
QString id() const override
The id of the method as saved in the project, must be unique in registry.
QgsClassificationMethod is an abstract class for implementations of classification methods.
void copyBase(QgsClassificationMethod *c) const
Copy the parameters (shall be used in clone implementation)
As part of the API refactoring and improvements which landed in the Processing API was substantially reworked from the x version This was done in order to allow much of the underlying Processing framework to be ported into c
#define QgsDebugMsgLevel(str, level)
Definition: qgslogger.h:39