QGIS API Documentation  3.9.0-Master (224899f119)
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 "rtree.hpp"
34 #include "feature.h"
35 #include "geomfunction.h"
36 #include "labelposition.h"
37 #include "problem.h"
38 #include "util.h"
39 #include "priorityqueue.h"
40 #include "internalexception.h"
41 #include <cfloat>
42 #include <limits> //for std::numeric_limits<int>::max()
43 
44 #include "qgslabelingengine.h"
45 
46 using namespace pal;
47 
48 inline void delete_chain( Chain *chain )
49 {
50  if ( chain )
51  {
52  delete[] chain->feat;
53  delete[] chain->label;
54  delete chain;
55  }
56 }
57 
59 {
60  bbox[0] = 0;
61  bbox[1] = 0;
62  bbox[2] = 0;
63  bbox[3] = 0;
64  candidates = new RTree<LabelPosition *, double, 2, double>();
65  candidates_sol = new RTree<LabelPosition *, double, 2, double>();
66 }
67 
69 {
70  if ( sol )
71  {
72  delete[] sol->s;
73  delete sol;
74  }
75 
76  delete[] featStartId;
77  delete[] featNbLp;
78 
79  qDeleteAll( mLabelPositions );
80  mLabelPositions.clear();
81 
82  qDeleteAll( mPositionsWithNoCandidates );
83 
84  delete[] inactiveCost;
85 
86  delete candidates;
87  delete candidates_sol;
88 }
89 
90 
92 {
93 
94  int i;
95  int j;
96  int k;
97 
98  int counter = 0;
99 
100  int lpid;
101 
102  bool *ok = new bool[nblp];
103  bool run = true;
104 
105  for ( i = 0; i < nblp; i++ )
106  ok[i] = false;
107 
108 
109  double amin[2];
110  double amax[2];
111  LabelPosition *lp2 = nullptr;
112 
113  while ( run )
114  {
115  run = false;
116  for ( i = 0; i < nbft; i++ )
117  {
118  // ok[i] = true;
119  for ( j = 0; j < featNbLp[i]; j++ ) // foreach candidate
120  {
121  if ( !ok[featStartId[i] + j] )
122  {
123  if ( mLabelPositions.at( featStartId[i] + j )->getNumOverlaps() == 0 ) // if candidate has no overlap
124  {
125  run = true;
126  ok[featStartId[i] + j] = true;
127  // 1) remove worse candidates from candidates
128  // 2) update nb_overlaps
129  counter += featNbLp[i] - j - 1;
130 
131  for ( k = j + 1; k < featNbLp[i]; k++ )
132  {
133 
134  lpid = featStartId[i] + k;
135  ok[lpid] = true;
136  lp2 = mLabelPositions.at( lpid );
137 
138  lp2->getBoundingBox( amin, amax );
139 
140  nbOverlap -= lp2->getNumOverlaps();
141  candidates->Search( amin, amax, LabelPosition::removeOverlapCallback, reinterpret_cast< void * >( lp2 ) );
142  lp2->removeFromIndex( candidates );
143  }
144 
145  featNbLp[i] = j + 1;
146  break;
147  }
148  }
149  }
150  }
151  }
152 
153  this->nblp -= counter;
154  delete[] ok;
155 }
156 
158 {
159  int i;
160 
161  if ( sol )
162  {
163  delete[] sol->s;
164  delete sol;
165  }
166 
167  sol = new Sol();
168  sol->s = new int[nbft];
169 
170  for ( i = 0; i < nbft; i++ )
171  sol->s[i] = -1;
172 
173  sol->cost = nbft;
174 }
175 
176 typedef struct
177 {
178  PriorityQueue *list = nullptr;
179  LabelPosition *lp = nullptr;
180  RTree <LabelPosition *, double, 2, double> *candidates;
181 } FalpContext;
182 
183 bool falpCallback2( LabelPosition *lp, void *ctx )
184 {
185  FalpContext *context = reinterpret_cast< FalpContext * >( ctx );
186  LabelPosition *lp2 = context->lp;
187  PriorityQueue *list = context->list;
188 
189  if ( lp->getId() != lp2->getId() && list->isIn( lp->getId() ) && lp->isInConflict( lp2 ) )
190  {
191  list->decreaseKey( lp->getId() );
192  }
193  return true;
194 }
195 
196 
197 void ignoreLabel( LabelPosition *lp, PriorityQueue *list, RTree <LabelPosition *, double, 2, double> *candidates )
198 {
199 
200 
201  FalpContext *context = new FalpContext();
202  context->candidates = nullptr;
203  context->list = list;
204  double amin[2];
205  double amax[2];
206 
207  if ( list->isIn( lp->getId() ) )
208  {
209  list->remove( lp->getId() );
210 
211  lp->getBoundingBox( amin, amax );
212 
213  context->lp = lp;
214  candidates->Search( amin, amax, falpCallback2, context );
215  }
216 
217  delete context;
218 }
219 
220 
221 bool falpCallback1( LabelPosition *lp, void *ctx )
222 {
223  FalpContext *context = reinterpret_cast< FalpContext * >( ctx );
224  LabelPosition *lp2 = context->lp;
225  PriorityQueue *list = context->list;
226  RTree <LabelPosition *, double, 2, double> *candidates = context->candidates;
227 
228  if ( lp2->isInConflict( lp ) )
229  {
230  ignoreLabel( lp, list, candidates );
231  }
232  return true;
233 }
234 
235 
236 
237 /* Better initial solution
238  * Step one FALP (Yamamoto, Camara, Lorena 2005)
239  */
241 {
242  int i, j;
243  int label;
244  PriorityQueue *list = nullptr;
245 
246  init_sol_empty();
247 
248  list = new PriorityQueue( nblp, all_nblp, true );
249 
250  double amin[2];
251  double amax[2];
252 
253  FalpContext *context = new FalpContext();
254  context->candidates = candidates;
255  context->list = list;
256 
257  LabelPosition *lp = nullptr;
258 
259  for ( i = 0; i < nbft; i++ )
260  for ( j = 0; j < featNbLp[i]; j++ )
261  {
262  label = featStartId[i] + j;
263  try
264  {
265  list->insert( label, mLabelPositions.at( label )->getNumOverlaps() );
266  }
267  catch ( pal::InternalException::Full & )
268  {
269  continue;
270  }
271  }
272 
273  while ( list->getSize() > 0 ) // O (log size)
274  {
275  if ( pal->isCanceled() )
276  {
277  delete context;
278  delete list;
279  return;
280  }
281 
282  label = list->getBest(); // O (log size)
283 
284 
285  lp = mLabelPositions.at( label );
286 
287  if ( lp->getId() != label )
288  {
289  //error
290  }
291 
292  int probFeatId = lp->getProblemFeatureId();
293  sol->s[probFeatId] = label;
294 
295  for ( i = featStartId[probFeatId]; i < featStartId[probFeatId] + featNbLp[probFeatId]; i++ )
296  {
297  ignoreLabel( mLabelPositions.at( i ), list, candidates );
298  }
299 
300 
301  lp->getBoundingBox( amin, amax );
302 
303  context->lp = lp;
304  candidates->Search( amin, amax, falpCallback1, reinterpret_cast< void * >( context ) );
305  candidates_sol->Insert( amin, amax, lp );
306  }
307 
308  delete context;
309 
310 
311 
312 
313  if ( displayAll )
314  {
315  int nbOverlap;
316  int start_p;
317  LabelPosition *retainedLabel = nullptr;
318  int p;
319 
320  for ( i = 0; i < nbft; i++ ) // forearch hidden feature
321  {
322  if ( sol->s[i] == -1 )
323  {
324  nbOverlap = std::numeric_limits<int>::max();
325  start_p = featStartId[i];
326  for ( p = 0; p < featNbLp[i]; p++ )
327  {
328  lp = mLabelPositions.at( start_p + p );
329  lp->resetNumOverlaps();
330 
331  lp->getBoundingBox( amin, amax );
332 
333 
334  candidates_sol->Search( amin, amax, LabelPosition::countOverlapCallback, lp );
335 
336  if ( lp->getNumOverlaps() < nbOverlap )
337  {
338  retainedLabel = lp;
339  nbOverlap = lp->getNumOverlaps();
340  }
341  }
342  sol->s[i] = retainedLabel->getId();
343 
344  retainedLabel->insertIntoIndex( candidates_sol );
345 
346  }
347  }
348  }
349 
350  delete list;
351 }
352 
353 
354 typedef struct
355 {
356  LabelPosition *lp = nullptr;
357  int *tmpsol = nullptr;
358  int *featWrap = nullptr;
359  int *feat = nullptr;
361  QLinkedList<ElemTrans *> *currentChain;
362  QLinkedList<int> *conflicts;
363  double *delta_tmp = nullptr;
364  double *inactiveCost = nullptr;
365 
366 } ChainContext;
367 
368 
369 bool chainCallback( LabelPosition *lp, void *context )
370 {
371  ChainContext *ctx = reinterpret_cast< ChainContext * >( context );
372 
373  if ( lp->isInConflict( ctx->lp ) )
374  {
375  int feat, rfeat;
376  bool sub = nullptr != ctx->featWrap;
377 
378  feat = lp->getProblemFeatureId();
379  if ( sub )
380  {
381  rfeat = feat;
382  feat = ctx->featWrap[feat];
383  }
384  else
385  rfeat = feat;
386 
387  if ( feat >= 0 && ctx->tmpsol[feat] == lp->getId() )
388  {
389  if ( sub && feat < ctx->borderSize )
390  {
391  throw - 2;
392  }
393  }
394 
395  // is there any cycles ?
396  QLinkedList< ElemTrans * >::iterator cur;
397  for ( cur = ctx->currentChain->begin(); cur != ctx->currentChain->end(); ++cur )
398  {
399  if ( ( *cur )->feat == feat )
400  {
401  throw - 1;
402  }
403  }
404 
405  if ( !ctx->conflicts->contains( feat ) )
406  {
407  ctx->conflicts->append( feat );
408  *ctx->delta_tmp += lp->cost() + ctx->inactiveCost[rfeat];
409  }
410  }
411  return true;
412 }
413 
414 inline Chain *Problem::chain( int seed )
415 {
416 
417  int i;
418  int j;
419 
420  int lid;
421 
422  double delta;
423  double delta_min;
424  double delta_best = std::numeric_limits<double>::max();
425  double delta_tmp;
426 
427  int next_seed;
428  int retainedLabel;
429  Chain *retainedChain = nullptr;
430 
431  int max_degree = pal->ejChainDeg;
432 
433  int seedNbLp;
434 
435  QLinkedList<ElemTrans *> *currentChain = new QLinkedList<ElemTrans *>;
436  QLinkedList<int> *conflicts = new QLinkedList<int>;
437 
438  int *tmpsol = new int[nbft];
439  memcpy( tmpsol, sol->s, sizeof( int ) *nbft );
440 
441  LabelPosition *lp = nullptr;
442  double amin[2];
443  double amax[2];
444 
445  ChainContext context;
446  context.featWrap = nullptr;
447  context.borderSize = 0;
448  context.tmpsol = tmpsol;
449  context.inactiveCost = inactiveCost;
450  context.feat = nullptr;
451  context.currentChain = currentChain;
452  context.conflicts = conflicts;
453  context.delta_tmp = &delta_tmp;
454 
455  delta = 0;
456  while ( seed != -1 )
457  {
458  seedNbLp = featNbLp[seed];
459  delta_min = std::numeric_limits<double>::max();
460 
461  next_seed = -1;
462  retainedLabel = -2;
463 
464  // sol[seed] is ejected
465  if ( tmpsol[seed] == -1 )
466  delta -= inactiveCost[seed];
467  else
468  delta -= mLabelPositions.at( tmpsol[seed] )->cost();
469 
470  for ( i = -1; i < seedNbLp; i++ )
471  {
472  try
473  {
474  // Skip active label !
475  if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[seed] != tmpsol[seed] )
476  {
477  if ( i != -1 ) // new_label
478  {
479  lid = featStartId[seed] + i;
480  delta_tmp = delta;
481 
482  lp = mLabelPositions.at( lid );
483 
484  // evaluate conflicts graph in solution after moving seed's label
485  lp->getBoundingBox( amin, amax );
486 
487  context.lp = lp;
488 
489  candidates_sol->Search( amin, amax, chainCallback, reinterpret_cast< void * >( &context ) );
490 
491  // no conflict -> end of chain
492  if ( conflicts->isEmpty() )
493  {
494  if ( !retainedChain || delta + lp->cost() < delta_best )
495  {
496  if ( retainedChain )
497  {
498  delete[] retainedChain->label;
499  delete[] retainedChain->feat;
500  }
501  else
502  {
503  retainedChain = new Chain();
504  }
505 
506  delta_best = delta + lp->cost();
507 
508  retainedChain->degree = currentChain->size() + 1;
509  retainedChain->feat = new int[retainedChain->degree];
510  retainedChain->label = new int[retainedChain->degree];
511  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
512  ElemTrans *move = nullptr;
513  j = 0;
514  while ( current != currentChain->end() )
515  {
516  move = *current;
517  retainedChain->feat[j] = move->feat;
518  retainedChain->label[j] = move->new_label;
519  ++current;
520  ++j;
521  }
522  retainedChain->feat[j] = seed;
523  retainedChain->label[j] = lid;
524  retainedChain->delta = delta + lp->cost();
525  }
526  }
527 
528  // another feature can be ejected
529  else if ( conflicts->size() == 1 )
530  {
531  if ( delta_tmp < delta_min )
532  {
533  delta_min = delta_tmp;
534  retainedLabel = lid;
535  next_seed = conflicts->takeFirst();
536  }
537  else
538  {
539  conflicts->takeFirst();
540  }
541  }
542  else
543  {
544 
545  // A lot of conflict : make them inactive and store chain
546  Chain *newChain = new Chain();
547  newChain->degree = currentChain->size() + 1 + conflicts->size();
548  newChain->feat = new int[newChain->degree];
549  newChain->label = new int[newChain->degree];
550  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
551  ElemTrans *move = nullptr;
552  j = 0;
553 
554  while ( current != currentChain->end() )
555  {
556  move = *current;
557  newChain->feat[j] = move->feat;
558  newChain->label[j] = move->new_label;
559  ++current;
560  ++j;
561  }
562 
563  // add the current candidates into the chain
564  newChain->feat[j] = seed;
565  newChain->label[j] = lid;
566  newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
567  j++;
568 
569  // hide all conflictual candidates
570  while ( !conflicts->isEmpty() )
571  {
572  int ftid = conflicts->takeFirst();
573  newChain->feat[j] = ftid;
574  newChain->label[j] = -1;
575  newChain->delta += inactiveCost[ftid];
576  j++;
577  }
578 
579  if ( newChain->delta < delta_best )
580  {
581  if ( retainedChain )
582  delete_chain( retainedChain );
583 
584  delta_best = newChain->delta;
585  retainedChain = newChain;
586  }
587  else
588  {
589  delete_chain( newChain );
590  }
591  }
592 
593  }
594  else // Current label == -1 end of chain ...
595  {
596  if ( !retainedChain || delta + inactiveCost[seed] < delta_best )
597  {
598  if ( retainedChain )
599  {
600  delete[] retainedChain->label;
601  delete[] retainedChain->feat;
602  }
603  else
604  retainedChain = new Chain();
605 
606  delta_best = delta + inactiveCost[seed];
607 
608  retainedChain->degree = currentChain->size() + 1;
609  retainedChain->feat = new int[retainedChain->degree];
610  retainedChain->label = new int[retainedChain->degree];
611  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
612  ElemTrans *move = nullptr;
613  j = 0;
614  while ( current != currentChain->end() )
615  {
616  move = *current;
617  retainedChain->feat[j] = move->feat;
618  retainedChain->label[j] = move->new_label;
619  ++current;
620  ++j;
621  }
622  retainedChain->feat[j] = seed;
623  retainedChain->label[j] = -1;
624  retainedChain->delta = delta + inactiveCost[seed];
625  }
626  }
627  }
628  }
629  catch ( int i )
630  {
631  Q_UNUSED( i )
632  conflicts->clear();
633  }
634  } // end foreach labelposition
635 
636  if ( next_seed == -1 )
637  {
638  seed = -1;
639  }
640  else if ( currentChain->size() > max_degree )
641  {
642  // Max degree reached
643  seed = -1;
644  }
645  else
646  {
647  ElemTrans *et = new ElemTrans();
648  et->feat = seed;
649  et->old_label = tmpsol[seed];
650  et->new_label = retainedLabel;
651  currentChain->append( et );
652 
653  if ( et->old_label != -1 )
654  {
655  mLabelPositions.at( et->old_label )->removeFromIndex( candidates_sol );
656  }
657 
658  if ( et->new_label != -1 )
659  {
660  mLabelPositions.at( et->new_label )->insertIntoIndex( candidates_sol );
661  }
662 
663 
664  tmpsol[seed] = retainedLabel;
665  delta += mLabelPositions.at( retainedLabel )->cost();
666  seed = next_seed;
667  }
668  }
669 
670 
671  while ( !currentChain->isEmpty() )
672  {
673  ElemTrans *et = currentChain->takeFirst();
674 
675  if ( et->new_label != -1 )
676  {
677  mLabelPositions.at( et->new_label )->removeFromIndex( candidates_sol );
678  }
679 
680  if ( et->old_label != -1 )
681  {
682  mLabelPositions.at( et->old_label )->insertIntoIndex( candidates_sol );
683  }
684 
685  delete et;
686  }
687  delete currentChain;
688 
689  delete[] tmpsol;
690  delete conflicts;
691 
692 
693  return retainedChain;
694 }
695 
696 typedef struct _nokContext
697 {
698  LabelPosition *lp = nullptr;
699  bool *ok = nullptr;
700  int *wrap = nullptr;
701 } NokContext;
702 
703 bool nokCallback( LabelPosition *lp, void *context )
704 {
705  NokContext *ctx = reinterpret_cast< NokContext *>( context );
706  LabelPosition *lp2 = ctx->lp;
707  bool *ok = ctx->ok;
708  int *wrap = ctx->wrap;
709 
710  if ( lp2->isInConflict( lp ) )
711  {
712  if ( wrap )
713  {
714  ok[wrap[lp->getProblemFeatureId()]] = false;
715  }
716  else
717  {
718  ok[lp->getProblemFeatureId()] = false;
719  }
720  }
721 
722  return true;
723 }
724 
726 {
727 
728  if ( nbft == 0 )
729  return;
730 
731  int i;
732  int seed;
733  bool *ok = new bool[nbft];
734  int fid;
735  int lid;
736  int popit = 0;
737  double amin[2];
738  double amax[2];
739 
740  NokContext context;
741  context.ok = ok;
742  context.wrap = nullptr;
743 
744  Chain *retainedChain = nullptr;
745 
746  std::fill( ok, ok + nbft, false );
747 
748  //initialization();
749  init_sol_falp();
750 
751  //check_solution();
752  solution_cost();
753 
754  int iter = 0;
755 
756  while ( true )
757  {
758 
759  //check_solution();
760 
761  for ( seed = ( iter + 1 ) % nbft;
762  ok[seed] && seed != iter;
763  seed = ( seed + 1 ) % nbft )
764  ;
765 
766  // All seeds are OK
767  if ( seed == iter )
768  {
769  break;
770  }
771 
772  iter = ( iter + 1 ) % nbft;
773  retainedChain = chain( seed );
774 
775  if ( retainedChain && retainedChain->delta < - EPSILON )
776  {
777  // apply modification
778  for ( i = 0; i < retainedChain->degree; i++ )
779  {
780  fid = retainedChain->feat[i];
781  lid = retainedChain->label[i];
782 
783  if ( sol->s[fid] >= 0 )
784  {
785  LabelPosition *old = mLabelPositions.at( sol->s[fid] );
786  old->removeFromIndex( candidates_sol );
787 
788  old->getBoundingBox( amin, amax );
789 
790  context.lp = old;
791  candidates->Search( amin, amax, nokCallback, &context );
792  }
793 
794  sol->s[fid] = lid;
795 
796  if ( sol->s[fid] >= 0 )
797  {
798  mLabelPositions.at( lid )->insertIntoIndex( candidates_sol );
799  }
800 
801  ok[fid] = false;
802  }
803  sol->cost += retainedChain->delta;
804  }
805  else
806  {
807  // no chain or the one is not god enough
808  ok[seed] = true;
809  }
810 
811  delete_chain( retainedChain );
812  popit++;
813  }
814 
815  solution_cost();
816  delete[] ok;
817 }
818 
820 {
821  return l1->getWidth() * l1->getHeight() > l2->getWidth() * l2->getHeight();
822 }
823 
824 QList<LabelPosition *> Problem::getSolution( bool returnInactive, QList<LabelPosition *> *unlabeled )
825 {
826  int i;
827  QList<LabelPosition *> solList;
828 
829  for ( i = 0; i < nbft; i++ )
830  {
831  if ( sol->s[i] != -1 )
832  {
833  solList.push_back( mLabelPositions.at( sol->s[i] ) ); // active labels
834  }
835  else if ( returnInactive
836  || mLabelPositions.at( featStartId[i] )->getFeaturePart()->layer()->displayAll()
837  || mLabelPositions.at( featStartId[i] )->getFeaturePart()->alwaysShow() )
838  {
839  solList.push_back( mLabelPositions.at( featStartId[i] ) ); // unplaced label
840  }
841  else if ( unlabeled )
842  {
843  unlabeled->push_back( mLabelPositions.at( featStartId[i] ) );
844  }
845  }
846 
847  // unlabeled features also include those with no candidates
848  if ( unlabeled )
849  unlabeled->append( mPositionsWithNoCandidates );
850 
851  // if features collide, order by size, so smaller ones appear on top
852  if ( returnInactive )
853  {
854  std::sort( solList.begin(), solList.end(), compareLabelArea );
855  }
856 
857  return solList;
858 }
859 
861 {
862  int i, j;
863 
864  PalStat *stats = new PalStat();
865 
866  stats->nbObjects = nbft;
867  stats->nbLabelledObjects = 0;
868 
869  stats->nbLayers = nbLabelledLayers;
870  stats->layersNbObjects = new int[stats->nbLayers];
871  stats->layersNbLabelledObjects = new int[stats->nbLayers];
872 
873  for ( i = 0; i < stats->nbLayers; i++ )
874  {
875  stats->layersName << labelledLayersName[i];
876  stats->layersNbObjects[i] = 0;
877  stats->layersNbLabelledObjects[i] = 0;
878  }
879 
880  QString lyrName;
881  int k;
882  for ( i = 0; i < nbft; i++ )
883  {
884  lyrName = mLabelPositions.at( featStartId[i] )->getFeaturePart()->feature()->provider()->name();
885  k = -1;
886  for ( j = 0; j < stats->nbLayers; j++ )
887  {
888  if ( lyrName == stats->layersName[j] )
889  {
890  k = j;
891  break;
892  }
893  }
894  if ( k != -1 )
895  {
896  stats->layersNbObjects[k]++;
897  if ( sol->s[i] >= 0 )
898  {
899  stats->layersNbLabelledObjects[k]++;
900  stats->nbLabelledObjects++;
901  }
902  }
903  else
904  {
905  // unknown layer
906  }
907  }
908 
909  return stats;
910 }
911 
912 void Problem::solution_cost()
913 {
914  sol->cost = 0.0;
915 
916  int nbOv;
917 
918  int i;
919 
921  context.inactiveCost = inactiveCost;
922  context.nbOv = &nbOv;
923  context.cost = &sol->cost;
924  double amin[2];
925  double amax[2];
926  LabelPosition *lp = nullptr;
927 
928  int nbHidden = 0;
929 
930  for ( i = 0; i < nbft; i++ )
931  {
932  if ( sol->s[i] == -1 )
933  {
934  sol->cost += inactiveCost[i];
935  nbHidden++;
936  }
937  else
938  {
939  nbOv = 0;
940  lp = mLabelPositions.at( sol->s[i] );
941 
942  lp->getBoundingBox( amin, amax );
943 
944  context.lp = lp;
945  candidates_sol->Search( amin, amax, LabelPosition::countFullOverlapCallback, &context );
946 
947  sol->cost += lp->cost();
948  }
949  }
950 }
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
static bool compareLabelArea(pal::LabelPosition *l1, pal::LabelPosition *l2)
Definition: problem.cpp:819
void reduce()
Definition: problem.cpp:91
double * delta_tmp
Definition: problem.cpp:363
bool isIn(int key)
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
double cost
Definition: problem.h:56
Thrown when something is added in a Full set.
int degree
Definition: problem.h:61
bool chainCallback(LabelPosition *lp, void *context)
Definition: problem.cpp:369
struct _nokContext NokContext
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
int getProblemFeatureId() const
struct pal::_elementary_transformation ElemTrans
void remove(int key)
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
QLinkedList< ElemTrans * > * currentChain
Definition: problem.cpp:361
LabelPosition * lp
Definition: problem.cpp:179
bool falpCallback1(LabelPosition *lp, void *ctx)
Definition: problem.cpp:221
int * wrap
Definition: problem.cpp:700
int * tmpsol
Definition: problem.cpp:357
double cost() const
Returns the candidate label position&#39;s geographical cost.
RTree< LabelPosition *, double, 2, double > * candidates
Definition: problem.cpp:180
void chain_search()
Test with very-large scale neighborhood.
Definition: problem.cpp:725
int * featWrap
Definition: problem.cpp:358
int * label
Definition: problem.h:64
double getHeight() const
void seed(uint32_t value)
struct pal::_chain Chain
double * inactiveCost
Definition: problem.cpp:364
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
bool nokCallback(LabelPosition *lp, void *context)
Definition: problem.cpp:703
int borderSize
Definition: problem.cpp:360
int * feat
Definition: problem.cpp:359
void insert(int key, double p)
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
bool * ok
Definition: problem.cpp:699
PalStat * getStats()
Definition: problem.cpp:860
LabelPosition * lp
Definition: problem.cpp:356
int getId() const
Returns the id.
LabelPosition * lp
Definition: problem.cpp:698
int * s
Definition: problem.h:55
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
int * feat
Definition: problem.h:63
double getWidth() const
int getNumOverlaps() const
void delete_chain(Chain *chain)
Definition: problem.cpp:48
QLinkedList< int > * conflicts
Definition: problem.cpp:362
#define EPSILON
Definition: util.h:75
Summary statistics of labeling problem.
Definition: palstat.h:48
void ignoreLabel(LabelPosition *lp, PriorityQueue *list, RTree< LabelPosition *, double, 2, double > *candidates)
Definition: problem.cpp:197
LabelPosition is a candidate feature label position.
Definition: labelposition.h:55
bool falpCallback2(LabelPosition *lp, void *ctx)
Definition: problem.cpp:183
PriorityQueue * list
Definition: problem.cpp:178
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:824
void init_sol_empty()
Basic initial solution : every feature to -1.
Definition: problem.cpp:157
double delta
Definition: problem.h:62
void init_sol_falp()
Definition: problem.cpp:240
void decreaseKey(int key)