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