20 #include <unordered_set>
24 QString QgsDbscanClusteringAlgorithm::name()
const
26 return QStringLiteral(
"dbscanclustering" );
29 QString QgsDbscanClusteringAlgorithm::displayName()
const
31 return QObject::tr(
"DBSCAN clustering" );
34 QString QgsDbscanClusteringAlgorithm::shortDescription()
const
36 return QObject::tr(
"Clusters point features using a density based scan algorithm." );
39 QStringList QgsDbscanClusteringAlgorithm::tags()
const
41 return QObject::tr(
"clustering,clusters,density,based,points" ).split(
',' );
44 QString QgsDbscanClusteringAlgorithm::group()
const
46 return QObject::tr(
"Vector analysis" );
49 QString QgsDbscanClusteringAlgorithm::groupId()
const
51 return QStringLiteral(
"vectoranalysis" );
54 void QgsDbscanClusteringAlgorithm::initAlgorithm(
const QVariantMap & )
61 QObject::tr(
"Maximum distance between clustered points" ), 1, QStringLiteral(
"INPUT" ),
false, 0 ) );
63 auto dbscanStarParam = qgis::make_unique<QgsProcessingParameterBoolean>( QStringLiteral(
"DBSCAN*" ),
64 QObject::tr(
"Treat border points as noise (DBSCAN*)" ),
false,
true );
66 addParameter( dbscanStarParam.release() );
68 auto fieldNameParam = qgis::make_unique<QgsProcessingParameterString>( QStringLiteral(
"FIELD_NAME" ),
69 QObject::tr(
"Cluster field name" ), QStringLiteral(
"CLUSTER_ID" ) );
71 addParameter( fieldNameParam.release() );
72 auto sizeFieldNameParam = qgis::make_unique<QgsProcessingParameterString>( QStringLiteral(
"SIZE_FIELD_NAME" ),
73 QObject::tr(
"Cluster size field name" ), QStringLiteral(
"CLUSTER_SIZE" ) );
75 addParameter( sizeFieldNameParam.release() );
82 QString 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”)." );
88 QgsDbscanClusteringAlgorithm *QgsDbscanClusteringAlgorithm::createInstance()
const
90 return new QgsDbscanClusteringAlgorithm();
93 struct KDBushDataEqualById
101 struct 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 eps = parameterAsDouble( parameters, QStringLiteral(
"EPS" ), context );
117 const bool borderPointsAreNoise = parameterAsBoolean( parameters, QStringLiteral(
"DBSCAN*" ), context );
119 QgsFields outputFields = source->fields();
121 const QString clusterFieldName = parameterAsString( parameters, QStringLiteral(
"FIELD_NAME" ), context );
123 const QString clusterSizeFieldName = parameterAsString( parameters, QStringLiteral(
"SIZE_FIELD_NAME" ), context );
124 newFields.
append(
QgsField( clusterSizeFieldName, QVariant::Int ) );
128 std::unique_ptr< QgsFeatureSink > sink( parameterAsSink( parameters, QStringLiteral(
"OUTPUT" ), context, dest, outputFields, source->wkbType(), source->sourceCrs() ) );
133 feedback->
pushInfo( QObject::tr(
"Building spatial index" ) );
136 return QVariantMap();
139 feedback->
pushInfo( QObject::tr(
"Analysing clusters" ) );
140 std::unordered_map< QgsFeatureId, int> idToCluster;
141 idToCluster.reserve( index.size() );
143 const long featureCount = source->featureCount();
144 dbscan( minSize, eps, borderPointsAreNoise, featureCount, features, index, idToCluster, feedback );
147 std::unordered_map< int, int> clusterSize;
148 std::for_each( idToCluster.begin(), idToCluster.end(), [ &clusterSize ]( std::pair< QgsFeatureId, int > idCluster ) { clusterSize[ idCluster.second ]++; } );
151 const double writeStep = featureCount > 0 ? 10.0 / featureCount : 1;
152 features = source->getFeatures();
165 auto cluster = idToCluster.find( feat.
id() );
166 if ( cluster != idToCluster.end() )
168 attr << cluster->second << clusterSize[ cluster->second ];
172 attr << QVariant() << QVariant();
179 outputs.insert( QStringLiteral(
"OUTPUT" ), dest );
180 outputs.insert( QStringLiteral(
"NUM_CLUSTERS" ),
static_cast< unsigned int >( clusterSize.size() ) );
185 void QgsDbscanClusteringAlgorithm::dbscan(
const std::size_t minSize,
187 const bool borderPointsAreNoise,
188 const long featureCount,
191 std::unordered_map< QgsFeatureId, int> &idToCluster,
194 const double step = featureCount > 0 ? 90.0 / featureCount : 1;
196 std::unordered_set< QgsFeatureId > visited;
197 visited.reserve( index.
size() );
201 int clusterCount = 0;
216 if ( visited.find( feat.
id() ) != visited.end() )
233 std::unordered_set< QgsSpatialIndexKDBushData, KDBushDataHashById, KDBushDataEqualById> within;
239 within.insert( data );
241 if ( within.size() < minSize )
244 visited.insert( feat.
id() );
254 idToCluster[ feat.
id() ] = clusterCount;
257 while ( !within.empty() )
265 within.erase( within.begin() );
267 if ( visited.find( j.
id ) != visited.end() )
273 visited.insert( j.
id );
279 std::unordered_set< QgsSpatialIndexKDBushData, KDBushDataHashById, KDBushDataEqualById > within2;
282 within2.insert( data );
284 if ( within2.size() >= minSize )
287 std::copy_if( within2.begin(),
289 std::inserter( within, within.end() ),
292 return visited.find( needle.id ) == visited.end();
295 if ( !borderPointsAreNoise || within2.size() >= minSize )
297 idToCluster[ j.
id ] = clusterCount;
Wrapper for iterator of features from vector data provider or vector layer.
bool nextFeature(QgsFeature &f)
This class wraps a request for features to a vector layer (or directly its vector data provider).
@ 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 id, geometry and a list of field/values...
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, FieldOrigin origin=OriginProvider, int originIndex=-1)
Appends a field. The field must have unique name, otherwise it is rejected (returns false)
const QgsAbstractGeometry * constGet() const SIP_HOLDGIL
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
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.
@ FlagAdvanced
Parameter is an advanced parameter which should be hidden from users by default.
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).
@ TypeVectorPoint
Vector point layers.
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(Type type) SIP_HOLDGIL
Returns a non-translated display string type for a WKB type, e.g., the geometry name used in WKT geom...
static Type flatType(Type type) SIP_HOLDGIL
Returns the flat type for a WKB type.