QGIS API Documentation 3.29.0-Master (da8bb1db43)
problem.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 "pal.h"
31#include "palstat.h"
32#include "layer.h"
33#include "feature.h"
34#include "geomfunction.h"
35#include "labelposition.h"
36#include "problem.h"
37#include "util.h"
38#include "priorityqueue.h"
39#include "internalexception.h"
40#include <cfloat>
41#include <limits> //for std::numeric_limits<int>::max()
42
43#include "qgslabelingengine.h"
44
45using namespace pal;
46
47inline void delete_chain( Chain *chain )
48{
49 if ( chain )
50 {
51 delete[] chain->feat;
52 delete[] chain->label;
53 delete chain;
54 }
55}
56
57Problem::Problem( const QgsRectangle &extent )
58 : mAllCandidatesIndex( extent )
59 , mActiveCandidatesIndex( extent )
60{
61
62}
63
64Problem::~Problem() = default;
65
67{
68 int i;
69 int j;
70 int k;
71
72 int counter = 0;
73
74 int lpid;
75
76 bool *ok = new bool[mTotalCandidates];
77 bool run = true;
78
79 for ( i = 0; i < mTotalCandidates; i++ )
80 ok[i] = false;
81
82
83 double amin[2];
84 double amax[2];
85 LabelPosition *lp2 = nullptr;
86
87 while ( run )
88 {
89 if ( pal->isCanceled() )
90 break;
91
92 run = false;
93 for ( i = 0; i < static_cast< int >( mFeatureCount ); i++ )
94 {
95 if ( pal->isCanceled() )
96 break;
97
98 // ok[i] = true;
99 for ( j = 0; j < mFeatNbLp[i]; j++ ) // for each candidate
100 {
101 if ( !ok[mFeatStartId[i] + j] )
102 {
103 if ( mLabelPositions.at( mFeatStartId[i] + j )->getNumOverlaps() == 0 ) // if candidate has no overlap
104 {
105 run = true;
106 ok[mFeatStartId[i] + j] = true;
107 // 1) remove worse candidates from candidates
108 // 2) update nb_overlaps
109 counter += mFeatNbLp[i] - j - 1;
110
111 for ( k = j + 1; k < mFeatNbLp[i]; k++ )
112 {
113
114 lpid = mFeatStartId[i] + k;
115 ok[lpid] = true;
116 lp2 = mLabelPositions[lpid ].get();
117
118 lp2->getBoundingBox( amin, amax );
119
120 mNbOverlap -= lp2->getNumOverlaps();
121 mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2, this]( const LabelPosition * lp ) -> bool
122 {
123 if ( candidatesAreConflicting( lp2, lp ) )
124 {
125 const_cast< LabelPosition * >( lp )->decrementNumOverlaps();
127 }
128
129 return true;
130 } );
131 lp2->removeFromIndex( mAllCandidatesIndex );
132 }
133
134 mFeatNbLp[i] = j + 1;
135 break;
136 }
137 }
138 }
139 }
140 }
141
142 this->mTotalCandidates -= counter;
143 delete[] ok;
144}
145
146void Problem::ignoreLabel( const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelPosition > &candidatesIndex )
147{
148 if ( list.isIn( lp->getId() ) )
149 {
150 list.remove( lp->getId() );
151
152 double amin[2];
153 double amax[2];
154 lp->getBoundingBox( amin, amax );
155 candidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &list, this]( const LabelPosition * lp2 )->bool
156 {
157 if ( lp2->getId() != lp->getId() && list.isIn( lp2->getId() ) && candidatesAreConflicting( lp2, lp ) )
158 {
159 list.decreaseKey( lp2->getId() );
160 }
161 return true;
162 } );
163 }
164}
165
166/* Better initial solution
167 * Step one FALP (Yamamoto, Camara, Lorena 2005)
168 */
170{
171 int label;
172
173 mSol.init( mFeatureCount );
174
175 PriorityQueue list( mTotalCandidates, mAllNblp, true );
176
177 double amin[2];
178 double amax[2];
179
180 LabelPosition *lp = nullptr;
181
182 for ( int i = 0; i < static_cast< int >( mFeatureCount ); i++ )
183 for ( int j = 0; j < mFeatNbLp[i]; j++ )
184 {
185 label = mFeatStartId[i] + j;
186 try
187 {
188 list.insert( label, mLabelPositions.at( label )->getNumOverlaps() );
189 }
191 {
192 continue;
193 }
194 }
195
196 while ( list.getSize() > 0 ) // O (log size)
197 {
198 if ( pal->isCanceled() )
199 {
200 return;
201 }
202
203 label = list.getBest(); // O (log size)
204
205 lp = mLabelPositions[ label ].get();
206
207 if ( lp->getId() != label )
208 {
209 //error
210 }
211
212 const int probFeatId = lp->getProblemFeatureId();
213 mSol.activeLabelIds[probFeatId] = label;
214
215 for ( int i = mFeatStartId[probFeatId]; i < mFeatStartId[probFeatId] + mFeatNbLp[probFeatId]; i++ )
216 {
217 ignoreLabel( mLabelPositions[ i ].get(), list, mAllCandidatesIndex );
218 }
219
220
221 lp->getBoundingBox( amin, amax );
222
223 std::vector< const LabelPosition * > conflictingPositions;
224 mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions, this]( const LabelPosition * lp2 ) ->bool
225 {
226 if ( candidatesAreConflicting( lp, lp2 ) )
227 {
228 conflictingPositions.emplace_back( lp2 );
229 }
230 return true;
231 } );
232
233 for ( const LabelPosition *conflict : conflictingPositions )
234 {
235 ignoreLabel( conflict, list, mAllCandidatesIndex );
236 }
237
238 mActiveCandidatesIndex.insert( lp, QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
239 }
240
241 if ( mDisplayAll )
242 {
243 int nbOverlap;
244 int start_p;
245 LabelPosition *retainedLabel = nullptr;
246 int p;
247
248 for ( std::size_t i = 0; i < mFeatureCount; i++ ) // forearch hidden feature
249 {
250 if ( mSol.activeLabelIds[i] == -1 )
251 {
252 nbOverlap = std::numeric_limits<int>::max();
253 start_p = mFeatStartId[i];
254 for ( p = 0; p < mFeatNbLp[i]; p++ )
255 {
256 lp = mLabelPositions[ start_p + p ].get();
257 lp->resetNumOverlaps();
258
259 lp->getBoundingBox( amin, amax );
260
261
262 mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
263 {
264 if ( candidatesAreConflicting( lp, lp2 ) )
265 {
267 }
268 return true;
269 } );
270
271 if ( lp->getNumOverlaps() < nbOverlap )
272 {
273 retainedLabel = lp;
274 nbOverlap = lp->getNumOverlaps();
275 }
276 }
277 mSol.activeLabelIds[i] = retainedLabel->getId();
278
279 retainedLabel->insertIntoIndex( mActiveCandidatesIndex );
280
281 }
282 }
283 }
284}
285
286bool Problem::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
287{
288 return pal->candidatesAreConflicting( lp1, lp2 );
289}
290
291inline Chain *Problem::chain( int seed )
292{
293 int lid;
294
295 double delta;
296 double delta_min;
297 double delta_best = std::numeric_limits<double>::max();
298 double delta_tmp;
299
300 int next_seed;
301 int retainedLabel;
302 Chain *retainedChain = nullptr;
303
304 const int max_degree = pal->mEjChainDeg;
305
306 int seedNbLp;
307
308 QLinkedList<ElemTrans *> currentChain;
309 QLinkedList<int> conflicts;
310
311 std::vector< int > tmpsol( mSol.activeLabelIds );
312
313 LabelPosition *lp = nullptr;
314
315 double amin[2];
316 double amax[2];
317
318 delta = 0;
319 while ( seed != -1 )
320 {
321 seedNbLp = mFeatNbLp[seed];
322 delta_min = std::numeric_limits<double>::max();
323
324 next_seed = -1;
325 retainedLabel = -2;
326
327 // sol[seed] is ejected
328 if ( tmpsol[seed] == -1 )
329 delta -= mInactiveCost[seed];
330 else
331 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
332
333 for ( int i = -1; i < seedNbLp; i++ )
334 {
335 try
336 {
337 // Skip active label !
338 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFeatStartId[seed] != tmpsol[seed] )
339 {
340 if ( i != -1 ) // new_label
341 {
342 lid = mFeatStartId[seed] + i;
343 delta_tmp = delta;
344
345 lp = mLabelPositions[ lid ].get();
346
347 // evaluate conflicts graph in solution after moving seed's label
348
349 lp->getBoundingBox( amin, amax );
350 mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, &currentChain, this]( const LabelPosition * lp2 ) -> bool
351 {
352 if ( candidatesAreConflicting( lp2, lp ) )
353 {
354 const int feat = lp2->getProblemFeatureId();
355
356 // is there any cycles ?
357 QLinkedList< ElemTrans * >::iterator cur;
358 for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
359 {
360 if ( ( *cur )->feat == feat )
361 {
362 throw - 1;
363 }
364 }
365
366 if ( !conflicts.contains( feat ) )
367 {
368 conflicts.append( feat );
369 delta_tmp += lp2->cost() + mInactiveCost[feat];
370 }
371 }
372 return true;
373 } );
374
375 // no conflict -> end of chain
376 if ( conflicts.isEmpty() )
377 {
378 if ( !retainedChain || delta + lp->cost() < delta_best )
379 {
380 if ( retainedChain )
381 {
382 delete[] retainedChain->label;
383 delete[] retainedChain->feat;
384 }
385 else
386 {
387 retainedChain = new Chain();
388 }
389
390 delta_best = delta + lp->cost();
391
392 retainedChain->degree = currentChain.size() + 1;
393 retainedChain->feat = new int[retainedChain->degree];
394 retainedChain->label = new int[retainedChain->degree];
395 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
396 ElemTrans *move = nullptr;
397 int j = 0;
398 while ( current != currentChain.end() )
399 {
400 move = *current;
401 retainedChain->feat[j] = move->feat;
402 retainedChain->label[j] = move->new_label;
403 ++current;
404 ++j;
405 }
406 retainedChain->feat[j] = seed;
407 retainedChain->label[j] = lid;
408 retainedChain->delta = delta + lp->cost();
409 }
410 }
411
412 // another feature can be ejected
413 else if ( conflicts.size() == 1 )
414 {
415 if ( delta_tmp < delta_min )
416 {
417 delta_min = delta_tmp;
418 retainedLabel = lid;
419 next_seed = conflicts.takeFirst();
420 }
421 else
422 {
423 conflicts.takeFirst();
424 }
425 }
426 else
427 {
428
429 // A lot of conflict : make them inactive and store chain
430 Chain *newChain = new Chain();
431 newChain->degree = currentChain.size() + 1 + conflicts.size();
432 newChain->feat = new int[newChain->degree];
433 newChain->label = new int[newChain->degree];
434 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
435 ElemTrans *move = nullptr;
436 int j = 0;
437
438 while ( current != currentChain.end() )
439 {
440 move = *current;
441 newChain->feat[j] = move->feat;
442 newChain->label[j] = move->new_label;
443 ++current;
444 ++j;
445 }
446
447 // add the current candidates into the chain
448 newChain->feat[j] = seed;
449 newChain->label[j] = lid;
450 newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
451 j++;
452
453 // hide all conflictual candidates
454 while ( !conflicts.isEmpty() )
455 {
456 const int ftid = conflicts.takeFirst();
457 newChain->feat[j] = ftid;
458 newChain->label[j] = -1;
459 newChain->delta += mInactiveCost[ftid];
460 j++;
461 }
462
463 if ( newChain->delta < delta_best )
464 {
465 if ( retainedChain )
466 delete_chain( retainedChain );
467
468 delta_best = newChain->delta;
469 retainedChain = newChain;
470 }
471 else
472 {
473 delete_chain( newChain );
474 }
475 }
476
477 }
478 else // Current label == -1 end of chain ...
479 {
480 if ( !retainedChain || delta + mInactiveCost[seed] < delta_best )
481 {
482 if ( retainedChain )
483 {
484 delete[] retainedChain->label;
485 delete[] retainedChain->feat;
486 }
487 else
488 retainedChain = new Chain();
489
490 delta_best = delta + mInactiveCost[seed];
491
492 retainedChain->degree = currentChain.size() + 1;
493 retainedChain->feat = new int[retainedChain->degree];
494 retainedChain->label = new int[retainedChain->degree];
495 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
496 ElemTrans *move = nullptr;
497 int j = 0;
498 while ( current != currentChain.end() )
499 {
500 move = *current;
501 retainedChain->feat[j] = move->feat;
502 retainedChain->label[j] = move->new_label;
503 ++current;
504 ++j;
505 }
506 retainedChain->feat[j] = seed;
507 retainedChain->label[j] = -1;
508 retainedChain->delta = delta + mInactiveCost[seed];
509 }
510 }
511 }
512 }
513 catch ( int )
514 {
515 conflicts.clear();
516 }
517 } // end for each labelposition
518
519 if ( next_seed == -1 )
520 {
521 seed = -1;
522 }
523 else if ( currentChain.size() > max_degree )
524 {
525 // Max degree reached
526 seed = -1;
527 }
528 else
529 {
530 ElemTrans *et = new ElemTrans();
531 et->feat = seed;
532 et->old_label = tmpsol[seed];
533 et->new_label = retainedLabel;
534 currentChain.append( et );
535
536 if ( et->old_label != -1 )
537 {
538 mLabelPositions.at( et->old_label )->removeFromIndex( mActiveCandidatesIndex );
539 }
540
541 if ( et->new_label != -1 )
542 {
543 mLabelPositions.at( et->new_label )->insertIntoIndex( mActiveCandidatesIndex );
544 }
545
546
547 tmpsol[seed] = retainedLabel;
548 // cppcheck-suppress invalidFunctionArg
549 delta += mLabelPositions.at( retainedLabel )->cost();
550 seed = next_seed;
551 }
552 }
553
554 while ( !currentChain.isEmpty() )
555 {
556 std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
557
558 if ( et->new_label != -1 )
559 {
560 mLabelPositions.at( et->new_label )->removeFromIndex( mActiveCandidatesIndex );
561 }
562
563 if ( et->old_label != -1 )
564 {
565 mLabelPositions.at( et->old_label )->insertIntoIndex( mActiveCandidatesIndex );
566 }
567 }
568
569 return retainedChain;
570}
571
572
574{
575 if ( mFeatureCount == 0 )
576 return;
577
578 int i;
579 int seed;
580 bool *ok = new bool[mFeatureCount];
581 int fid;
582 int lid;
583 int popit = 0;
584
585 Chain *retainedChain = nullptr;
586
587 std::fill( ok, ok + mFeatureCount, false );
588
590
591 int iter = 0;
592
593 double amin[2];
594 double amax[2];
595
596 while ( true )
597 {
598 for ( seed = ( iter + 1 ) % mFeatureCount;
599 ok[seed] && seed != iter;
600 seed = ( seed + 1 ) % mFeatureCount )
601 ;
602
603 // All seeds are OK
604 if ( seed == iter )
605 {
606 break;
607 }
608
609 iter = ( iter + 1 ) % mFeatureCount;
610 retainedChain = chain( seed );
611
612 if ( retainedChain && retainedChain->delta < - EPSILON )
613 {
614 // apply modification
615 for ( i = 0; i < retainedChain->degree; i++ )
616 {
617 fid = retainedChain->feat[i];
618 lid = retainedChain->label[i];
619
620 if ( mSol.activeLabelIds[fid] >= 0 )
621 {
622 LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
623 old->removeFromIndex( mActiveCandidatesIndex );
624 old->getBoundingBox( amin, amax );
625 mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old, this]( const LabelPosition * lp ) ->bool
626 {
627 if ( candidatesAreConflicting( old, lp ) )
628 {
629 ok[lp->getProblemFeatureId()] = false;
630 }
631
632 return true;
633 } );
634 }
635
636 mSol.activeLabelIds[fid] = lid;
637
638 if ( mSol.activeLabelIds[fid] >= 0 )
639 {
640 mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex );
641 }
642
643 ok[fid] = false;
644 }
645 }
646 else
647 {
648 // no chain or the one is not good enough
649 ok[seed] = true;
650 }
651
652 delete_chain( retainedChain );
653 popit++;
654 }
655
656 delete[] ok;
657}
658
659QList<LabelPosition *> Problem::getSolution( bool returnInactive, QList<LabelPosition *> *unlabeled )
660{
661 QList<LabelPosition *> finalLabelPlacements;
662 finalLabelPlacements.reserve( mFeatureCount );
663
664 // loop through all features to be labeled
665 for ( std::size_t i = 0; i < mFeatureCount; i++ )
666 {
667 const int labelId = mSol.activeLabelIds[i];
668 const bool foundNonOverlappingPlacement = labelId != -1;
669 const int startIndexForLabelPlacements = mFeatStartId[i];
670 const bool foundCandidatesForFeature = startIndexForLabelPlacements < static_cast< int >( mLabelPositions.size() );
671
672 if ( foundNonOverlappingPlacement )
673 {
674 finalLabelPlacements.push_back( mLabelPositions[ labelId ].get() ); // active labels
675 }
676 else if ( foundCandidatesForFeature &&
677 ( returnInactive // allowing any overlapping labels regardless of where they are from
678 || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->feature()->overlapHandling() == Qgis::LabelOverlapHandling::AllowOverlapIfRequired // allowing overlapping labels for the layer
679 || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->alwaysShow() ) ) // allowing overlapping labels for the feature
680 {
681 finalLabelPlacements.push_back( mLabelPositions[ startIndexForLabelPlacements ].get() ); // unplaced label
682 }
683 else if ( unlabeled )
684 {
685 // need to be careful here -- if the next feature's start id is the same as this one, then this feature had no candidates!
686 if ( foundCandidatesForFeature && ( i == mFeatureCount - 1 || startIndexForLabelPlacements != mFeatStartId[i + 1] ) )
687 unlabeled->push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
688 }
689 }
690
691 // unlabeled features also include those with no candidates
692 if ( unlabeled )
693 {
694 unlabeled->reserve( mPositionsWithNoCandidates.size() );
695 for ( const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
696 unlabeled->append( position.get() );
697 }
698
699 return finalLabelPlacements;
700}
A rtree spatial index for use in the pal labeling engine.
Definition: palrtree.h:36
bool intersects(const QgsRectangle &bounds, const std::function< bool(T *data)> &callback) const
Performs an intersection check against the index, for data intersecting the specified bounds.
Definition: palrtree.h:96
@ AllowOverlapIfRequired
Avoids overlapping labels when possible, but permit overlaps if labels for features cannot otherwise ...
A rectangle specified with double values.
Definition: qgsrectangle.h:42
Contains information about the context of a rendering operation.
Thrown when something is added in a Full set.
LabelPosition is a candidate feature label position.
Definition: labelposition.h:56
void incrementNumOverlaps()
Increases the number of overlaps recorded against this position by 1.
void removeFromIndex(PalRtree< LabelPosition > &index)
Removes the label position from the specified index.
void decrementNumOverlaps()
Decreases the number of overlaps recorded against this position by 1.
int getId() const
Returns the id.
double cost() const
Returns the candidate label position's geographical cost.
int getNumOverlaps() const
int getProblemFeatureId() const
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
void insertIntoIndex(PalRtree< LabelPosition > &index)
Inserts the label position into the specified index.
Custom priority queue for use in pal labeling engine.
Definition: priorityqueue.h:53
void decreaseKey(int key)
void insert(int key, double p)
bool isIn(int key) const
void remove(int key)
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:659
void init_sol_falp()
Definition: problem.cpp:169
void chainSearch(QgsRenderContext &context)
Test with very-large scale neighborhood.
Definition: problem.cpp:573
void reduce()
Definition: problem.cpp:66
void delete_chain(Chain *chain)
Definition: problem.cpp:47
double delta
Definition: problem.h:61
int * label
Definition: problem.h:63
int * feat
Definition: problem.h:62
int degree
Definition: problem.h:60
int feat
Definition: util.h:68
int new_label
Definition: util.h:70
int old_label
Definition: util.h:69
#define EPSILON
Definition: util.h:78