Branch data Line data Source code
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 "palstat.h"
35 : : #include "costcalculator.h"
36 : : #include "feature.h"
37 : : #include "geomfunction.h"
38 : : #include "labelposition.h"
39 : : #include "problem.h"
40 : : #include "pointset.h"
41 : : #include "internalexception.h"
42 : : #include "util.h"
43 : : #include "palrtree.h"
44 : : #include "qgssettings.h"
45 : : #include <cfloat>
46 : : #include <list>
47 : :
48 : : using namespace pal;
49 : :
50 : 0 : Pal::Pal()
51 : : {
52 : 0 : QgsSettings settings;
53 : 0 : mGlobalCandidatesLimitPoint = settings.value( QStringLiteral( "rendering/label_candidates_limit_points" ), 0, QgsSettings::Core ).toInt();
54 : 0 : mGlobalCandidatesLimitLine = settings.value( QStringLiteral( "rendering/label_candidates_limit_lines" ), 0, QgsSettings::Core ).toInt();
55 : 0 : mGlobalCandidatesLimitPolygon = settings.value( QStringLiteral( "rendering/label_candidates_limit_polygons" ), 0, QgsSettings::Core ).toInt();
56 : 0 : }
57 : :
58 : 0 : Pal::~Pal() = default;
59 : :
60 : 0 : void Pal::removeLayer( Layer *layer )
61 : : {
62 : 0 : if ( !layer )
63 : 0 : return;
64 : :
65 : 0 : mMutex.lock();
66 : :
67 : 0 : for ( auto it = mLayers.begin(); it != mLayers.end(); ++it )
68 : : {
69 : 0 : if ( it->second.get() == layer )
70 : : {
71 : 0 : mLayers.erase( it );
72 : 0 : break;
73 : : }
74 : 0 : }
75 : 0 : mMutex.unlock();
76 : 0 : }
77 : :
78 : 0 : Layer *Pal::addLayer( QgsAbstractLabelProvider *provider, const QString &layerName, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, bool displayAll )
79 : : {
80 : 0 : mMutex.lock();
81 : :
82 : : Q_ASSERT( mLayers.find( provider ) == mLayers.end() );
83 : :
84 : 0 : std::unique_ptr< Layer > layer = std::make_unique< Layer >( provider, layerName, arrangement, defaultPriority, active, toLabel, this, displayAll );
85 : 0 : Layer *res = layer.get();
86 : 0 : mLayers.insert( std::pair<QgsAbstractLabelProvider *, std::unique_ptr< Layer >>( provider, std::move( layer ) ) );
87 : 0 : mMutex.unlock();
88 : :
89 : 0 : return res;
90 : 0 : }
91 : :
92 : 0 : std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeometry &mapBoundary )
93 : : {
94 : : // expand out the incoming buffer by 1000x -- that's the visible map extent, yet we may be getting features which exceed this extent
95 : : // (while 1000x may seem excessive here, this value is only used for scaling coordinates in the spatial indexes
96 : : // and the consequence of inserting coordinates outside this extent is worse than the consequence of setting this value too large.)
97 : 0 : const QgsRectangle maxCoordinateExtentForSpatialIndices = extent.buffered( std::max( extent.width(), extent.height() ) * 1000 );
98 : :
99 : : // to store obstacles
100 : 0 : PalRtree< FeaturePart > obstacles( maxCoordinateExtentForSpatialIndices );
101 : 0 : PalRtree< LabelPosition > allCandidatesFirstRound( maxCoordinateExtentForSpatialIndices );
102 : 0 : std::vector< FeaturePart * > allObstacleParts;
103 : 0 : std::unique_ptr< Problem > prob = std::make_unique< Problem >( maxCoordinateExtentForSpatialIndices );
104 : :
105 : : double bbx[4];
106 : : double bby[4];
107 : :
108 : 0 : bbx[0] = bbx[3] = prob->mMapExtentBounds[0] = extent.xMinimum();
109 : 0 : bby[0] = bby[1] = prob->mMapExtentBounds[1] = extent.yMinimum();
110 : 0 : bbx[1] = bbx[2] = prob->mMapExtentBounds[2] = extent.xMaximum();
111 : 0 : bby[2] = bby[3] = prob->mMapExtentBounds[3] = extent.yMaximum();
112 : :
113 : 0 : prob->pal = this;
114 : :
115 : 0 : std::list< std::unique_ptr< Feats > > features;
116 : :
117 : : // prepare map boundary
118 : 0 : geos::unique_ptr mapBoundaryGeos( QgsGeos::asGeos( mapBoundary ) );
119 : 0 : geos::prepared_unique_ptr mapBoundaryPrepared( GEOSPrepare_r( QgsGeos::getGEOSHandler(), mapBoundaryGeos.get() ) );
120 : :
121 : 0 : int obstacleCount = 0;
122 : :
123 : : // first step : extract features from layers
124 : :
125 : 0 : std::size_t previousFeatureCount = 0;
126 : 0 : int previousObstacleCount = 0;
127 : :
128 : 0 : QStringList layersWithFeaturesInBBox;
129 : :
130 : 0 : QMutexLocker palLocker( &mMutex );
131 : 0 : for ( const auto &it : mLayers )
132 : : {
133 : 0 : Layer *layer = it.second.get();
134 : 0 : if ( !layer )
135 : : {
136 : : // invalid layer name
137 : 0 : continue;
138 : : }
139 : :
140 : : // only select those who are active
141 : 0 : if ( !layer->active() )
142 : 0 : continue;
143 : :
144 : : // check for connected features with the same label text and join them
145 : 0 : if ( layer->mergeConnectedLines() )
146 : 0 : layer->joinConnectedFeatures();
147 : :
148 : 0 : if ( isCanceled() )
149 : 0 : return nullptr;
150 : :
151 : 0 : layer->chopFeaturesAtRepeatDistance();
152 : :
153 : 0 : if ( isCanceled() )
154 : 0 : return nullptr;
155 : :
156 : 0 : QMutexLocker locker( &layer->mMutex );
157 : :
158 : : // generate candidates for all features
159 : 0 : for ( const std::unique_ptr< FeaturePart > &featurePart : std::as_const( layer->mFeatureParts ) )
160 : : {
161 : 0 : if ( isCanceled() )
162 : 0 : break;
163 : :
164 : : // Holes of the feature are obstacles
165 : 0 : for ( int i = 0; i < featurePart->getNumSelfObstacles(); i++ )
166 : : {
167 : 0 : FeaturePart *selfObstacle = featurePart->getSelfObstacle( i );
168 : 0 : obstacles.insert( selfObstacle, selfObstacle->boundingBox() );
169 : 0 : allObstacleParts.emplace_back( selfObstacle );
170 : :
171 : 0 : if ( !featurePart->getSelfObstacle( i )->getHoleOf() )
172 : : {
173 : : //ERROR: SHOULD HAVE A PARENT!!!!!
174 : 0 : }
175 : 0 : }
176 : :
177 : : // generate candidates for the feature part
178 : 0 : std::vector< std::unique_ptr< LabelPosition > > candidates = featurePart->createCandidates( this );
179 : :
180 : 0 : if ( isCanceled() )
181 : 0 : break;
182 : :
183 : : // purge candidates that are outside the bbox
184 : 0 : candidates.erase( std::remove_if( candidates.begin(), candidates.end(), [&mapBoundaryPrepared, this]( std::unique_ptr< LabelPosition > &candidate )
185 : : {
186 : 0 : if ( showPartialLabels() )
187 : 0 : return !candidate->intersects( mapBoundaryPrepared.get() );
188 : : else
189 : 0 : return !candidate->within( mapBoundaryPrepared.get() );
190 : 0 : } ), candidates.end() );
191 : :
192 : 0 : if ( isCanceled() )
193 : 0 : break;
194 : :
195 : 0 : if ( !candidates.empty() )
196 : : {
197 : 0 : for ( std::unique_ptr< LabelPosition > &candidate : candidates )
198 : : {
199 : 0 : candidate->insertIntoIndex( allCandidatesFirstRound );
200 : 0 : candidate->setGlobalId( mNextCandidateId++ );
201 : : }
202 : :
203 : 0 : std::sort( candidates.begin(), candidates.end(), CostCalculator::candidateSortGrow );
204 : :
205 : : // valid features are added to fFeats
206 : 0 : std::unique_ptr< Feats > ft = std::make_unique< Feats >();
207 : 0 : ft->feature = featurePart.get();
208 : 0 : ft->shape = nullptr;
209 : 0 : ft->candidates = std::move( candidates );
210 : 0 : ft->priority = featurePart->calculatePriority();
211 : 0 : features.emplace_back( std::move( ft ) );
212 : 0 : }
213 : : else
214 : : {
215 : : // no candidates, so generate a default "point on surface" one
216 : 0 : std::unique_ptr< LabelPosition > unplacedPosition = featurePart->createCandidatePointOnSurface( featurePart.get() );
217 : 0 : if ( !unplacedPosition )
218 : 0 : continue;
219 : :
220 : 0 : if ( layer->displayAll() )
221 : : {
222 : : // if we are displaying all labels, we throw the default candidate in too
223 : 0 : unplacedPosition->insertIntoIndex( allCandidatesFirstRound );
224 : 0 : unplacedPosition->setGlobalId( mNextCandidateId++ );
225 : 0 : candidates.emplace_back( std::move( unplacedPosition ) );
226 : :
227 : : // valid features are added to fFeats
228 : 0 : std::unique_ptr< Feats > ft = std::make_unique< Feats >();
229 : 0 : ft->feature = featurePart.get();
230 : 0 : ft->shape = nullptr;
231 : 0 : ft->candidates = std::move( candidates );
232 : 0 : ft->priority = featurePart->calculatePriority();
233 : 0 : features.emplace_back( std::move( ft ) );
234 : 0 : }
235 : : else
236 : : {
237 : : // not displaying all labels for this layer, so it goes into the unlabeled feature list
238 : 0 : prob->positionsWithNoCandidates()->emplace_back( std::move( unplacedPosition ) );
239 : : }
240 : 0 : }
241 : 0 : }
242 : 0 : if ( isCanceled() )
243 : 0 : return nullptr;
244 : :
245 : : // collate all layer obstacles
246 : 0 : for ( FeaturePart *obstaclePart : std::as_const( layer->mObstacleParts ) )
247 : : {
248 : 0 : if ( isCanceled() )
249 : 0 : break; // do not continue searching
250 : :
251 : : // insert into obstacles
252 : 0 : obstacles.insert( obstaclePart, obstaclePart->boundingBox() );
253 : 0 : allObstacleParts.emplace_back( obstaclePart );
254 : 0 : obstacleCount++;
255 : : }
256 : :
257 : 0 : if ( isCanceled() )
258 : 0 : return nullptr;
259 : :
260 : 0 : locker.unlock();
261 : 0 :
262 : 0 : if ( features.size() - previousFeatureCount > 0 || obstacleCount > previousObstacleCount )
263 : 0 : {
264 : 0 : layersWithFeaturesInBBox << layer->name();
265 : 0 : }
266 : 0 : previousFeatureCount = features.size();
267 : 0 : previousObstacleCount = obstacleCount;
268 : 0 : }
269 : 0 : palLocker.unlock();
270 : :
271 : 0 : if ( isCanceled() )
272 : 0 : return nullptr;
273 : 0 :
274 : 0 : prob->mLayerCount = layersWithFeaturesInBBox.size();
275 : 0 : prob->labelledLayersName = layersWithFeaturesInBBox;
276 : 0 :
277 : 0 : prob->mFeatureCount = features.size();
278 : 0 : prob->mTotalCandidates = 0;
279 : 0 : prob->mFeatNbLp.resize( prob->mFeatureCount );
280 : 0 : prob->mFeatStartId.resize( prob->mFeatureCount );
281 : 0 : prob->mInactiveCost.resize( prob->mFeatureCount );
282 : 0 :
283 : 0 : if ( !features.empty() )
284 : : {
285 : 0 : // Filtering label positions against obstacles
286 : 0 : for ( FeaturePart *obstaclePart : allObstacleParts )
287 : 0 : {
288 : 0 : if ( isCanceled() )
289 : 0 : break; // do not continue searching
290 : :
291 : 0 : allCandidatesFirstRound.intersects( obstaclePart->boundingBox(), [obstaclePart, this]( const LabelPosition * candidatePosition ) -> bool
292 : : {
293 : : // test whether we should ignore this obstacle for the candidate. We do this if:
294 : : // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (e.g.,
295 : : // features aren't obstacles for their own labels)
296 : : // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (e.g., holes
297 : : // are ONLY obstacles for the labels of the feature they belong to)
298 : 0 : if ( ( !obstaclePart->getHoleOf() && candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( obstaclePart ) )
299 : 0 : || ( obstaclePart->getHoleOf() && !candidatePosition->getFeaturePart()->hasSameLabelFeatureAs( dynamic_cast< FeaturePart * >( obstaclePart->getHoleOf() ) ) ) )
300 : : {
301 : 0 : return true;
302 : : }
303 : :
304 : 0 : CostCalculator::addObstacleCostPenalty( const_cast< LabelPosition * >( candidatePosition ), obstaclePart, this );
305 : :
306 : 0 : return true;
307 : 0 : } );
308 : : }
309 : :
310 : 0 : if ( isCanceled() )
311 : : {
312 : 0 : return nullptr;
313 : : }
314 : :
315 : 0 : int idlp = 0;
316 : 0 : for ( std::size_t i = 0; i < prob->mFeatureCount; i++ ) /* for each feature into prob */
317 : : {
318 : 0 : std::unique_ptr< Feats > feat = std::move( features.front() );
319 : 0 : features.pop_front();
320 : :
321 : 0 : prob->mFeatStartId[i] = idlp;
322 : 0 : prob->mInactiveCost[i] = std::pow( 2, 10 - 10 * feat->priority );
323 : :
324 : 0 : std::size_t maxCandidates = 0;
325 : 0 : switch ( feat->feature->getGeosType() )
326 : : {
327 : : case GEOS_POINT:
328 : : // this is usually 0, i.e. no maximum
329 : 0 : maxCandidates = feat->feature->maximumPointCandidates();
330 : 0 : break;
331 : :
332 : : case GEOS_LINESTRING:
333 : 0 : maxCandidates = feat->feature->maximumLineCandidates();
334 : 0 : break;
335 : :
336 : : case GEOS_POLYGON:
337 : 0 : maxCandidates = std::max( static_cast< std::size_t >( 16 ), feat->feature->maximumPolygonCandidates() );
338 : 0 : break;
339 : : }
340 : :
341 : 0 : if ( isCanceled() )
342 : 0 : return nullptr;
343 : :
344 : 0 : auto pruneHardConflicts = [&]
345 : : {
346 : 0 : switch ( mPlacementVersion )
347 : : {
348 : : case QgsLabelingEngineSettings::PlacementEngineVersion1:
349 : 0 : break;
350 : :
351 : : case QgsLabelingEngineSettings::PlacementEngineVersion2:
352 : : {
353 : : // v2 placement rips out candidates where the candidate cost is too high when compared to
354 : : // their inactive cost
355 : :
356 : : // note, we start this at the SECOND candidate (you'll see why after this loop)
357 : 0 : feat->candidates.erase( std::remove_if( feat->candidates.begin() + 1, feat->candidates.end(), [ & ]( std::unique_ptr< LabelPosition > &candidate )
358 : : {
359 : 0 : if ( candidate->hasHardObstacleConflict() )
360 : : {
361 : 0 : return true;
362 : : }
363 : 0 : return false;
364 : 0 : } ), feat->candidates.end() );
365 : :
366 : 0 : if ( feat->candidates.size() == 1 && feat->candidates[ 0 ]->hasHardObstacleConflict() && !feat->feature->layer()->displayAll() )
367 : : {
368 : : // we've going to end up removing ALL candidates for this label. Oh well, that's allowed. We just need to
369 : : // make sure we move this last candidate to the unplaced labels list
370 : 0 : prob->positionsWithNoCandidates()->emplace_back( std::move( feat->candidates.front() ) );
371 : 0 : feat->candidates.clear();
372 : 0 : }
373 : : }
374 : 0 : }
375 : 0 : };
376 : :
377 : : // if we're not showing all labels (including conflicts) for this layer, then we prune the candidates
378 : : // upfront to avoid extra work...
379 : 0 : if ( !feat->feature->layer()->displayAll() )
380 : : {
381 : 0 : pruneHardConflicts();
382 : 0 : }
383 : :
384 : 0 : if ( feat->candidates.empty() )
385 : 0 : continue;
386 : :
387 : : // calculate final costs
388 : 0 : CostCalculator::finalizeCandidatesCosts( feat.get(), bbx, bby );
389 : :
390 : : // sort candidates list, best label to worst
391 : 0 : std::sort( feat->candidates.begin(), feat->candidates.end(), CostCalculator::candidateSortGrow );
392 : :
393 : : // but if we ARE showing all labels (including conflicts), let's go ahead and prune them now.
394 : : // Since we've calculated all their costs and sorted them, if we've hit the situation that ALL
395 : : // candidates have conflicts, then at least when we pick the first candidate to display it will be
396 : : // the lowest cost (i.e. best possible) overlapping candidate...
397 : 0 : if ( feat->feature->layer()->displayAll() )
398 : : {
399 : 0 : pruneHardConflicts();
400 : 0 : }
401 : :
402 : :
403 : : // only keep the 'maxCandidates' best candidates
404 : 0 : if ( maxCandidates > 0 && feat->candidates.size() > maxCandidates )
405 : : {
406 : 0 : feat->candidates.resize( maxCandidates );
407 : 0 : }
408 : :
409 : 0 : if ( isCanceled() )
410 : 0 : return nullptr;
411 : :
412 : : // update problem's # candidate
413 : 0 : prob->mFeatNbLp[i] = static_cast< int >( feat->candidates.size() );
414 : 0 : prob->mTotalCandidates += static_cast< int >( feat->candidates.size() );
415 : :
416 : : // add all candidates into a rtree (to speed up conflicts searching)
417 : 0 : for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
418 : : {
419 : 0 : candidate->insertIntoIndex( prob->allCandidatesIndex() );
420 : 0 : candidate->setProblemIds( static_cast< int >( i ), idlp++ );
421 : : }
422 : 0 : features.emplace_back( std::move( feat ) );
423 : 0 : }
424 : :
425 : 0 : int nbOverlaps = 0;
426 : :
427 : : double amin[2];
428 : : double amax[2];
429 : 0 : while ( !features.empty() ) // for each feature
430 : : {
431 : 0 : if ( isCanceled() )
432 : 0 : return nullptr;
433 : :
434 : 0 : std::unique_ptr< Feats > feat = std::move( features.front() );
435 : 0 : features.pop_front();
436 : :
437 : 0 : for ( std::unique_ptr< LabelPosition > &candidate : feat->candidates )
438 : : {
439 : 0 : std::unique_ptr< LabelPosition > lp = std::move( candidate );
440 : :
441 : 0 : lp->resetNumOverlaps();
442 : :
443 : : // make sure that candidate's cost is less than 1
444 : 0 : lp->validateCost();
445 : :
446 : : //prob->feat[idlp] = j;
447 : :
448 : : // lookup for overlapping candidate
449 : 0 : lp->getBoundingBox( amin, amax );
450 : 0 : prob->allCandidatesIndex().intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
451 : : {
452 : 0 : if ( candidatesAreConflicting( lp.get(), lp2 ) )
453 : : {
454 : 0 : lp->incrementNumOverlaps();
455 : 0 : }
456 : :
457 : 0 : return true;
458 : :
459 : : } );
460 : :
461 : 0 : nbOverlaps += lp->getNumOverlaps();
462 : :
463 : 0 : prob->addCandidatePosition( std::move( lp ) );
464 : :
465 : 0 : if ( isCanceled() )
466 : 0 : return nullptr;
467 : 0 : }
468 : 0 : }
469 : 0 : nbOverlaps /= 2;
470 : 0 : prob->mAllNblp = prob->mTotalCandidates;
471 : 0 : prob->mNbOverlap = nbOverlaps;
472 : 0 : }
473 : :
474 : 0 : return prob;
475 : 0 : }
476 : :
477 : 0 : void Pal::registerCancellationCallback( Pal::FnIsCanceled fnCanceled, void *context )
478 : : {
479 : 0 : fnIsCanceled = fnCanceled;
480 : 0 : fnIsCanceledContext = context;
481 : 0 : }
482 : :
483 : 0 : std::unique_ptr<Problem> Pal::extractProblem( const QgsRectangle &extent, const QgsGeometry &mapBoundary )
484 : : {
485 : 0 : return extract( extent, mapBoundary );
486 : : }
487 : :
488 : 0 : QList<LabelPosition *> Pal::solveProblem( Problem *prob, bool displayAll, QList<LabelPosition *> *unlabeled )
489 : : {
490 : 0 : if ( !prob )
491 : 0 : return QList<LabelPosition *>();
492 : :
493 : 0 : prob->reduce();
494 : :
495 : : try
496 : : {
497 : 0 : prob->chain_search();
498 : 0 : }
499 : : catch ( InternalException::Empty & )
500 : : {
501 : 0 : return QList<LabelPosition *>();
502 : 0 : }
503 : :
504 : 0 : return prob->getSolution( displayAll, unlabeled );
505 : 0 : }
506 : :
507 : 0 : void Pal::setMinIt( int min_it )
508 : : {
509 : 0 : if ( min_it >= 0 )
510 : 0 : mTabuMinIt = min_it;
511 : 0 : }
512 : :
513 : 0 : void Pal::setMaxIt( int max_it )
514 : : {
515 : 0 : if ( max_it > 0 )
516 : 0 : mTabuMaxIt = max_it;
517 : 0 : }
518 : :
519 : 0 : void Pal::setPopmusicR( int r )
520 : : {
521 : 0 : if ( r > 0 )
522 : 0 : mPopmusicR = r;
523 : 0 : }
524 : :
525 : 0 : void Pal::setEjChainDeg( int degree )
526 : : {
527 : 0 : this->mEjChainDeg = degree;
528 : 0 : }
529 : :
530 : 0 : void Pal::setTenure( int tenure )
531 : : {
532 : 0 : this->mTenure = tenure;
533 : 0 : }
534 : :
535 : 0 : void Pal::setCandListSize( double fact )
536 : : {
537 : 0 : this->mCandListSize = fact;
538 : 0 : }
539 : :
540 : 0 : void Pal::setShowPartialLabels( bool show )
541 : : {
542 : 0 : this->mShowPartialLabels = show;
543 : 0 : }
544 : :
545 : 0 : QgsLabelingEngineSettings::PlacementEngineVersion Pal::placementVersion() const
546 : : {
547 : 0 : return mPlacementVersion;
548 : : }
549 : :
550 : 0 : void Pal::setPlacementVersion( QgsLabelingEngineSettings::PlacementEngineVersion placementVersion )
551 : : {
552 : 0 : mPlacementVersion = placementVersion;
553 : 0 : }
554 : :
555 : 0 : bool Pal::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
556 : : {
557 : : // we cache the value -- this can be costly to calculate, and we check this multiple times
558 : : // per candidate during the labeling problem solving
559 : :
560 : : // conflicts are commutative - so we always store them in the cache using the smaller id as the first element of the key pair
561 : 0 : auto key = qMakePair( std::min( lp1->globalId(), lp2->globalId() ), std::max( lp1->globalId(), lp2->globalId() ) );
562 : 0 : auto it = mCandidateConflicts.constFind( key );
563 : 0 : if ( it != mCandidateConflicts.constEnd() )
564 : 0 : return *it;
565 : :
566 : 0 : const bool res = lp1->isInConflict( lp2 );
567 : 0 : mCandidateConflicts.insert( key, res );
568 : 0 : return res;
569 : 0 : }
570 : :
571 : 0 : int Pal::getMinIt()
572 : : {
573 : 0 : return mTabuMaxIt;
574 : : }
575 : :
576 : 0 : int Pal::getMaxIt()
577 : : {
578 : 0 : return mTabuMinIt;
579 : : }
580 : :
581 : 0 : bool Pal::showPartialLabels() const
582 : : {
583 : 0 : return mShowPartialLabels;
584 : : }
|
