QGIS API Documentation 3.43.0-Master (58029bba303)
pal.cpp
Go to the documentation of this file.
1/*
2 * libpal - Automated Placement of Labels Library
3 *
4 * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5 * University of Applied Sciences, Western Switzerland
6 * http://www.hes-so.ch
7 *
8 * Contact:
9 * maxence.laurent <at> heig-vd <dot> ch
10 * or
11 * eric.taillard <at> heig-vd <dot> ch
12 *
13 * This file is part of libpal.
14 *
15 * libpal is free software: you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation, either version 3 of the License, or
18 * (at your option) any later version.
19 *
20 * libpal is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
24 *
25 * You should have received a copy of the GNU General Public License
26 * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27 *
28 */
29
30#include "qgsgeometry.h"
31#include "pal.h"
32#include "layer.h"
33#include "costcalculator.h"
34#include "feature.h"
35#include "geomfunction.h"
36#include "labelposition.h"
37#include "problem.h"
38#include "pointset.h"
39#include "internalexception.h"
40#include "util.h"
41#include "palrtree.h"
42#include "qgslabelingengine.h"
43#include "qgsrendercontext.h"
45#include "qgsruntimeprofiler.h"
47#if ( GEOS_VERSION_MAJOR == 3 && GEOS_VERSION_MINOR<10 )
48#include "qgsmessagelog.h"
49#endif
50#include <cfloat>
51#include <list>
52
53
54using namespace pal;
55
56const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitPoints = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-points" ), sTreePal, 0 );
57const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitLines = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-lines" ), sTreePal, 0 );
58const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitPolygons = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-polygons" ), sTreePal, 0 );
59
60
62{
63 mGlobalCandidatesLimitPoint = Pal::settingsRenderingLabelCandidatesLimitPoints->value();
64 mGlobalCandidatesLimitLine = Pal::settingsRenderingLabelCandidatesLimitLines->value();
65 mGlobalCandidatesLimitPolygon = Pal::settingsRenderingLabelCandidatesLimitPolygons->value();
66}
67
68Pal::~Pal() = default;
69
70void Pal::removeLayer( Layer *layer )
71{
72 if ( !layer )
73 return;
74
75 mMutex.lock();
76
77 for ( auto it = mLayers.begin(); it != mLayers.end(); ++it )
78 {
79 if ( it->second.get() == layer )
80 {
81 mLayers.erase( it );
82 break;
83 }
84 }
85 mMutex.unlock();
86}
87
88Layer *Pal::addLayer( QgsAbstractLabelProvider *provider, const QString &layerName, Qgis::LabelPlacement arrangement, double defaultPriority, bool active, bool toLabel )
89{
90 mMutex.lock();
91
92#ifdef QGISDEBUG
93 for ( const auto &it : mLayers )
94 {
95 Q_ASSERT( it.first != provider );
96 }
97#endif
98
99 auto layer = std::make_unique< Layer >( provider, layerName, arrangement, defaultPriority, active, toLabel, this );
100 Layer *res = layer.get();
101 mLayers.emplace_back( std::make_pair( provider, std::move( layer ) ) );
102 mMutex.unlock();
103
104 // cppcheck-suppress returnDanglingLifetime
105 return res;
106}
107
108std::unique_ptr<Problem> Pal::extractProblem( const QgsRectangle &extent, const QgsGeometry &mapBoundary, QgsRenderContext &context )
109{
110 QgsLabelingEngineFeedback *feedback = qobject_cast< QgsLabelingEngineFeedback * >( context.feedback() );
111 QgsLabelingEngineContext labelContext( context );
112 labelContext.setExtent( extent );
113 labelContext.setMapBoundaryGeometry( mapBoundary );
114
115 std::unique_ptr< QgsScopedRuntimeProfile > extractionProfile;
117 {
118 extractionProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Placing labels" ), QStringLiteral( "rendering" ) );
119 }
120
121 // expand out the incoming buffer by 1000x -- that's the visible map extent, yet we may be getting features which exceed this extent
122 // (while 1000x may seem excessive here, this value is only used for scaling coordinates in the spatial indexes
123 // and the consequence of inserting coordinates outside this extent is worse than the consequence of setting this value too large.)
124 const QgsRectangle maxCoordinateExtentForSpatialIndices = extent.buffered( std::max( extent.width(), extent.height() ) * 1000 );
125
126 // to store obstacles
127 PalRtree< FeaturePart > obstacles( maxCoordinateExtentForSpatialIndices );
128 PalRtree< LabelPosition > allCandidatesFirstRound( maxCoordinateExtentForSpatialIndices );
129 std::vector< FeaturePart * > allObstacleParts;
130 auto prob = std::make_unique< Problem >( maxCoordinateExtentForSpatialIndices );
131
132 double bbx[4];
133 double bby[4];
134
135 bbx[0] = bbx[3] = prob->mMapExtentBounds[0] = extent.xMinimum();
136 bby[0] = bby[1] = prob->mMapExtentBounds[1] = extent.yMinimum();
137 bbx[1] = bbx[2] = prob->mMapExtentBounds[2] = extent.xMaximum();
138 bby[2] = bby[3] = prob->mMapExtentBounds[3] = extent.yMaximum();
139
140 prob->pal = this;
141
142 std::list< std::unique_ptr< Feats > > features;
143
144 // prepare map boundary
145 geos::unique_ptr mapBoundaryGeos( QgsGeos::asGeos( mapBoundary ) );
146 geos::prepared_unique_ptr mapBoundaryPrepared( GEOSPrepare_r( QgsGeosContext::get(), mapBoundaryGeos.get() ) );
147
148 int obstacleCount = 0;
149
150 // first step : extract features from layers
151
152 std::size_t previousFeatureCount = 0;
153 int previousObstacleCount = 0;
154
155 QStringList layersWithFeaturesInBBox;
156
157 QMutexLocker palLocker( &mMutex );
158
159 double step = !mLayers.empty() ? 100.0 / mLayers.size() : 1;
160 int index = -1;
161 std::unique_ptr< QgsScopedRuntimeProfile > candidateProfile;
163 {
164 candidateProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Generating label candidates" ), QStringLiteral( "rendering" ) );
165 }
166
167 for ( auto it = mLayers.rbegin(); it != mLayers.rend(); ++it )
168 {
169 index++;
170 if ( feedback )
171 feedback->setProgress( index * step );
172
173 Layer *layer = it->second.get();
174 if ( !layer )
175 {
176 // invalid layer name
177 continue;
178 }
179
180 // only select those who are active
181 if ( !layer->active() )
182 continue;
183
184 if ( feedback )
185 feedback->emit candidateCreationAboutToBegin( it->first );
186
187 std::unique_ptr< QgsScopedRuntimeProfile > layerProfile;
189 {
190 layerProfile = std::make_unique< QgsScopedRuntimeProfile >( it->first->providerId(), QStringLiteral( "rendering" ) );
191 }
192
193 // check for connected features with the same label text and join them
194 if ( layer->mergeConnectedLines() )
195 layer->joinConnectedFeatures();
196
197 if ( isCanceled() )
198 return nullptr;
199
201
202 if ( isCanceled() )
203 return nullptr;
204
205 QMutexLocker locker( &layer->mMutex );
206
207 const double featureStep = !layer->mFeatureParts.empty() ? step / layer->mFeatureParts.size() : 1;
208 std::size_t featureIndex = 0;
209 // generate candidates for all features
210 for ( const std::unique_ptr< FeaturePart > &featurePart : std::as_const( layer->mFeatureParts ) )
211 {
212 if ( feedback )
213 feedback->setProgress( index * step + featureIndex * featureStep );
214 featureIndex++;
215
216 if ( isCanceled() )
217 break;
218
219 // Holes of the feature are obstacles
220 for ( int i = 0; i < featurePart->getNumSelfObstacles(); i++ )
221 {
222 FeaturePart *selfObstacle = featurePart->getSelfObstacle( i );
223 obstacles.insert( selfObstacle, selfObstacle->boundingBox() );
224 allObstacleParts.emplace_back( selfObstacle );
225
226 if ( !featurePart->getSelfObstacle( i )->getHoleOf() )
227 {
228 //ERROR: SHOULD HAVE A PARENT!!!!!
229 }
230 }
231
232 // generate candidates for the feature part
233 std::vector< std::unique_ptr< LabelPosition > > candidates = featurePart->createCandidates( this );
234
235 if ( isCanceled() )
236 break;
237
238 // purge candidates that violate known constraints, eg
239 // - they are outside the bbox
240 // - they violate a labeling rule
241 candidates.erase( std::remove_if( candidates.begin(), candidates.end(), [&mapBoundaryPrepared, &labelContext, this]( std::unique_ptr< LabelPosition > &candidate )
242 {
243 if ( showPartialLabels() )
244 {
245 if ( !candidate->intersects( mapBoundaryPrepared.get() ) )
246 return true;
247 }
248 else
249 {
250 if ( !candidate->within( mapBoundaryPrepared.get() ) )
251 return true;
252 }
253
254 for ( QgsAbstractLabelingEngineRule *rule : std::as_const( mRules ) )
255 {
256 if ( rule->candidateIsIllegal( candidate.get(), labelContext ) )
257 {
258 return true;
259 }
260 }
261 return false;
262 } ), candidates.end() );
263
264 if ( isCanceled() )
265 break;
266
267 if ( !candidates.empty() )
268 {
269 for ( std::unique_ptr< LabelPosition > &candidate : candidates )
270 {
271 candidate->insertIntoIndex( allCandidatesFirstRound, this );
272 candidate->setGlobalId( mNextCandidateId++ );
273 }
274
275 std::sort( candidates.begin(), candidates.end(), CostCalculator::candidateSortGrow );
276
277 // valid features are added to fFeats
278 auto ft = std::make_unique< Feats >();
279 ft->feature = featurePart.get();
280 ft->shape = nullptr;
281 ft->candidates = std::move( candidates );
282 ft->priority = featurePart->calculatePriority();
283 features.emplace_back( std::move( ft ) );
284 }
285 else
286 {
287 // no candidates, so generate a default "point on surface" one
288 std::unique_ptr< LabelPosition > unplacedPosition = featurePart->createCandidatePointOnSurface( featurePart.get() );
289 if ( !unplacedPosition )
290 continue;
291
292 if ( featurePart->feature()->allowDegradedPlacement() )
293 {
294 // if we are allowing degraded placements, we throw the default candidate in too
295 unplacedPosition->insertIntoIndex( allCandidatesFirstRound, this );
296 unplacedPosition->setGlobalId( mNextCandidateId++ );
297 candidates.emplace_back( std::move( unplacedPosition ) );
298
299 // valid features are added to fFeats
300 auto ft = std::make_unique< Feats >();
301 ft->feature = featurePart.get();
302 ft->shape = nullptr;
303 ft->candidates = std::move( candidates );
304 ft->priority = featurePart->calculatePriority();
305 features.emplace_back( std::move( ft ) );
306 }
307 else
308 {
309 // not displaying all labels for this layer, so it goes into the unlabeled feature list
310 prob->positionsWithNoCandidates()->emplace_back( std::move( unplacedPosition ) );
311 }
312 }
313 }
314 if ( isCanceled() )
315 return nullptr;
316
317 // collate all layer obstacles
318 for ( FeaturePart *obstaclePart : std::as_const( layer->mObstacleParts ) )
319 {
320 if ( isCanceled() )
321 break; // do not continue searching
322
323 // insert into obstacles
324 obstacles.insert( obstaclePart, obstaclePart->boundingBox() );
325 allObstacleParts.emplace_back( obstaclePart );
326 obstacleCount++;
327 }
328
329 if ( isCanceled() )
330 return nullptr;
331
332 locker.unlock();
333
334 if ( features.size() - previousFeatureCount > 0 || obstacleCount > previousObstacleCount )
335 {
336 layersWithFeaturesInBBox << layer->name();
337 }
338 previousFeatureCount = features.size();
339 previousObstacleCount = obstacleCount;
340
341 if ( feedback )
342 feedback->emit candidateCreationFinished( it->first );
343 }
344
345 candidateProfile.reset();
346
347 palLocker.unlock();
348
349 if ( isCanceled() )
350 return nullptr;
351
352 prob->mLayerCount = layersWithFeaturesInBBox.size();
353 prob->labelledLayersName = layersWithFeaturesInBBox;
354
355 prob->mFeatureCount = features.size();
356 prob->mTotalCandidates = 0;
357 prob->mCandidateCountForFeature.resize( prob->mFeatureCount );
358 prob->mFirstCandidateIndexForFeature.resize( prob->mFeatureCount );
359 prob->mUnlabeledCostForFeature.resize( prob->mFeatureCount );
360
361 if ( !features.empty() )
362 {
363 if ( feedback )
364 feedback->emit obstacleCostingAboutToBegin();
365
366 std::unique_ptr< QgsScopedRuntimeProfile > costingProfile;
367 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
368 {
369 costingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Assigning label costs" ), QStringLiteral( "rendering" ) );
370 }
371
372 // allow rules to alter candidate costs
373 for ( const auto &feature : features )
374 {
375 for ( auto &candidate : feature->candidates )
376 {
377 for ( QgsAbstractLabelingEngineRule *rule : std::as_const( mRules ) )
378 {
379 rule->alterCandidateCost( candidate.get(), labelContext );
380 }
381 }
382 }
383
384 // Filtering label positions against obstacles
385 index = -1;
386 step = !allObstacleParts.empty() ? 100.0 / allObstacleParts.size() : 1;
387
388 for ( FeaturePart *obstaclePart : allObstacleParts )
389 {
390 index++;
391 if ( feedback )
392 feedback->setProgress( step * index );
393
394 if ( isCanceled() )
395 break; // do not continue searching
396
397 allCandidatesFirstRound.intersects( obstaclePart->boundingBox(), [obstaclePart, this]( const LabelPosition * candidatePosition ) -> bool
398 {
399 // test whether we should ignore this obstacle for the candidate. We do this if:
400 // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (e.g.,
401 // features aren't obstacles for their own labels)
402 // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (e.g., holes
403 // are ONLY obstacles for the labels of the feature they belong to)
404 // 3. The label is set to "Always Allow" overlap mode
405 if ( candidatePosition->getFeaturePart()->feature()->overlapHandling() == Qgis::LabelOverlapHandling::AllowOverlapAtNoCost
406 || ( !obstaclePart->getHoleOf() && candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( obstaclePart ) )
407 || ( obstaclePart->getHoleOf() && !candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( dynamic_cast< FeaturePart * >( obstaclePart->getHoleOf() ) ) ) )
408 {
409 return true;
410 }
411
412 CostCalculator::addObstacleCostPenalty( const_cast< LabelPosition * >( candidatePosition ), obstaclePart, this );
413 return true;
414 } );
415 }
416
417 if ( feedback )
418 feedback->emit obstacleCostingFinished();
419 costingProfile.reset();
420
421 if ( isCanceled() )
422 {
423 return nullptr;
424 }
425
426 step = prob->mFeatureCount != 0 ? 100.0 / prob->mFeatureCount : 1;
427 if ( feedback )
428 feedback->emit calculatingConflictsAboutToBegin();
429
430 std::unique_ptr< QgsScopedRuntimeProfile > conflictProfile;
431 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
432 {
433 conflictProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Calculating conflicts" ), QStringLiteral( "rendering" ) );
434 }
435
436 int currentLabelPositionIndex = 0;
437 // loop through all the features registered in the problem
438 for ( std::size_t featureIndex = 0; featureIndex < prob->mFeatureCount; featureIndex++ )
439 {
440 if ( feedback )
441 feedback->setProgress( static_cast< double >( featureIndex ) * step );
442
443 std::unique_ptr< Feats > feat = std::move( features.front() );
444 features.pop_front();
445
446 prob->mFirstCandidateIndexForFeature[featureIndex] = currentLabelPositionIndex;
447 prob->mUnlabeledCostForFeature[featureIndex] = std::pow( 2, 10 - 10 * feat->priority );
448
449 std::size_t maxCandidates = 0;
450 switch ( feat->feature->getGeosType() )
451 {
452 case GEOS_POINT:
453 // this is usually 0, i.e. no maximum
454 maxCandidates = feat->feature->maximumPointCandidates();
455 break;
456
457 case GEOS_LINESTRING:
458 maxCandidates = feat->feature->maximumLineCandidates();
459 break;
460
461 case GEOS_POLYGON:
462 maxCandidates = std::max( static_cast< std::size_t >( 16 ), feat->feature->maximumPolygonCandidates() );
463 break;
464 }
465
466 if ( isCanceled() )
467 return nullptr;
468
469 auto pruneHardConflicts = [&]
470 {
471 switch ( mPlacementVersion )
472 {
474 break;
475
477 {
478 // v2 placement rips out candidates where the candidate cost is too high when compared to
479 // their inactive cost
480
481 // note, we start this at the SECOND candidate (you'll see why after this loop)
482 feat->candidates.erase( std::remove_if( feat->candidates.begin() + 1, feat->candidates.end(), [ & ]( std::unique_ptr< LabelPosition > &candidate )
483 {
484 if ( candidate->hasHardObstacleConflict() )
485 {
486 return true;
487 }
488 return false;
489 } ), feat->candidates.end() );
490
491 if ( feat->candidates.size() == 1 && feat->candidates[ 0 ]->hasHardObstacleConflict() )
492 {
493 switch ( feat->feature->feature()->overlapHandling() )
494 {
496 {
497 // we're going to end up removing ALL candidates for this label. Oh well, that's allowed. We just need to
498 // make sure we move this last candidate to the unplaced labels list
499 prob->positionsWithNoCandidates()->emplace_back( std::move( feat->candidates.front() ) );
500 feat->candidates.clear();
501 break;
502 }
503
506 // we can't avoid overlaps for this label, but in this mode we are allowing overlaps as a last resort.
507 // => don't discard this last remaining candidate.
508 break;
509 }
510 }
511 }
512 }
513 };
514
515 // if we're not showing all labels (including conflicts) for this layer, then we prune the candidates
516 // upfront to avoid extra work...
517 switch ( feat->feature->feature()->overlapHandling() )
518 {
520 pruneHardConflicts();
521 break;
522
525 break;
526 }
527
528 if ( feat->candidates.empty() )
529 continue;
530
531 // calculate final costs
532 CostCalculator::finalizeCandidatesCosts( feat.get(), bbx, bby );
533
534 // sort candidates list, best label to worst
535 std::sort( feat->candidates.begin(), feat->candidates.end(), CostCalculator::candidateSortGrow );
536
537 // but if we ARE showing all labels (including conflicts), let's go ahead and prune them now.
538 // Since we've calculated all their costs and sorted them, if we've hit the situation that ALL
539 // candidates have conflicts, then at least when we pick the first candidate to display it will be
540 // the lowest cost (i.e. best possible) overlapping candidate...
541 switch ( feat->feature->feature()->overlapHandling() )
542 {
544 break;
547 pruneHardConflicts();
548 break;
549 }
550
551 // only keep the 'maxCandidates' best candidates
552 if ( maxCandidates > 0 && feat->candidates.size() > maxCandidates )
553 {
554 feat->candidates.resize( maxCandidates );
555 }
556
557 if ( isCanceled() )
558 return nullptr;
559
560 // update problem's # candidate
561 prob->mCandidateCountForFeature[featureIndex] = static_cast< int >( feat->candidates.size() );
562 prob->mTotalCandidates += static_cast< int >( feat->candidates.size() );
563
564 // add all candidates into a rtree (to speed up conflicts searching)
565 for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
566 {
567 candidate->insertIntoIndex( prob->allCandidatesIndex(), this );
568 candidate->setProblemIds( static_cast< int >( featureIndex ), currentLabelPositionIndex++ );
569 }
570 features.emplace_back( std::move( feat ) );
571 }
572
573 if ( feedback )
574 feedback->emit calculatingConflictsFinished();
575
576 conflictProfile.reset();
577
578 int nbOverlaps = 0;
579
580 if ( feedback )
581 feedback->emit finalizingCandidatesAboutToBegin();
582
583 std::unique_ptr< QgsScopedRuntimeProfile > finalizingProfile;
584 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
585 {
586 finalizingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Finalizing labels" ), QStringLiteral( "rendering" ) );
587 }
588
589 index = -1;
590 step = !features.empty() ? 100.0 / features.size() : 1;
591 while ( !features.empty() ) // for each feature
592 {
593 index++;
594 if ( feedback )
595 feedback->setProgress( step * index );
596
597 if ( isCanceled() )
598 return nullptr;
599
600 std::unique_ptr< Feats > feat = std::move( features.front() );
601 features.pop_front();
602
603 for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
604 {
605 std::unique_ptr< LabelPosition > lp = std::move( candidate );
606
607 lp->resetNumOverlaps();
608
609 // make sure that candidate's cost is less than 1
610 lp->validateCost();
611
612 //prob->feat[idlp] = j;
613
614 // lookup for overlapping candidate
615 const QgsRectangle searchBounds = lp->boundingBoxForCandidateConflicts( this );
616 prob->allCandidatesIndex().intersects( searchBounds, [&lp, this]( const LabelPosition * lp2 )->bool
617 {
618 if ( candidatesAreConflicting( lp.get(), lp2 ) )
619 {
620 lp->incrementNumOverlaps();
621 }
622
623 return true;
624
625 } );
626
627 nbOverlaps += lp->getNumOverlaps();
628
629 prob->addCandidatePosition( std::move( lp ) );
630
631 if ( isCanceled() )
632 return nullptr;
633 }
634 }
635
636 if ( feedback )
637 feedback->emit finalizingCandidatesFinished();
638
639 finalizingProfile.reset();
640
641 nbOverlaps /= 2;
642 prob->mAllNblp = prob->mTotalCandidates;
643 prob->mNbOverlap = nbOverlaps;
644 }
645
646 return prob;
647}
648
650{
651 fnIsCanceled = fnCanceled;
652 fnIsCanceledContext = context;
653}
654
655
656QList<LabelPosition *> Pal::solveProblem( Problem *prob, QgsRenderContext &context, bool displayAll, QList<LabelPosition *> *unlabeled )
657{
658 QgsLabelingEngineFeedback *feedback = qobject_cast< QgsLabelingEngineFeedback * >( context.feedback() );
659
660 if ( !prob )
661 return QList<LabelPosition *>();
662
663 std::unique_ptr< QgsScopedRuntimeProfile > calculatingProfile;
665 {
666 calculatingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Calculating optimal labeling" ), QStringLiteral( "rendering" ) );
667 }
668
669 if ( feedback )
670 feedback->emit reductionAboutToBegin();
671
672 {
673 std::unique_ptr< QgsScopedRuntimeProfile > reductionProfile;
675 {
676 reductionProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Reducing labeling" ), QStringLiteral( "rendering" ) );
677 }
678
679 prob->reduce();
680 }
681
682 if ( feedback )
683 feedback->emit reductionFinished();
684
685 if ( feedback )
686 feedback->emit solvingPlacementAboutToBegin();
687
688 {
689 std::unique_ptr< QgsScopedRuntimeProfile > solvingProfile;
691 {
692 solvingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Solving labeling" ), QStringLiteral( "rendering" ) );
693 }
694 try
695 {
696 prob->chainSearch( context );
697 }
698 catch ( InternalException::Empty & )
699 {
700 return QList<LabelPosition *>();
701 }
702 }
703
704 if ( feedback )
705 feedback->emit solvingPlacementFinished();
706
707 return prob->getSolution( displayAll, unlabeled );
708}
709
710void Pal::setMinIt( int min_it )
711{
712 if ( min_it >= 0 )
713 mTabuMinIt = min_it;
714}
715
716void Pal::setMaxIt( int max_it )
717{
718 if ( max_it > 0 )
719 mTabuMaxIt = max_it;
720}
721
722void Pal::setPopmusicR( int r )
723{
724 if ( r > 0 )
725 mPopmusicR = r;
726}
727
728void Pal::setEjChainDeg( int degree )
729{
730 this->mEjChainDeg = degree;
731}
732
733void Pal::setTenure( int tenure )
734{
735 this->mTenure = tenure;
736}
737
738void Pal::setCandListSize( double fact )
739{
740 this->mCandListSize = fact;
741}
742
744{
745 this->mShowPartialLabels = show;
746}
747
749{
750 return mPlacementVersion;
751}
752
754{
755 mPlacementVersion = placementVersion;
756}
757
759{
760 // we cache the value -- this can be costly to calculate, and we check this multiple times
761 // per candidate during the labeling problem solving
762
763 if ( lp1->getProblemFeatureId() == lp2->getProblemFeatureId() )
764 return false;
765
766 // conflicts are commutative - so we always store them in the cache using the smaller id as the first element of the key pair
767 auto key = qMakePair( std::min( lp1->globalId(), lp2->globalId() ), std::max( lp1->globalId(), lp2->globalId() ) );
768 auto it = mCandidateConflicts.constFind( key );
769 if ( it != mCandidateConflicts.constEnd() )
770 return *it;
771
772 bool res = false;
773
774 const double labelMarginDistance = std::max(
777 );
778
779 if ( labelMarginDistance > 0 )
780 {
781 GEOSContextHandle_t geosctxt = QgsGeosContext::get();
782 try
783 {
784#if GEOS_VERSION_MAJOR>3 || ( GEOS_VERSION_MAJOR == 3 && GEOS_VERSION_MINOR>=10 )
785 if ( GEOSPreparedDistanceWithin_r( geosctxt, lp1->preparedMultiPartGeom(), lp2->multiPartGeom(), labelMarginDistance ) )
786 {
787 res = true;
788 }
789#else
790 QgsMessageLog::logMessage( QStringLiteral( "label margin distance requires GEOS 3.10+" ) );
791#endif
792 }
793 catch ( GEOSException &e )
794 {
795 QgsDebugError( QStringLiteral( "GEOS exception: %1" ).arg( e.what() ) );
796 }
797 }
798
799 if ( !res )
800 {
801 for ( QgsAbstractLabelingEngineRule *rule : mRules )
802 {
803 if ( rule->candidatesAreConflicting( lp1, lp2 ) )
804 {
805 res = true;
806 break;
807 }
808 }
809 }
810
811 res |= lp1->isInConflict( lp2 );
812
813 mCandidateConflicts.insert( key, res );
814 return res;
815}
816
817void Pal::setRules( const QList<QgsAbstractLabelingEngineRule *> &rules )
818{
819 mRules = rules;
820}
821
822int Pal::getMinIt() const
823{
824 return mTabuMaxIt;
825}
826
827int Pal::getMaxIt() const
828{
829 return mTabuMinIt;
830}
831
833{
834 return mShowPartialLabels;
835}
A rtree spatial index for use in the pal labeling engine.
Definition palrtree.h:36
void insert(T *data, const QgsRectangle &bounds)
Inserts new data into the spatial index, with the specified bounds.
Definition palrtree.h:59
LabelPlacement
Placement modes which determine how label candidates are generated for a feature.
Definition qgis.h:1158
@ RecordProfile
Enable run-time profiling while rendering.
LabelPlacementEngineVersion
Labeling placement engine version.
Definition qgis.h:2787
@ Version2
Version 2 (default for new projects since QGIS 3.12)
@ Version1
Version 1, matches placement from QGIS <= 3.10.1.
@ AllowOverlapAtNoCost
Labels may freely overlap other labels, at no cost.
@ AllowOverlapIfRequired
Avoids overlapping labels when possible, but permit overlaps if labels for features cannot otherwise ...
@ PreventOverlap
Do not allow labels to overlap other labels.
An abstract interface class for label providers.
Abstract base class for labeling engine rules.
void setProgress(double progress)
Sets the current progress for the feedback object.
Definition qgsfeedback.h:61
A geometry is the spatial representation of a feature.
static GEOSContextHandle_t get()
Returns a thread local instance of a GEOS context, safe for use in the current thread.
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0, Qgis::GeosCreationFlags flags=Qgis::GeosCreationFlags())
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
Definition qgsgeos.cpp:257
double labelMarginDistance() const
Returns the minimum distance (in label units) between labels for this feature and other labels.
const QgsLabelFeatureThinningSettings & thinningSettings() const
Returns the thinning settings for this label.
Encapsulates the context for a labeling engine run.
void setMapBoundaryGeometry(const QgsGeometry &geometry)
Sets the map label boundary geometry, which defines the limits within which labels may be placed in t...
void setExtent(const QgsRectangle &extent)
Sets the map extent defining the limits for labeling.
QgsFeedback subclass for granular reporting of labeling engine progress.
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::MessageLevel::Warning, bool notifyUser=true, const char *file=__builtin_FILE(), const char *function=__builtin_FUNCTION(), int line=__builtin_LINE())
Adds a message to the log instance (and creates it if necessary).
A rectangle specified with double values.
double xMinimum
double yMinimum
double xMaximum
bool intersects(const QgsRectangle &rect) const
Returns true when rectangle intersects with other rectangle.
double yMaximum
QgsRectangle buffered(double width) const
Gets rectangle enlarged by buffer.
Contains information about the context of a rendering operation.
QgsFeedback * feedback() const
Returns the feedback object that can be queried regularly during rendering to check if rendering shou...
Qgis::RenderContextFlags flags() const
Returns combination of flags used for rendering.
T value(const QString &dynamicKeyPart=QString()) const
Returns settings value.
An integer settings entry.
static void addObstacleCostPenalty(pal::LabelPosition *lp, pal::FeaturePart *obstacle, Pal *pal)
Increase candidate's cost according to its collision with passed feature.
static void finalizeCandidatesCosts(Feats *feat, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
static bool candidateSortGrow(const std::unique_ptr< pal::LabelPosition > &c1, const std::unique_ptr< pal::LabelPosition > &c2)
Sorts label candidates in ascending order of cost.
Represents a part of a label feature.
Definition feature.h:58
QgsLabelFeature * feature()
Returns the parent feature.
Definition feature.h:87
FeaturePart * getSelfObstacle(int i)
Gets hole (inner ring) - considered as obstacle.
Definition feature.h:300
Thrown when trying to access an empty data set.
LabelPosition is a candidate feature label position.
bool isInConflict(const LabelPosition *ls) const
Check whether or not this overlap with another labelPosition.
const GEOSGeometry * multiPartGeom() const
Returns a GEOS representation of all label parts as a multipolygon.
unsigned int globalId() const
Returns the global ID for the candidate, which is unique for a single run of the pal labelling engine...
FeaturePart * getFeaturePart() const
Returns the feature corresponding to this labelposition.
const GEOSPreparedGeometry * preparedMultiPartGeom() const
Returns a prepared GEOS representation of all label parts as a multipolygon.
int getProblemFeatureId() const
A set of features which influence the labeling process.
Definition layer.h:62
QMutex mMutex
Definition layer.h:344
std::deque< std::unique_ptr< FeaturePart > > mFeatureParts
List of feature parts.
Definition layer.h:315
bool active() const
Returns whether the layer is currently active.
Definition layer.h:197
bool mergeConnectedLines() const
Returns whether connected lines will be merged before labeling.
Definition layer.h:255
void joinConnectedFeatures()
Join connected features with the same label text.
Definition layer.cpp:297
void chopFeaturesAtRepeatDistance()
Chop layer features at the repeat distance.
Definition layer.cpp:365
void setPlacementVersion(Qgis::LabelPlacementEngineVersion placementVersion)
Sets the placement engine version, which dictates how the label placement problem is solved.
Definition pal.cpp:753
void setShowPartialLabels(bool show)
Sets whether partial labels show be allowed.
Definition pal.cpp:743
std::unique_ptr< Problem > extractProblem(const QgsRectangle &extent, const QgsGeometry &mapBoundary, QgsRenderContext &context)
Extracts the labeling problem for the specified map extent - only features within this extent will be...
Definition pal.cpp:108
Qgis::LabelPlacementEngineVersion placementVersion() const
Returns the placement engine version, which dictates how the label placement problem is solved.
Definition pal.cpp:748
void setRules(const QList< QgsAbstractLabelingEngineRule * > &rules)
Sets rules which the labeling solution must satisfy.
Definition pal.cpp:817
void removeLayer(Layer *layer)
remove a layer
Definition pal.cpp:70
bool candidatesAreConflicting(const LabelPosition *lp1, const LabelPosition *lp2) const
Returns true if a labelling candidate lp1 conflicts with lp2.
Definition pal.cpp:758
bool(* FnIsCanceled)(void *ctx)
Cancelation check callback function.
Definition pal.h:123
bool showPartialLabels() const
Returns whether partial labels should be allowed.
Definition pal.cpp:832
static const QgsSettingsEntryInteger * settingsRenderingLabelCandidatesLimitLines
Definition pal.h:92
static const QgsSettingsEntryInteger * settingsRenderingLabelCandidatesLimitPoints
Definition pal.h:91
static const QgsSettingsEntryInteger * settingsRenderingLabelCandidatesLimitPolygons
Definition pal.h:93
Pal()
Definition pal.cpp:61
bool isCanceled()
Check whether the job has been canceled.
Definition pal.h:129
QList< LabelPosition * > solveProblem(Problem *prob, QgsRenderContext &context, bool displayAll, QList< pal::LabelPosition * > *unlabeled=nullptr)
Solves the labeling problem, selecting the best candidate locations for all labels and returns a list...
Definition pal.cpp:656
void registerCancellationCallback(FnIsCanceled fnCanceled, void *context)
Register a function that returns whether this job has been canceled - PAL calls it during the computa...
Definition pal.cpp:649
QList< QgsAbstractLabelingEngineRule * > rules() const
Returns the rules which the labeling solution must satisify.
Definition pal.h:279
Layer * addLayer(QgsAbstractLabelProvider *provider, const QString &layerName, Qgis::LabelPlacement arrangement, double defaultPriority, bool active, bool toLabel)
add a new layer
Definition pal.cpp:88
QgsRectangle boundingBox() const
Returns the point set bounding box.
Definition pointset.h:163
Representation of a labeling problem.
Definition problem.h:73
QList< LabelPosition * > getSolution(bool returnInactive, QList< LabelPosition * > *unlabeled=nullptr)
Solves the labeling problem, selecting the best candidate locations for all labels and returns a list...
Definition problem.cpp:644
void chainSearch(QgsRenderContext &context)
Test with very-large scale neighborhood.
Definition problem.cpp:561
void reduce()
Gets called AFTER extractProblem.
Definition problem.cpp:71
#define QgsDebugError(str)
Definition qgslogger.h:40