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