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