QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
Loading...
Searching...
No Matches
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 "palexception.h"
34#include "costcalculator.h"
35#include "feature.h"
36#include "geomfunction.h"
37#include "labelposition.h"
38#include "problem.h"
39#include "pointset.h"
40#include "internalexception.h"
41#include "util.h"
42#include "palrtree.h"
43#include "qgslabelingengine.h"
44#include "qgsrendercontext.h"
46#include "qgsruntimeprofiler.h"
48
49#include <cfloat>
50#include <list>
51
52
53using namespace pal;
54
55const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitPoints = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-points" ), sTreePal, 0 );
56const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitLines = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-lines" ), sTreePal, 0 );
57const QgsSettingsEntryInteger *Pal::settingsRenderingLabelCandidatesLimitPolygons = new QgsSettingsEntryInteger( QStringLiteral( "label-candidates-limit-polygons" ), sTreePal, 0 );
58
59
61{
62 mGlobalCandidatesLimitPoint = Pal::settingsRenderingLabelCandidatesLimitPoints->value();
63 mGlobalCandidatesLimitLine = Pal::settingsRenderingLabelCandidatesLimitLines->value();
64 mGlobalCandidatesLimitPolygon = Pal::settingsRenderingLabelCandidatesLimitPolygons->value();
65}
66
67Pal::~Pal() = default;
68
69void Pal::removeLayer( Layer *layer )
70{
71 if ( !layer )
72 return;
73
74 mMutex.lock();
75
76 for ( auto it = mLayers.begin(); it != mLayers.end(); ++it )
77 {
78 if ( it->second.get() == layer )
79 {
80 mLayers.erase( it );
81 break;
82 }
83 }
84 mMutex.unlock();
85}
86
87Layer *Pal::addLayer( QgsAbstractLabelProvider *provider, const QString &layerName, Qgis::LabelPlacement arrangement, double defaultPriority, bool active, bool toLabel )
88{
89 mMutex.lock();
90
91 Q_ASSERT( mLayers.find( provider ) == mLayers.end() );
92
93 std::unique_ptr< Layer > layer = std::make_unique< Layer >( provider, layerName, arrangement, defaultPriority, active, toLabel, this );
94 Layer *res = layer.get();
95 mLayers.insert( std::pair<QgsAbstractLabelProvider *, std::unique_ptr< Layer >>( provider, std::move( layer ) ) );
96 mMutex.unlock();
97
98 // cppcheck-suppress returnDanglingLifetime
99 return res;
100}
101
102std::unique_ptr<Problem> Pal::extractProblem( const QgsRectangle &extent, const QgsGeometry &mapBoundary, QgsRenderContext &context )
103{
104 QgsLabelingEngineFeedback *feedback = qobject_cast< QgsLabelingEngineFeedback * >( context.feedback() );
105 QgsLabelingEngineContext labelContext( context );
106 labelContext.setExtent( extent );
107 labelContext.setMapBoundaryGeometry( mapBoundary );
108
109 std::unique_ptr< QgsScopedRuntimeProfile > extractionProfile;
111 {
112 extractionProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Placing labels" ), QStringLiteral( "rendering" ) );
113 }
114
115 // expand out the incoming buffer by 1000x -- that's the visible map extent, yet we may be getting features which exceed this extent
116 // (while 1000x may seem excessive here, this value is only used for scaling coordinates in the spatial indexes
117 // and the consequence of inserting coordinates outside this extent is worse than the consequence of setting this value too large.)
118 const QgsRectangle maxCoordinateExtentForSpatialIndices = extent.buffered( std::max( extent.width(), extent.height() ) * 1000 );
119
120 // to store obstacles
121 PalRtree< FeaturePart > obstacles( maxCoordinateExtentForSpatialIndices );
122 PalRtree< LabelPosition > allCandidatesFirstRound( maxCoordinateExtentForSpatialIndices );
123 std::vector< FeaturePart * > allObstacleParts;
124 std::unique_ptr< Problem > prob = std::make_unique< Problem >( maxCoordinateExtentForSpatialIndices );
125
126 double bbx[4];
127 double bby[4];
128
129 bbx[0] = bbx[3] = prob->mMapExtentBounds[0] = extent.xMinimum();
130 bby[0] = bby[1] = prob->mMapExtentBounds[1] = extent.yMinimum();
131 bbx[1] = bbx[2] = prob->mMapExtentBounds[2] = extent.xMaximum();
132 bby[2] = bby[3] = prob->mMapExtentBounds[3] = extent.yMaximum();
133
134 prob->pal = this;
135
136 std::list< std::unique_ptr< Feats > > features;
137
138 // prepare map boundary
139 geos::unique_ptr mapBoundaryGeos( QgsGeos::asGeos( mapBoundary ) );
140 geos::prepared_unique_ptr mapBoundaryPrepared( GEOSPrepare_r( QgsGeosContext::get(), mapBoundaryGeos.get() ) );
141
142 int obstacleCount = 0;
143
144 // first step : extract features from layers
145
146 std::size_t previousFeatureCount = 0;
147 int previousObstacleCount = 0;
148
149 QStringList layersWithFeaturesInBBox;
150
151 QMutexLocker palLocker( &mMutex );
152
153 double step = !mLayers.empty() ? 100.0 / mLayers.size() : 1;
154 int index = -1;
155 std::unique_ptr< QgsScopedRuntimeProfile > candidateProfile;
157 {
158 candidateProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Generating label candidates" ), QStringLiteral( "rendering" ) );
159 }
160
161 for ( const auto &it : mLayers )
162 {
163 index++;
164 if ( feedback )
165 feedback->setProgress( index * step );
166
167 Layer *layer = it.second.get();
168 if ( !layer )
169 {
170 // invalid layer name
171 continue;
172 }
173
174 // only select those who are active
175 if ( !layer->active() )
176 continue;
177
178 if ( feedback )
179 feedback->emit candidateCreationAboutToBegin( it.first );
180
181 std::unique_ptr< QgsScopedRuntimeProfile > layerProfile;
183 {
184 layerProfile = std::make_unique< QgsScopedRuntimeProfile >( it.first->providerId(), QStringLiteral( "rendering" ) );
185 }
186
187 // check for connected features with the same label text and join them
188 if ( layer->mergeConnectedLines() )
189 layer->joinConnectedFeatures();
190
191 if ( isCanceled() )
192 return nullptr;
193
195
196 if ( isCanceled() )
197 return nullptr;
198
199 QMutexLocker locker( &layer->mMutex );
200
201 const double featureStep = !layer->mFeatureParts.empty() ? step / layer->mFeatureParts.size() : 1;
202 std::size_t featureIndex = 0;
203 // generate candidates for all features
204 for ( const std::unique_ptr< FeaturePart > &featurePart : std::as_const( layer->mFeatureParts ) )
205 {
206 if ( feedback )
207 feedback->setProgress( index * step + featureIndex * featureStep );
208 featureIndex++;
209
210 if ( isCanceled() )
211 break;
212
213 // Holes of the feature are obstacles
214 for ( int i = 0; i < featurePart->getNumSelfObstacles(); i++ )
215 {
216 FeaturePart *selfObstacle = featurePart->getSelfObstacle( i );
217 obstacles.insert( selfObstacle, selfObstacle->boundingBox() );
218 allObstacleParts.emplace_back( selfObstacle );
219
220 if ( !featurePart->getSelfObstacle( i )->getHoleOf() )
221 {
222 //ERROR: SHOULD HAVE A PARENT!!!!!
223 }
224 }
225
226 // generate candidates for the feature part
227 std::vector< std::unique_ptr< LabelPosition > > candidates = featurePart->createCandidates( this );
228
229 if ( isCanceled() )
230 break;
231
232 // purge candidates that violate known constraints, eg
233 // - they are outside the bbox
234 // - they violate a labeling rule
235 candidates.erase( std::remove_if( candidates.begin(), candidates.end(), [&mapBoundaryPrepared, &labelContext, this]( std::unique_ptr< LabelPosition > &candidate )
236 {
237 if ( showPartialLabels() )
238 {
239 if ( !candidate->intersects( mapBoundaryPrepared.get() ) )
240 return true;
241 }
242 else
243 {
244 if ( !candidate->within( mapBoundaryPrepared.get() ) )
245 return true;
246 }
247
248 for ( QgsAbstractLabelingEngineRule *rule : std::as_const( mRules ) )
249 {
250 if ( rule->candidateIsIllegal( candidate.get(), labelContext ) )
251 {
252 return true;
253 }
254 }
255 return false;
256 } ), candidates.end() );
257
258 if ( isCanceled() )
259 break;
260
261 if ( !candidates.empty() )
262 {
263 for ( std::unique_ptr< LabelPosition > &candidate : candidates )
264 {
265 candidate->insertIntoIndex( allCandidatesFirstRound );
266 candidate->setGlobalId( mNextCandidateId++ );
267 }
268
269 std::sort( candidates.begin(), candidates.end(), CostCalculator::candidateSortGrow );
270
271 // valid features are added to fFeats
272 std::unique_ptr< Feats > ft = std::make_unique< Feats >();
273 ft->feature = featurePart.get();
274 ft->shape = nullptr;
275 ft->candidates = std::move( candidates );
276 ft->priority = featurePart->calculatePriority();
277 features.emplace_back( std::move( ft ) );
278 }
279 else
280 {
281 // no candidates, so generate a default "point on surface" one
282 std::unique_ptr< LabelPosition > unplacedPosition = featurePart->createCandidatePointOnSurface( featurePart.get() );
283 if ( !unplacedPosition )
284 continue;
285
286 if ( featurePart->feature()->allowDegradedPlacement() )
287 {
288 // if we are allowing degraded placements, we throw the default candidate in too
289 unplacedPosition->insertIntoIndex( allCandidatesFirstRound );
290 unplacedPosition->setGlobalId( mNextCandidateId++ );
291 candidates.emplace_back( std::move( unplacedPosition ) );
292
293 // valid features are added to fFeats
294 std::unique_ptr< Feats > ft = std::make_unique< Feats >();
295 ft->feature = featurePart.get();
296 ft->shape = nullptr;
297 ft->candidates = std::move( candidates );
298 ft->priority = featurePart->calculatePriority();
299 features.emplace_back( std::move( ft ) );
300 }
301 else
302 {
303 // not displaying all labels for this layer, so it goes into the unlabeled feature list
304 prob->positionsWithNoCandidates()->emplace_back( std::move( unplacedPosition ) );
305 }
306 }
307 }
308 if ( isCanceled() )
309 return nullptr;
310
311 // collate all layer obstacles
312 for ( FeaturePart *obstaclePart : std::as_const( layer->mObstacleParts ) )
313 {
314 if ( isCanceled() )
315 break; // do not continue searching
316
317 // insert into obstacles
318 obstacles.insert( obstaclePart, obstaclePart->boundingBox() );
319 allObstacleParts.emplace_back( obstaclePart );
320 obstacleCount++;
321 }
322
323 if ( isCanceled() )
324 return nullptr;
325
326 locker.unlock();
327
328 if ( features.size() - previousFeatureCount > 0 || obstacleCount > previousObstacleCount )
329 {
330 layersWithFeaturesInBBox << layer->name();
331 }
332 previousFeatureCount = features.size();
333 previousObstacleCount = obstacleCount;
334
335 if ( feedback )
336 feedback->emit candidateCreationFinished( it.first );
337 }
338
339 candidateProfile.reset();
340
341 palLocker.unlock();
342
343 if ( isCanceled() )
344 return nullptr;
345
346 prob->mLayerCount = layersWithFeaturesInBBox.size();
347 prob->labelledLayersName = layersWithFeaturesInBBox;
348
349 prob->mFeatureCount = features.size();
350 prob->mTotalCandidates = 0;
351 prob->mCandidateCountForFeature.resize( prob->mFeatureCount );
352 prob->mFirstCandidateIndexForFeature.resize( prob->mFeatureCount );
353 prob->mUnlabeledCostForFeature.resize( prob->mFeatureCount );
354
355 if ( !features.empty() )
356 {
357 if ( feedback )
358 feedback->emit obstacleCostingAboutToBegin();
359
360 std::unique_ptr< QgsScopedRuntimeProfile > costingProfile;
361 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
362 {
363 costingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Assigning label costs" ), QStringLiteral( "rendering" ) );
364 }
365
366 // allow rules to alter candidate costs
367 for ( const auto &feature : features )
368 {
369 for ( auto &candidate : feature->candidates )
370 {
371 for ( QgsAbstractLabelingEngineRule *rule : std::as_const( mRules ) )
372 {
373 rule->alterCandidateCost( candidate.get(), labelContext );
374 }
375 }
376 }
377
378 // Filtering label positions against obstacles
379 index = -1;
380 step = !allObstacleParts.empty() ? 100.0 / allObstacleParts.size() : 1;
381
382 for ( FeaturePart *obstaclePart : allObstacleParts )
383 {
384 index++;
385 if ( feedback )
386 feedback->setProgress( step * index );
387
388 if ( isCanceled() )
389 break; // do not continue searching
390
391 allCandidatesFirstRound.intersects( obstaclePart->boundingBox(), [obstaclePart, this]( const LabelPosition * candidatePosition ) -> bool
392 {
393 // test whether we should ignore this obstacle for the candidate. We do this if:
394 // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (e.g.,
395 // features aren't obstacles for their own labels)
396 // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (e.g., holes
397 // are ONLY obstacles for the labels of the feature they belong to)
398 // 3. The label is set to "Always Allow" overlap mode
399 if ( candidatePosition->getFeaturePart()->feature()->overlapHandling() == Qgis::LabelOverlapHandling::AllowOverlapAtNoCost
400 || ( !obstaclePart->getHoleOf() && candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( obstaclePart ) )
401 || ( obstaclePart->getHoleOf() && !candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( dynamic_cast< FeaturePart * >( obstaclePart->getHoleOf() ) ) ) )
402 {
403 return true;
404 }
405
406 CostCalculator::addObstacleCostPenalty( const_cast< LabelPosition * >( candidatePosition ), obstaclePart, this );
407 return true;
408 } );
409 }
410
411 if ( feedback )
412 feedback->emit obstacleCostingFinished();
413 costingProfile.reset();
414
415 if ( isCanceled() )
416 {
417 return nullptr;
418 }
419
420 step = prob->mFeatureCount != 0 ? 100.0 / prob->mFeatureCount : 1;
421 if ( feedback )
422 feedback->emit calculatingConflictsAboutToBegin();
423
424 std::unique_ptr< QgsScopedRuntimeProfile > conflictProfile;
425 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
426 {
427 conflictProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Calculating conflicts" ), QStringLiteral( "rendering" ) );
428 }
429
430 int currentLabelPositionIndex = 0;
431 // loop through all the features registered in the problem
432 for ( std::size_t featureIndex = 0; featureIndex < prob->mFeatureCount; featureIndex++ )
433 {
434 if ( feedback )
435 feedback->setProgress( static_cast< double >( featureIndex ) * step );
436
437 std::unique_ptr< Feats > feat = std::move( features.front() );
438 features.pop_front();
439
440 prob->mFirstCandidateIndexForFeature[featureIndex] = currentLabelPositionIndex;
441 prob->mUnlabeledCostForFeature[featureIndex] = std::pow( 2, 10 - 10 * feat->priority );
442
443 std::size_t maxCandidates = 0;
444 switch ( feat->feature->getGeosType() )
445 {
446 case GEOS_POINT:
447 // this is usually 0, i.e. no maximum
448 maxCandidates = feat->feature->maximumPointCandidates();
449 break;
450
451 case GEOS_LINESTRING:
452 maxCandidates = feat->feature->maximumLineCandidates();
453 break;
454
455 case GEOS_POLYGON:
456 maxCandidates = std::max( static_cast< std::size_t >( 16 ), feat->feature->maximumPolygonCandidates() );
457 break;
458 }
459
460 if ( isCanceled() )
461 return nullptr;
462
463 auto pruneHardConflicts = [&]
464 {
465 switch ( mPlacementVersion )
466 {
468 break;
469
471 {
472 // v2 placement rips out candidates where the candidate cost is too high when compared to
473 // their inactive cost
474
475 // note, we start this at the SECOND candidate (you'll see why after this loop)
476 feat->candidates.erase( std::remove_if( feat->candidates.begin() + 1, feat->candidates.end(), [ & ]( std::unique_ptr< LabelPosition > &candidate )
477 {
478 if ( candidate->hasHardObstacleConflict() )
479 {
480 return true;
481 }
482 return false;
483 } ), feat->candidates.end() );
484
485 if ( feat->candidates.size() == 1 && feat->candidates[ 0 ]->hasHardObstacleConflict() )
486 {
487 switch ( feat->feature->feature()->overlapHandling() )
488 {
490 {
491 // we're going to end up removing ALL candidates for this label. Oh well, that's allowed. We just need to
492 // make sure we move this last candidate to the unplaced labels list
493 prob->positionsWithNoCandidates()->emplace_back( std::move( feat->candidates.front() ) );
494 feat->candidates.clear();
495 break;
496 }
497
500 // we can't avoid overlaps for this label, but in this mode we are allowing overlaps as a last resort.
501 // => don't discard this last remaining candidate.
502 break;
503 }
504 }
505 }
506 }
507 };
508
509 // if we're not showing all labels (including conflicts) for this layer, then we prune the candidates
510 // upfront to avoid extra work...
511 switch ( feat->feature->feature()->overlapHandling() )
512 {
514 pruneHardConflicts();
515 break;
516
519 break;
520 }
521
522 if ( feat->candidates.empty() )
523 continue;
524
525 // calculate final costs
526 CostCalculator::finalizeCandidatesCosts( feat.get(), bbx, bby );
527
528 // sort candidates list, best label to worst
529 std::sort( feat->candidates.begin(), feat->candidates.end(), CostCalculator::candidateSortGrow );
530
531 // but if we ARE showing all labels (including conflicts), let's go ahead and prune them now.
532 // Since we've calculated all their costs and sorted them, if we've hit the situation that ALL
533 // candidates have conflicts, then at least when we pick the first candidate to display it will be
534 // the lowest cost (i.e. best possible) overlapping candidate...
535 switch ( feat->feature->feature()->overlapHandling() )
536 {
538 break;
541 pruneHardConflicts();
542 break;
543 }
544
545 // only keep the 'maxCandidates' best candidates
546 if ( maxCandidates > 0 && feat->candidates.size() > maxCandidates )
547 {
548 feat->candidates.resize( maxCandidates );
549 }
550
551 if ( isCanceled() )
552 return nullptr;
553
554 // update problem's # candidate
555 prob->mCandidateCountForFeature[featureIndex] = static_cast< int >( feat->candidates.size() );
556 prob->mTotalCandidates += static_cast< int >( feat->candidates.size() );
557
558 // add all candidates into a rtree (to speed up conflicts searching)
559 for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
560 {
561 candidate->insertIntoIndex( prob->allCandidatesIndex() );
562 candidate->setProblemIds( static_cast< int >( featureIndex ), currentLabelPositionIndex++ );
563 }
564 features.emplace_back( std::move( feat ) );
565 }
566
567 if ( feedback )
568 feedback->emit calculatingConflictsFinished();
569
570 conflictProfile.reset();
571
572 int nbOverlaps = 0;
573
574 if ( feedback )
575 feedback->emit finalizingCandidatesAboutToBegin();
576
577 std::unique_ptr< QgsScopedRuntimeProfile > finalizingProfile;
578 if ( context.flags() & Qgis::RenderContextFlag::RecordProfile )
579 {
580 finalizingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Finalizing labels" ), QStringLiteral( "rendering" ) );
581 }
582
583 index = -1;
584 step = !features.empty() ? 100.0 / features.size() : 1;
585 while ( !features.empty() ) // for each feature
586 {
587 index++;
588 if ( feedback )
589 feedback->setProgress( step * index );
590
591 if ( isCanceled() )
592 return nullptr;
593
594 std::unique_ptr< Feats > feat = std::move( features.front() );
595 features.pop_front();
596
597 for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
598 {
599 std::unique_ptr< LabelPosition > lp = std::move( candidate );
600
601 lp->resetNumOverlaps();
602
603 // make sure that candidate's cost is less than 1
604 lp->validateCost();
605
606 //prob->feat[idlp] = j;
607
608 // lookup for overlapping candidate
609 const QgsRectangle searchBounds = lp->boundingBoxForCandidateConflicts( this );
610 prob->allCandidatesIndex().intersects( searchBounds, [&lp, this]( const LabelPosition * lp2 )->bool
611 {
612 if ( candidatesAreConflicting( lp.get(), lp2 ) )
613 {
614 lp->incrementNumOverlaps();
615 }
616
617 return true;
618
619 } );
620
621 nbOverlaps += lp->getNumOverlaps();
622
623 prob->addCandidatePosition( std::move( lp ) );
624
625 if ( isCanceled() )
626 return nullptr;
627 }
628 }
629
630 if ( feedback )
631 feedback->emit finalizingCandidatesFinished();
632
633 finalizingProfile.reset();
634
635 nbOverlaps /= 2;
636 prob->mAllNblp = prob->mTotalCandidates;
637 prob->mNbOverlap = nbOverlaps;
638 }
639
640 return prob;
641}
642
644{
645 fnIsCanceled = fnCanceled;
646 fnIsCanceledContext = context;
647}
648
649
650QList<LabelPosition *> Pal::solveProblem( Problem *prob, QgsRenderContext &context, bool displayAll, QList<LabelPosition *> *unlabeled )
651{
652 QgsLabelingEngineFeedback *feedback = qobject_cast< QgsLabelingEngineFeedback * >( context.feedback() );
653
654 if ( !prob )
655 return QList<LabelPosition *>();
656
657 std::unique_ptr< QgsScopedRuntimeProfile > calculatingProfile;
659 {
660 calculatingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Calculating optimal labeling" ), QStringLiteral( "rendering" ) );
661 }
662
663 if ( feedback )
664 feedback->emit reductionAboutToBegin();
665
666 {
667 std::unique_ptr< QgsScopedRuntimeProfile > reductionProfile;
669 {
670 reductionProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Reducing labeling" ), QStringLiteral( "rendering" ) );
671 }
672
673 prob->reduce();
674 }
675
676 if ( feedback )
677 feedback->emit reductionFinished();
678
679 if ( feedback )
680 feedback->emit solvingPlacementAboutToBegin();
681
682 {
683 std::unique_ptr< QgsScopedRuntimeProfile > solvingProfile;
685 {
686 solvingProfile = std::make_unique< QgsScopedRuntimeProfile >( QObject::tr( "Solving labeling" ), QStringLiteral( "rendering" ) );
687 }
688 try
689 {
690 prob->chainSearch( context );
691 }
692 catch ( InternalException::Empty & )
693 {
694 return QList<LabelPosition *>();
695 }
696 }
697
698 if ( feedback )
699 feedback->emit solvingPlacementFinished();
700
701 return prob->getSolution( displayAll, unlabeled );
702}
703
704void Pal::setMinIt( int min_it )
705{
706 if ( min_it >= 0 )
707 mTabuMinIt = min_it;
708}
709
710void Pal::setMaxIt( int max_it )
711{
712 if ( max_it > 0 )
713 mTabuMaxIt = max_it;
714}
715
716void Pal::setPopmusicR( int r )
717{
718 if ( r > 0 )
719 mPopmusicR = r;
720}
721
722void Pal::setEjChainDeg( int degree )
723{
724 this->mEjChainDeg = degree;
725}
726
727void Pal::setTenure( int tenure )
728{
729 this->mTenure = tenure;
730}
731
732void Pal::setCandListSize( double fact )
733{
734 this->mCandListSize = fact;
735}
736
738{
739 this->mShowPartialLabels = show;
740}
741
743{
744 return mPlacementVersion;
745}
746
748{
749 mPlacementVersion = placementVersion;
750}
751
753{
754 // we cache the value -- this can be costly to calculate, and we check this multiple times
755 // per candidate during the labeling problem solving
756
757 if ( lp1->getProblemFeatureId() == lp2->getProblemFeatureId() )
758 return false;
759
760 // conflicts are commutative - so we always store them in the cache using the smaller id as the first element of the key pair
761 auto key = qMakePair( std::min( lp1->globalId(), lp2->globalId() ), std::max( lp1->globalId(), lp2->globalId() ) );
762 auto it = mCandidateConflicts.constFind( key );
763 if ( it != mCandidateConflicts.constEnd() )
764 return *it;
765
766 bool res = false;
767 for ( QgsAbstractLabelingEngineRule *rule : mRules )
768 {
769 if ( rule->candidatesAreConflicting( lp1, lp2 ) )
770 {
771 res = true;
772 break;
773 }
774 }
775
776 res |= lp1->isInConflict( lp2 );
777
778 mCandidateConflicts.insert( key, res );
779 return res;
780}
781
782void Pal::setRules( const QList<QgsAbstractLabelingEngineRule *> &rules )
783{
784 mRules = rules;
785}
786
787int Pal::getMinIt() const
788{
789 return mTabuMaxIt;
790}
791
792int Pal::getMaxIt() const
793{
794 return mTabuMinIt;
795}
796
798{
799 return mShowPartialLabels;
800}
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:1125
@ RecordProfile
Enable run-time profiling while rendering.
LabelPlacementEngineVersion
Labeling placement engine version.
Definition qgis.h:2670
@ 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.
The QgsAbstractLabelProvider class is an interface class.
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
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.
A rectangle specified with double values.
double xMinimum() const
Returns the x minimum value (left side of rectangle).
bool intersects(const QgsRectangle &rect) const
Returns true when rectangle intersects with other rectangle.
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
double width() const
Returns the width of the rectangle.
double xMaximum() const
Returns the x maximum value (right side of rectangle).
double yMaximum() const
Returns the y maximum value (top side of rectangle).
double height() const
Returns the height of the rectangle.
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.
Main class to handle feature.
Definition feature.h:65
FeaturePart * getSelfObstacle(int i)
Gets hole (inner ring) - considered as obstacle.
Definition feature.h:307
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.
unsigned int globalId() const
Returns the global ID for the candidate, which is unique for a single run of the pal labelling engine...
int getProblemFeatureId() const
A set of features which influence the labeling process.
Definition layer.h:63
QMutex mMutex
Definition layer.h:345
std::deque< std::unique_ptr< FeaturePart > > mFeatureParts
List of feature parts.
Definition layer.h:316
bool active() const
Returns whether the layer is currently active.
Definition layer.h:198
bool mergeConnectedLines() const
Returns whether connected lines will be merged before labeling.
Definition layer.h:256
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:747
void setShowPartialLabels(bool show)
Sets whether partial labels show be allowed.
Definition pal.cpp:737
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:102
Qgis::LabelPlacementEngineVersion placementVersion() const
Returns the placement engine version, which dictates how the label placement problem is solved.
Definition pal.cpp:742
void setRules(const QList< QgsAbstractLabelingEngineRule * > &rules)
Sets rules which the labeling solution must satisfy.
Definition pal.cpp:782
void removeLayer(Layer *layer)
remove a layer
Definition pal.cpp:69
bool candidatesAreConflicting(const LabelPosition *lp1, const LabelPosition *lp2) const
Returns true if a labelling candidate lp1 conflicts with lp2.
Definition pal.cpp:752
bool(* FnIsCanceled)(void *ctx)
Definition pal.h:122
bool showPartialLabels() const
Returns whether partial labels should be allowed.
Definition pal.cpp:797
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:60
bool isCanceled()
Check whether the job has been canceled.
Definition pal.h:128
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:650
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:643
QList< QgsAbstractLabelingEngineRule * > rules() const
Returns the rules which the labeling solution must satisify.
Definition pal.h:278
Layer * addLayer(QgsAbstractLabelProvider *provider, const QString &layerName, Qgis::LabelPlacement arrangement, double defaultPriority, bool active, bool toLabel)
add a new layer
Definition pal.cpp:87
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