QGIS API Documentation  3.27.0-Master (bef583a8ef)
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 
45 using namespace pal;
46 
47 inline 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 
64 Problem::~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();
126  lp2->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 
146 void 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  }
190  catch ( pal::InternalException::Full & )
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  {
266  lp->incrementNumOverlaps();
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 
286 bool Problem::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
287 {
288  return pal->candidatesAreConflicting( lp1, lp2 );
289 }
290 
291 inline 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 
573 void Problem::chainSearch( QgsRenderContext & )
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 
589  init_sol_falp();
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 
659 QList<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
Problem(const QgsRectangle &extent)
Constructor for Problem.
Definition: problem.cpp:57
void init_sol_falp()
Definition: problem.cpp:169
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