20#include <unordered_set>
24QString QgsDbscanClusteringAlgorithm::name()
const
26 return QStringLiteral(
"dbscanclustering" );
29QString QgsDbscanClusteringAlgorithm::displayName()
const
31 return QObject::tr(
"DBSCAN clustering" );
34QString QgsDbscanClusteringAlgorithm::shortDescription()
const
36 return QObject::tr(
"Clusters point features using a density based scan algorithm." );
39QStringList QgsDbscanClusteringAlgorithm::tags()
const
41 return QObject::tr(
"clustering,clusters,density,based,points,distance" ).split(
',' );
44QString QgsDbscanClusteringAlgorithm::group()
const
46 return QObject::tr(
"Vector analysis" );
49QString QgsDbscanClusteringAlgorithm::groupId()
const
51 return QStringLiteral(
"vectoranalysis" );
54void QgsDbscanClusteringAlgorithm::initAlgorithm(
const QVariantMap & )
61 QObject::tr(
"Maximum distance between clustered points" ), 1, QStringLiteral(
"INPUT" ),
false, 0 ) );
63 auto dbscanStarParam = std::make_unique<QgsProcessingParameterBoolean>( QStringLiteral(
"DBSCAN*" ),
64 QObject::tr(
"Treat border points as noise (DBSCAN*)" ),
false,
true );
66 addParameter( dbscanStarParam.release() );
68 auto fieldNameParam = std::make_unique<QgsProcessingParameterString>( QStringLiteral(
"FIELD_NAME" ),
69 QObject::tr(
"Cluster field name" ), QStringLiteral(
"CLUSTER_ID" ) );
71 addParameter( fieldNameParam.release() );
72 auto sizeFieldNameParam = std::make_unique<QgsProcessingParameterString>( QStringLiteral(
"SIZE_FIELD_NAME" ),
73 QObject::tr(
"Cluster size field name" ), QStringLiteral(
"CLUSTER_SIZE" ) );
75 addParameter( sizeFieldNameParam.release() );
82QString QgsDbscanClusteringAlgorithm::shortHelpString()
const
84 return QObject::tr(
"Clusters point features based on a 2D implementation of Density-based spatial clustering of applications with noise (DBSCAN) algorithm.\n\n"
85 "The algorithm requires two parameters, a minimum cluster size (“minPts”), and the maximum distance allowed between clustered points (“eps”)." );
88QgsDbscanClusteringAlgorithm *QgsDbscanClusteringAlgorithm::createInstance()
const
90 return new QgsDbscanClusteringAlgorithm();
93struct KDBushDataEqualById
101struct KDBushDataHashById
105 return std::hash< QgsFeatureId > {}( a.
id );
111 std::unique_ptr< QgsProcessingFeatureSource > source( parameterAsSource( parameters, QStringLiteral(
"INPUT" ), context ) );
115 const std::size_t minSize =
static_cast< std::size_t
>( parameterAsInt( parameters, QStringLiteral(
"MIN_SIZE" ), context ) );
116 const double eps1 = parameterAsDouble( parameters, QStringLiteral(
"EPS" ), context );
117 const double eps2 = parameterAsDouble( parameters, QStringLiteral(
"EPS2" ), context );
118 const bool borderPointsAreNoise = parameterAsBoolean( parameters, QStringLiteral(
"DBSCAN*" ), context );
120 QgsFields outputFields = source->fields();
122 const QString clusterFieldName = parameterAsString( parameters, QStringLiteral(
"FIELD_NAME" ), context );
123 newFields.
append(
QgsField( clusterFieldName, QMetaType::Type::Int ) );
124 const QString clusterSizeFieldName = parameterAsString( parameters, QStringLiteral(
"SIZE_FIELD_NAME" ), context );
125 newFields.
append(
QgsField( clusterSizeFieldName, QMetaType::Type::Int ) );
129 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral(
"OUTPUT" ), context, dest, outputFields, source->wkbType(), source->sourceCrs() ) );
135 std::unordered_map< QgsFeatureId, QDateTime> idToDateTime;
136 const QString dateTimeFieldName = parameterAsString( parameters, QStringLiteral(
"DATETIME_FIELD" ), context );
137 int dateTimefieldIndex = -1;
138 if ( !dateTimeFieldName.isEmpty() )
140 dateTimefieldIndex = source->fields().lookupField( dateTimeFieldName );
141 if ( dateTimefieldIndex == -1 )
152 feedback->
pushInfo( QObject::tr(
"Building spatial index" ) );
156 if ( dateTimefieldIndex >= 0 )
157 idToDateTime[ feature.
id() ] = feature.
attributes().at( dateTimefieldIndex ).toDateTime();
162 return QVariantMap();
165 feedback->
pushInfo( QObject::tr(
"Analysing clusters" ) );
166 std::unordered_map< QgsFeatureId, int> idToCluster;
167 idToCluster.reserve( index.size() );
168 const long featureCount = source->featureCount();
170 stdbscan( minSize, eps1, eps2, borderPointsAreNoise, featureCount, features, index, idToCluster, idToDateTime, feedback );
173 std::unordered_map< int, int> clusterSize;
174 std::for_each( idToCluster.begin(), idToCluster.end(), [ &clusterSize ]( std::pair< QgsFeatureId, int > idCluster ) { clusterSize[ idCluster.second ]++; } );
177 const double writeStep = featureCount > 0 ? 10.0 / featureCount : 1;
178 features = source->getFeatures();
191 const auto cluster = idToCluster.find( feat.
id() );
192 if ( cluster != idToCluster.end() )
194 attr << cluster->second << clusterSize[ cluster->second ];
198 attr << QVariant() << QVariant();
206 outputs.insert( QStringLiteral(
"OUTPUT" ), dest );
207 outputs.insert( QStringLiteral(
"NUM_CLUSTERS" ),
static_cast< unsigned int >( clusterSize.size() ) );
211void QgsDbscanClusteringAlgorithm::stdbscan(
const std::size_t minSize,
214 const bool borderPointsAreNoise,
215 const long featureCount,
218 std::unordered_map< QgsFeatureId, int> &idToCluster,
219 std::unordered_map< QgsFeatureId, QDateTime> &idToDateTime,
222 const double step = featureCount > 0 ? 90.0 / featureCount : 1;
224 std::unordered_set< QgsFeatureId > visited;
225 visited.reserve( index.
size() );
229 int clusterCount = 0;
244 if ( visited.find( feat.
id() ) != visited.end() )
261 if ( !idToDateTime.empty() && !idToDateTime[ feat.
id() ].isValid() )
269 std::unordered_set< QgsSpatialIndexKDBushData, KDBushDataHashById, KDBushDataEqualById> within;
275 if ( idToDateTime.empty() || ( idToDateTime[ data.id ].isValid() && std::abs( idToDateTime[ pointId ].msecsTo( idToDateTime[ data.id ] ) ) <= eps2 ) )
276 within.insert( data );
278 if ( within.size() < minSize )
281 visited.insert( feat.
id() );
291 idToCluster[ feat.
id() ] = clusterCount;
294 while ( !within.empty() )
302 within.erase( within.begin() );
304 if ( visited.find( j.
id ) != visited.end() )
310 visited.insert( j.
id );
316 std::unordered_set< QgsSpatialIndexKDBushData, KDBushDataHashById, KDBushDataEqualById > within2;
319 if ( idToDateTime.empty() || ( idToDateTime[ data.id ].isValid() && std::abs( idToDateTime[ point2Id ].msecsTo( idToDateTime[ data.id ] ) ) <= eps2 ) )
320 within2.insert( data );
323 if ( within2.size() >= minSize )
326 std::copy_if( within2.begin(),
328 std::inserter( within, within.end() ),
331 return visited.find( needle.id ) == visited.end();
334 if ( !borderPointsAreNoise || within2.size() >= minSize )
336 idToCluster[ j.
id ] = clusterCount;
@ VectorPoint
Vector point layers.
@ Advanced
Parameter is an advanced parameter which should be hidden from users by default.
Wrapper for iterator of features from vector data provider or vector layer.
bool nextFeature(QgsFeature &f)
Fetch next feature and stores in f, returns true on success.
This class wraps a request for features to a vector layer (or directly its vector data provider).
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
QgsFeatureRequest & setNoAttributes()
Set that no attributes will be fetched.
@ FastInsert
Use faster inserts, at the cost of updating the passed features to reflect changes made at the provid...
The feature class encapsulates a single feature including its unique ID, geometry and a list of field...
void setAttributes(const QgsAttributes &attrs)
Sets the feature's attributes.
bool hasGeometry() const
Returns true if the feature has an associated geometry.
bool isCanceled() const
Tells whether the operation has been canceled already.
void setProgress(double progress)
Sets the current progress for the feedback object.
Encapsulate a field in an attribute table or data source.
Container of fields for a vector layer.
bool append(const QgsField &field, Qgis::FieldOrigin origin=Qgis::FieldOrigin::Provider, int originIndex=-1)
Appends a field.
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
Qgis::WkbType wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
A class to represent a 2D point.
Contains information about the context in which a processing algorithm is executed.
Custom exception class for processing related exceptions.
Base class for providing feedback from a processing algorithm.
virtual void pushInfo(const QString &info)
Pushes a general informational message from the algorithm.
virtual void reportError(const QString &error, bool fatalError=false)
Reports that the algorithm encountered an error while executing.
A numeric output for processing algorithms.
A double numeric parameter for distance values.
A feature sink output for processing algorithms.
An input feature source (such as vector layers) parameter for processing algorithms.
A numeric parameter for processing algorithms.
static QgsFields combineFields(const QgsFields &fieldsA, const QgsFields &fieldsB, const QString &fieldsBPrefix=QString())
Combines two field lists, avoiding duplicate field names (in a case-insensitive manner).
A container for data stored inside a QgsSpatialIndexKDBush index.
QgsFeatureId id
Feature ID.
QgsPointXY point() const
Returns the indexed point.
A very fast static spatial index for 2D points based on a flat KD-tree.
qgssize size() const
Returns the size of the index, i.e.
QList< QgsSpatialIndexKDBushData > within(const QgsPointXY &point, double radius) const
Returns the list of features which are within the given search radius of point.
static QString displayString(Qgis::WkbType type)
Returns a non-translated display string type for a WKB type, e.g., the geometry name used in WKT geom...
static Qgis::WkbType flatType(Qgis::WkbType type)
Returns the flat type for a WKB type.
QList< int > QgsAttributeList