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