QGIS API Documentation 3.41.0-Master (3440c17df1d)
Loading...
Searching...
No Matches
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
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>
18#include "qgsapplication.h"
19
20#include <QRandomGenerator>
21
27
29{
30 return QObject::tr( "Natural Breaks (Jenks)" );
31}
32
34{
35 return QStringLiteral( "Jenks" );
36}
37
44
46{
47 return QgsApplication::getThemeIcon( "classification_methods/mClassificationNaturalBreak.svg" );
48}
49
50
51QList<double> QgsClassificationJenks::calculateBreaks( double &minimum, double &maximum,
52 const QList<double> &values, int nclasses, QString &error )
53{
54 Q_UNUSED( error )
55 // Jenks Optimal (Natural Breaks) algorithm
56 // Based on the Jenks algorithm from the 'classInt' package available for
57 // the R statistical prgramming language, and from Python code from here:
58 // http://danieljlewis.org/2010/06/07/jenks-natural-breaks-algorithm-in-python/
59 // and is based on a JAVA and Fortran code available here:
60 // https://stat.ethz.ch/pipermail/r-sig-geo/2006-March/000811.html
61
62 // Returns class breaks such that classes are internally homogeneous while
63 // assuring heterogeneity among classes.
64
65 if ( values.isEmpty() )
66 return QList<double>();
67
68 if ( nclasses <= 1 )
69 {
70 return QList<double>() << maximum;
71 }
72
73 if ( nclasses >= values.size() )
74 {
75 return values;
76 }
77
78 QVector<double> sample;
79 QVector<double> sorted;
80
81 // if we have lots of values, we need to take a random sample
82 if ( values.size() > mMaximumSize )
83 {
84 // for now, sample at least maximumSize values or a 10% sample, whichever
85 // is larger. This will produce a more representative sample for very large
86 // layers, but could end up being computationally intensive...
87
88 sample.resize( std::max( mMaximumSize, static_cast<int>( values.size() ) / 10 ) );
89
90 QgsDebugMsgLevel( QStringLiteral( "natural breaks (jenks) sample size: %1" ).arg( sample.size() ), 2 );
91 QgsDebugMsgLevel( QStringLiteral( "values:%1" ).arg( values.size() ), 2 );
92
93 sample[ 0 ] = minimum;
94 sample[ 1 ] = maximum;
95
96 sorted = values.toVector();
97 std::sort( sorted.begin(), sorted.end() );
98
99 int j = -1;
100
101 // loop through all values in initial array
102 // skip the first value as it is a minimum one
103 // skip the last value as that one is a maximum one
104 // and those are already in the sample as items 0 and 1
105 for ( int i = 1; i < sorted.size() - 2; i++ )
106 {
107 if ( ( i * ( mMaximumSize - 2 ) / ( sorted.size() - 2 ) ) > j )
108 {
109 j++;
110 sample[ j + 2 ] = sorted[ i ];
111 }
112 }
113 }
114 else
115 {
116 sample = values.toVector();
117 }
118
119 const int n = sample.size();
120
121 // sort the sample values
122 std::sort( sample.begin(), sample.end() );
123
124 QVector< QVector<int> > matrixOne( n + 1 );
125 QVector< QVector<double> > matrixTwo( n + 1 );
126
127 for ( int i = 0; i <= n; i++ )
128 {
129 matrixOne[i].resize( nclasses + 1 );
130 matrixTwo[i].resize( nclasses + 1 );
131 }
132
133 for ( int i = 1; i <= nclasses; i++ )
134 {
135 matrixOne[0][i] = 1;
136 matrixOne[1][i] = 1;
137 matrixTwo[0][i] = 0.0;
138 for ( int j = 2; j <= n; j++ )
139 {
140 matrixTwo[j][i] = std::numeric_limits<double>::max();
141 }
142 }
143
144 for ( int l = 2; l <= n; l++ )
145 {
146 double s1 = 0.0;
147 double s2 = 0.0;
148 int w = 0;
149
150 double v = 0.0;
151
152 for ( int m = 1; m <= l; m++ )
153 {
154 const int i3 = l - m + 1;
155
156 const double val = sample[ i3 - 1 ];
157
158 s2 += val * val;
159 s1 += val;
160 w++;
161
162 v = s2 - ( s1 * s1 ) / static_cast< double >( w );
163 const int i4 = i3 - 1;
164 if ( i4 != 0 )
165 {
166 for ( int j = 2; j <= nclasses; j++ )
167 {
168 if ( matrixTwo[l][j] >= v + matrixTwo[i4][j - 1] )
169 {
170 matrixOne[l][j] = i4;
171 matrixTwo[l][j] = v + matrixTwo[i4][j - 1];
172 }
173 }
174 }
175 }
176 matrixOne[l][1] = 1;
177 matrixTwo[l][1] = v;
178 }
179
180 QVector<double> breaks( nclasses );
181 breaks[nclasses - 1] = sample[n - 1];
182
183 for ( int j = nclasses, k = n; j >= 2; j-- )
184 {
185 const int id = matrixOne[k][j] - 1;
186 breaks[j - 2] = sample[id];
187 k = matrixOne[k][j] - 1;
188 }
189
190 return breaks.toList();
191}
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