QGIS API Documentation  2.11.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
pal.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 //#define _VERBOSE_
31 
32 #define _CRT_SECURE_NO_DEPRECATE
33 
34 #include "qgsgeometry.h"
35 #include "pal.h"
36 #include "layer.h"
37 #include "palexception.h"
38 #include "palstat.h"
39 #include "rtree.hpp"
40 #include "costcalculator.h"
41 #include "feature.h"
42 #include "geomfunction.h"
43 #include "labelposition.h"
44 #include "problem.h"
45 #include "pointset.h"
46 #include "util.h"
47 #include <QTime>
48 #include <cstdarg>
49 #include <iostream>
50 #include <fstream>
51 #include <cfloat>
52 #include <list>
53 
54 namespace pal
55 {
56  GEOSContextHandle_t geosContext()
57  {
59  }
60 
62  {
63  // do not init and exit GEOS - we do it inside QGIS
64  //initGEOS( geosNotice, geosError );
65 
66  fnIsCancelled = 0;
67  fnIsCancelledContext = 0;
68 
69  ejChainDeg = 50;
70  tenure = 10;
71  candListSize = 0.2;
72 
73  tabuMinIt = 3;
74  tabuMaxIt = 4;
75  searchMethod = POPMUSIC_CHAIN;
76  popmusic_r = 30;
77 
78  searchMethod = CHAIN;
79 
80  setSearch( CHAIN );
81 
82  point_p = 8;
83  line_p = 8;
84  poly_p = 8;
85 
86  showPartial = true;
87 
88  std::cout.precision( 12 );
89  std::cerr.precision( 12 );
90 
91  }
92 
94  {
95  // TODO make const ! or whatever else
96  return mLayers.values();
97  }
98 
99  Layer *Pal::getLayer( const QString& layerName )
100  {
101  mMutex.lock();
102  if ( !mLayers.contains( layerName ) )
103  {
104  mMutex.unlock();
105  throw new PalException::UnknownLayer();
106  }
107 
108  Layer* result = mLayers.value( layerName );
109  mMutex.unlock();
110  return result;
111  }
112 
113  void Pal::removeLayer( Layer *layer )
114  {
115  if ( !layer )
116  return;
117 
118  mMutex.lock();
119  QString key = mLayers.key( layer, QString() );
120  if ( !key.isEmpty() )
121  {
122  mLayers.remove( key );
123  }
124  delete layer;
125  mMutex.unlock();
126  }
127 
129  {
130 
131  mMutex.lock();
132 
133  qDeleteAll( mLayers );
134  mLayers.clear();
135  mMutex.unlock();
136 
137  // do not init and exit GEOS - we do it inside QGIS
138  //finishGEOS();
139  }
140 
141  Layer* Pal::addLayer( const QString &layerName, Arrangement arrangement, double defaultPriority, bool obstacle, bool active, bool toLabel, bool displayAll )
142  {
143  mMutex.lock();
144 
145  //check if layer is already known
146  if ( mLayers.contains( layerName ) )
147  {
148  mMutex.unlock();
149  //There is already a layer with this name, so we just return the existing one.
150  //Sometimes the same layer is added twice (e.g. datetime split with otf-reprojection)
151  return mLayers.value( layerName );
152  }
153 
154  Layer* layer = new Layer( layerName, arrangement, defaultPriority, obstacle, active, toLabel, this, displayAll );
155  mLayers.insert( layerName, layer );
156  mMutex.unlock();
157 
158  return layer;
159  }
160 
161  typedef struct _featCbackCtx
162  {
167  double bbox_min[2];
168  double bbox_max[2];
169  } FeatCallBackCtx;
170 
171 
172 
173  /*
174  * Callback function
175  *
176  * Extract a specific shape from indexes
177  */
178  bool extractFeatCallback( FeaturePart *ft_ptr, void *ctx )
179  {
180  double amin[2], amax[2];
181 
182  FeatCallBackCtx *context = ( FeatCallBackCtx* ) ctx;
183 
184 #ifdef _DEBUG_FULL_
185  std::cout << "extract feat : " << ft_ptr->getLayer()->getName() << "/" << ft_ptr->getUID() << std::endl;
186 #endif
187 
188  // all feature which are obstacle will be inserted into obstacles
189  if ( ft_ptr->getFeature()->isObstacle() )
190  {
191  ft_ptr->getBoundingBox( amin, amax );
192  context->obstacles->Insert( amin, amax, ft_ptr );
193  }
194 
195  // first do some checks whether to extract candidates or not
196 
197  // feature has to be labeled?
198  if ( !context->layer->labelLayer() )
199  return true;
200 
201  // is the feature well defined? TODO Check epsilon
202  if ( ft_ptr->getLabelWidth() < 0.0000001 || ft_ptr->getLabelHeight() < 0.0000001 )
203  return true;
204 
205  // OK, everything's fine, let's process the feature part
206 
207  // Holes of the feature are obstacles
208  for ( int i = 0; i < ft_ptr->getNumSelfObstacles(); i++ )
209  {
210  ft_ptr->getSelfObstacle( i )->getBoundingBox( amin, amax );
211  context->obstacles->Insert( amin, amax, ft_ptr->getSelfObstacle( i ) );
212 
213  if ( !ft_ptr->getSelfObstacle( i )->getHoleOf() )
214  {
215  std::cout << "ERROR: SHOULD HAVE A PARENT!!!!!" << std::endl;
216  }
217  }
218 
219  // generate candidates for the feature part
220  LabelPosition** lPos = NULL;
221  int nblp = ft_ptr->setPosition( &lPos, context->bbox_min, context->bbox_max, ft_ptr, context->candidates );
222 
223  if ( nblp > 0 )
224  {
225  // valid features are added to fFeats
226  Feats *ft = new Feats();
227  ft->feature = ft_ptr;
228  ft->shape = NULL;
229  ft->nblp = nblp;
230  ft->lPos = lPos;
231  ft->priority = ft_ptr->getFeature()->calculatePriority();
232  context->fFeats->append( ft );
233  }
234  else
235  {
236  // Others are deleted
237  delete[] lPos;
238  }
239 
240  return true;
241  }
242 
243 
244 
245 
246  typedef struct _filterContext
247  {
250  } FilterContext;
251 
252  bool filteringCallback( FeaturePart *featurePart, void *ctx )
253  {
254 
255  RTree<LabelPosition*, double, 2, double> *cdtsIndex = (( FilterContext* ) ctx )->cdtsIndex;
256  Pal* pal = (( FilterContext* )ctx )->pal;
257 
258  if ( pal->isCancelled() )
259  return false; // do not continue searching
260 
261  double amin[2], amax[2];
262  featurePart->getBoundingBox( amin, amax );
263 
264  LabelPosition::PruneCtx pruneContext;
265  pruneContext.obstacle = featurePart;
266  pruneContext.pal = pal;
267  cdtsIndex->Search( amin, amax, LabelPosition::pruneCallback, ( void* ) &pruneContext );
268 
269  return true;
270  }
271 
272  Problem* Pal::extract( const QStringList& layerNames, double lambda_min, double phi_min, double lambda_max, double phi_max )
273  {
274  // to store obstacles
275  RTree<FeaturePart*, double, 2, double> *obstacles = new RTree<FeaturePart*, double, 2, double>();
276 
277  Problem *prob = new Problem();
278 
279  int i, j;
280 
281  double bbx[4];
282  double bby[4];
283 
284  double amin[2];
285  double amax[2];
286 
287  int max_p = 0;
288 
289  LabelPosition* lp;
290 
291  bbx[0] = bbx[3] = amin[0] = prob->bbox[0] = lambda_min;
292  bby[0] = bby[1] = amin[1] = prob->bbox[1] = phi_min;
293  bbx[1] = bbx[2] = amax[0] = prob->bbox[2] = lambda_max;
294  bby[2] = bby[3] = amax[1] = prob->bbox[3] = phi_max;
295 
296  prob->pal = this;
297 
299 
300  FeatCallBackCtx *context = new FeatCallBackCtx();
301  context->fFeats = fFeats;
302  context->obstacles = obstacles;
303  context->candidates = prob->candidates;
304 
305  context->bbox_min[0] = amin[0];
306  context->bbox_min[1] = amin[1];
307 
308  context->bbox_max[0] = amax[0];
309  context->bbox_max[1] = amax[1];
310 
311  // first step : extract features from layers
312 
313  int previousFeatureCount = 0;
314  Layer *layer;
315 
316  QStringList layersWithFeaturesInBBox;
317 
318  mMutex.lock();
319  Q_FOREACH ( QString layerName, layerNames )
320  {
321  layer = mLayers.value( layerName, 0 );
322  if ( !layer )
323  {
324  // invalid layer name
325  continue;
326  }
327 
328  // only select those who are active
329  if ( !layer->active() )
330  continue;
331 
332  // check for connected features with the same label text and join them
333  if ( layer->mergeConnectedLines() )
334  layer->joinConnectedFeatures();
335 
336  layer->chopFeaturesAtRepeatDistance();
337 
338  // find features within bounding box and generate candidates list
339  context->layer = layer;
340  context->layer->mMutex.lock();
341  context->layer->rtree->Search( amin, amax, extractFeatCallback, ( void* ) context );
342  context->layer->mMutex.unlock();
343 
344  if ( context->fFeats->size() - previousFeatureCount > 0 )
345  {
346  layersWithFeaturesInBBox << layer->name();
347  }
348  previousFeatureCount = context->fFeats->size();
349  }
350  delete context;
351  mMutex.unlock();
352 
353  prob->nbLabelledLayers = layersWithFeaturesInBBox.size();
354  prob->labelledLayersName = layersWithFeaturesInBBox;
355 
356  if ( fFeats->size() == 0 )
357  {
358 #ifdef _VERBOSE_
359  std::cout << std::endl << "Empty problem" << std::endl;
360 #endif
361  delete fFeats;
362  delete prob;
363  delete obstacles;
364  return NULL;
365  }
366 
367  prob->nbft = fFeats->size();
368  prob->nblp = 0;
369  prob->featNbLp = new int [prob->nbft];
370  prob->featStartId = new int [prob->nbft];
371  prob->inactiveCost = new double[prob->nbft];
372 
373  Feats *feat;
374 
375 #ifdef _VERBOSE_
376  std::cout << "FIRST NBFT : " << prob->nbft << std::endl;
377 #endif
378 
379  // Filtering label positions against obstacles
380  amin[0] = amin[1] = -DBL_MAX;
381  amax[0] = amax[1] = DBL_MAX;
382  FilterContext filterCtx;
383  filterCtx.cdtsIndex = prob->candidates;
384  filterCtx.pal = this;
385  obstacles->Search( amin, amax, filteringCallback, ( void* ) &filterCtx );
386 
387  if ( isCancelled() )
388  {
389  qDeleteAll( *fFeats );
390  delete fFeats;
391  delete prob;
392  delete obstacles;
393  return 0;
394  }
395 
396  int idlp = 0;
397  for ( i = 0; i < prob->nbft; i++ ) /* foreach feature into prob */
398  {
399  feat = fFeats->takeFirst();
400 #ifdef _DEBUG_FULL_
401  std::cout << "Feature:" << feat->feature->getLayer()->getName() << "/" << feat->feature->getUID() << " candidates " << feat->nblp << std::endl;
402 #endif
403  prob->featStartId[i] = idlp;
404  prob->inactiveCost[i] = pow( 2, 10 - 10 * feat->priority );
405 
406  switch ( feat->feature->getGeosType() )
407  {
408  case GEOS_POINT:
409  max_p = point_p;
410  break;
411  case GEOS_LINESTRING:
412  max_p = line_p;
413  break;
414  case GEOS_POLYGON:
415  max_p = poly_p;
416  break;
417  }
418 
419  // sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
420  max_p = CostCalculator::finalizeCandidatesCosts( feat, max_p, obstacles, bbx, bby );
421 
422 #ifdef _DEBUG_FULL_
423  std::cout << "All costs are set" << std::endl;
424 #endif
425  // only keep the 'max_p' best candidates
426  for ( j = max_p; j < feat->nblp; j++ )
427  {
428  // TODO remove from index
429  feat->lPos[j]->removeFromIndex( prob->candidates );
430  delete feat->lPos[j];
431  }
432  feat->nblp = max_p;
433 
434  // update problem's # candidate
435  prob->featNbLp[i] = feat->nblp;
436  prob->nblp += feat->nblp;
437 
438  // add all candidates into a rtree (to speed up conflicts searching)
439  for ( j = 0; j < feat->nblp; j++, idlp++ )
440  {
441  lp = feat->lPos[j];
442  //lp->insertIntoIndex(prob->candidates);
443  lp->setProblemIds( i, idlp ); // bugfix #1 (maxence 10/23/2008)
444  }
445  fFeats->append( feat );
446  }
447 
448 #ifdef _DEBUG_FULL_
449  std::cout << "Malloc problem...." << std::endl;
450 #endif
451 
452 
453  idlp = 0;
454  int nbOverlaps = 0;
455  prob->labelpositions = new LabelPosition*[prob->nblp];
456  //prob->feat = new int[prob->nblp];
457 
458 #ifdef _DEBUG_FULL_
459  std::cout << "problem malloc'd" << std::endl;
460 #endif
461 
462 
463  j = 0;
464  while ( fFeats->size() > 0 ) // foreach feature
465  {
466  if ( isCancelled() )
467  {
468  qDeleteAll( *fFeats );
469  delete fFeats;
470  delete prob;
471  delete obstacles;
472  return 0;
473  }
474 
475  feat = fFeats->takeFirst();
476  for ( i = 0; i < feat->nblp; i++, idlp++ ) // foreach label candidate
477  {
478  lp = feat->lPos[i];
479  lp->resetNumOverlaps();
480 
481  // make sure that candidate's cost is less than 1
482  lp->validateCost();
483 
484  prob->labelpositions[idlp] = lp;
485  //prob->feat[idlp] = j;
486 
487  lp->getBoundingBox( amin, amax );
488 
489  // lookup for overlapping candidate
490  prob->candidates->Search( amin, amax, LabelPosition::countOverlapCallback, ( void* ) lp );
491 
492  nbOverlaps += lp->getNumOverlaps();
493 #ifdef _DEBUG_FULL_
494  std::cout << "Nb overlap for " << idlp << "/" << prob->nblp - 1 << " : " << lp->getNumOverlaps() << std::endl;
495 #endif
496  }
497  j++;
498  delete[] feat->lPos;
499  delete feat;
500  }
501  delete fFeats;
502 
503  //delete candidates;
504  delete obstacles;
505 
506 
507  nbOverlaps /= 2;
508  prob->all_nblp = prob->nblp;
509  prob->nbOverlap = nbOverlaps;
510 
511 
512 #ifdef _VERBOSE_
513  std::cout << "nbOverlap: " << prob->nbOverlap << std::endl;
514  std::cerr << prob->nbft << "\t"
515  << prob->nblp << "\t"
516  << prob->nbOverlap << "\t";
517 #endif
518 
519  return prob;
520  }
521 
522  std::list<LabelPosition*>* Pal::labeller( double bbox[4], PalStat **stats, bool displayAll )
523  {
524  return labeller( mLayers.keys(), bbox, stats, displayAll );
525  }
526 
527  /*
528  * BIG MACHINE
529  */
530  std::list<LabelPosition*>* Pal::labeller( const QStringList& layerNames, double bbox[4], PalStat **stats, bool displayAll )
531  {
532 #ifdef _DEBUG_
533  std::cout << "LABELLER (selection)" << std::endl;
534 #endif
535 
536  Problem *prob;
537 
538  SearchMethod old_searchMethod = searchMethod;
539 
540  if ( displayAll )
541  {
543  }
544 
545 #ifdef _VERBOSE_
546  clock_t start = clock();
547  double create_time;
548  std::cout << std::endl << "bbox: " << bbox[0] << " " << bbox[1] << " " << bbox[2] << " " << bbox[3] << std::endl;
549 #endif
550 
551  QTime t;
552  t.start();
553 
554  // First, extract the problem
555  if (( prob = extract( layerNames, bbox[0], bbox[1], bbox[2], bbox[3] ) ) == NULL )
556  {
557  // nothing to be done => return an empty result set
558  if ( stats )
559  ( *stats ) = new PalStat();
560  return new std::list<LabelPosition*>();
561  }
562 
563  std::cout << "PAL EXTRACT: " << t.elapsed() / 1000.0 << " s" << std::endl;
564  t.restart();
565 
566  // reduce number of candidates
567  // (remove candidates which surely won't be used)
568  prob->reduce();
569 
570 #ifdef _VERBOSE_
571  std::cerr << prob->nblp << "\t"
572  << prob->nbOverlap;
573 #endif
574 
575 
576  prob->displayAll = displayAll;
577 
578 #ifdef _VERBOSE_
579  create_time = double( clock() - start ) / double( CLOCKS_PER_SEC );
580 
581  std::cout << std::endl << "Problem : " << prob->nblp << " candidates for " << prob->nbft << " features makes " << prob->nbOverlap << " overlaps" << std::endl;
582  std::cout << std::endl << "Times:" << std::endl << " to create problem: " << create_time << std::endl;
583 #endif
584 
585  // search a solution
586  if ( searchMethod == FALP )
587  prob->init_sol_falp();
588  else if ( searchMethod == CHAIN )
589  prob->chain_search();
590  else
591  prob->popmusic();
592 
593  std::cout << "PAL SEARCH (" << searchMethod << "): " << t.elapsed() / 1000.0 << " s" << std::endl;
594  t.restart();
595 
596  // Post-Optimization
597  //prob->post_optimization();
598 
599 
600  std::list<LabelPosition*> * solution = prob->getSolution( displayAll );
601 
602  if ( stats )
603  *stats = prob->getStats();
604 
605 #ifdef _VERBOSE_
606  clock_t total_time = clock() - start;
607  std::cout << " Total time: " << double( total_time ) / double( CLOCKS_PER_SEC ) << std::endl;
608  std::cerr << "\t" << create_time << "\t" << double( total_time ) / double( CLOCKS_PER_SEC ) << std::endl;
609 #endif
610 
611  delete prob;
612 
613 
614  if ( displayAll )
615  {
616  setSearch( old_searchMethod );
617  }
618 
619  return solution;
620  }
621 
622  void Pal::registerCancellationCallback( Pal::FnIsCancelled fnCancelled, void *context )
623  {
624  fnIsCancelled = fnCancelled;
625  fnIsCancelledContext = context;
626  }
627 
628  Problem* Pal::extractProblem( double bbox[4] )
629  {
630  return extract( mLayers.keys(), bbox[0], bbox[1], bbox[2], bbox[3] );
631  }
632 
633  std::list<LabelPosition*>* Pal::solveProblem( Problem* prob, bool displayAll )
634  {
635  if ( prob == NULL )
636  return new std::list<LabelPosition*>();
637 
638  prob->reduce();
639 
640  if ( searchMethod == FALP )
641  prob->init_sol_falp();
642  else if ( searchMethod == CHAIN )
643  prob->chain_search();
644  else
645  prob->popmusic();
646 
647  return prob->getSolution( displayAll );
648  }
649 
650 
651  void Pal::setPointP( int point_p )
652  {
653  if ( point_p > 0 )
654  this->point_p = point_p;
655  }
656 
657  void Pal::setLineP( int line_p )
658  {
659  if ( line_p > 0 )
660  this->line_p = line_p;
661  }
662 
663  void Pal::setPolyP( int poly_p )
664  {
665  if ( poly_p > 0 )
666  this->poly_p = poly_p;
667  }
668 
669 
670  void Pal::setMinIt( int min_it )
671  {
672  if ( min_it >= 0 )
673  tabuMinIt = min_it;
674  }
675 
676  void Pal::setMaxIt( int max_it )
677  {
678  if ( max_it > 0 )
679  tabuMaxIt = max_it;
680  }
681 
682  void Pal::setPopmusicR( int r )
683  {
684  if ( r > 0 )
685  popmusic_r = r;
686  }
687 
688  void Pal::setEjChainDeg( int degree )
689  {
690  this->ejChainDeg = degree;
691  }
692 
693  void Pal::setTenure( int tenure )
694  {
695  this->tenure = tenure;
696  }
697 
698  void Pal::setCandListSize( double fact )
699  {
700  this->candListSize = fact;
701  }
702 
703  void Pal::setShowPartial( bool show )
704  {
705  this->showPartial = show;
706  }
707 
709  {
710  return point_p;
711  }
712 
714  {
715  return line_p;
716  }
717 
719  {
720  return poly_p;
721  }
722 
723  int Pal::getMinIt()
724  {
725  return tabuMaxIt;
726  }
727 
728  int Pal::getMaxIt()
729  {
730  return tabuMinIt;
731  }
732 
734  {
735  return showPartial;
736  }
737 
739  {
740  return searchMethod;
741  }
742 
744  {
745  switch ( method )
746  {
747  case POPMUSIC_CHAIN:
748  searchMethod = method;
749  popmusic_r = 30;
750  tabuMinIt = 2;
751  tabuMaxIt = 4;
752  tenure = 10;
753  ejChainDeg = 50;
754  candListSize = 0.2;
755  break;
756  case CHAIN:
757  searchMethod = method;
758  ejChainDeg = 50;
759  break;
760  case POPMUSIC_TABU:
761  searchMethod = method;
762  popmusic_r = 25;
763  tabuMinIt = 2;
764  tabuMaxIt = 4;
765  tenure = 10;
766  ejChainDeg = 50;
767  candListSize = 0.2;
768  break;
769  case POPMUSIC_TABU_CHAIN:
770  searchMethod = method;
771  popmusic_r = 25;
772  tabuMinIt = 2;
773  tabuMaxIt = 4;
774  tenure = 10;
775  ejChainDeg = 50;
776  candListSize = 0.2;
777  break;
778  case FALP:
779  searchMethod = method;
780  break;
781  default:
782  std::cerr << "Unknown search method..." << std::endl;
783  }
784  }
785 
786 } // namespace pal
787 
void removeLayer(Layer *layer)
remove a layer
Definition: pal.cpp:113
PointSet * getHoleOf()
Returns NULL if this isn't a hole.
Definition: pointset.h:122
std::list< LabelPosition * > * solveProblem(Problem *prob, bool displayAll)
Definition: pal.cpp:633
FeaturePart * feature
Definition: util.h:53
Definition: pal.h:68
Feature * getFeature()
Returns the parent feature.
Definition: feature.h:264
double getLabelHeight() const
Definition: feature.h:298
bool labelLayer() const
Returns whether the layer will be labeled or not.
Definition: layer.h:138
int setPosition(LabelPosition ***lPos, double bbox_min[2], double bbox_max[2], PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
Generic method to generate candidates.
Definition: feature.cpp:1259
int getNumSelfObstacles() const
Definition: feature.h:308
friend class Problem
Definition: pal.h:111
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
A layer of spacial entites.
Definition: layer.h:57
void setPointP(int point_p)
set # candidates to generate for points features Higher the value is, longer Pal::labeller will spend...
Definition: pal.cpp:651
RTree< LabelPosition *, double, 2, double > * cdtsIndex
Definition: pal.cpp:248
void setPolyP(int poly_p)
set maximum # candidates to generate for polygon features Higher the value is, longer Pal::labeller w...
Definition: pal.cpp:663
Layer * layer
Definition: pal.cpp:163
void popmusic()
popmusic framework
Definition: problem.cpp:415
Pal main class.
Definition: pal.h:109
bool isCancelled()
Check whether the job has been cancelled.
Definition: pal.h:205
is slower and best than TABU, worse and faster than TABU_CHAIN
Definition: pal.h:67
bool(* FnIsCancelled)(void *ctx)
Definition: pal.h:199
double getLabelWidth() const
Definition: feature.h:297
QLinkedList< Feats * > * fFeats
Definition: pal.cpp:164
void unlock()
double bbox_min[2]
Definition: pal.cpp:167
int getLineP()
get maximum # candidates to generate for line features
Definition: pal.cpp:713
std::list< LabelPosition * > * getSolution(bool returnInactive)
Definition: problem.cpp:2609
PointSet * shape
Definition: util.h:54
is a little bit better than CHAIN but slower
Definition: pal.h:66
int size() const
int elapsed() const
Try to access an unknown layer.
Definition: palexception.h:67
QString getUID() const
Returns the unique ID of the feature.
Definition: feature.cpp:191
double isObstacle() const
Returns whether the feature will act as an obstacle for labels.
Definition: feature.h:121
void chain_search()
Test with very-large scale neighborhood.
Definition: problem.cpp:2446
void setSearch(SearchMethod method)
Select the search method to use.
Definition: pal.cpp:743
RTree< FeaturePart *, double, 2, double > * obstacles
Definition: pal.cpp:165
is the best but slowest
Definition: pal.h:65
bool isEmpty() const
int getPointP()
get # candidates to generate for point features
Definition: pal.cpp:708
int restart()
Problem * extractProblem(double bbox[4])
Definition: pal.cpp:628
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
Definition: pal.cpp:56
For usage in problem solving algorithm.
Definition: util.h:50
double priority
Definition: util.h:55
Main class to handle feature.
Definition: feature.h:203
Layer * getLayer(const QString &layerName)
Look for a layer.
Definition: pal.cpp:99
Layer * addLayer(const QString &layerName, Arrangement arrangement, double defaultPriority, bool obstacle, bool active, bool toLabel, bool displayAll=false)
add a new layer
Definition: pal.cpp:141
friend class Layer
Definition: pal.h:113
QList< Layer * > getLayers()
get all layers
Definition: pal.cpp:93
static bool pruneCallback(LabelPosition *lp, void *ctx)
Check whether the candidate in ctx overlap with obstacle feat.
RTree< LabelPosition *, double, 2, double > * candidates
Definition: pal.cpp:166
bool extractFeatCallback(FeaturePart *ft_ptr, void *ctx)
Definition: pal.cpp:178
void lock()
void setShowPartial(bool show)
Set flag show partial label.
Definition: pal.cpp:703
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:115
PalStat * getStats()
Definition: problem.cpp:2643
std::list< LabelPosition * > * labeller(double bbox[4], PalStat **stats, bool displayAll)
the labeling machine Will extract all active layers
Definition: pal.cpp:522
bool getShowPartial()
Get flag show partial label.
Definition: pal.cpp:733
Arrangement
The way to arrange labels against spatial entities.
Definition: pal.h:75
double bbox_max[2]
Definition: pal.cpp:168
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
~Pal()
delete an instance
Definition: pal.cpp:128
struct pal::_filterContext FilterContext
void init_sol_falp()
Definition: problem.cpp:299
LabelPosition ** lPos
Definition: util.h:57
FeaturePart * getSelfObstacle(int i)
Definition: feature.h:309
Summury of problem.
Definition: palstat.h:41
LabelPosition is a candidate feature label position.
Definition: labelposition.h:48
SearchMethod getSearch()
get the search method in use
Definition: pal.cpp:738
Pal()
Create an new pal instance.
Definition: pal.cpp:61
Represent a problem.
Definition: problem.h:92
bool filteringCallback(FeaturePart *featurePart, void *ctx)
Definition: pal.cpp:252
void start()
void setLineP(int line_p)
set maximum # candidates to generate for lines features Higher the value is, longer Pal::labeller wil...
Definition: pal.cpp:657
static int finalizeCandidatesCosts(Feats *feat, int max_p, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
void reduce()
Definition: problem.cpp:144
int getPolyP()
get maximum # candidates to generate for polygon features
Definition: pal.cpp:718
double calculatePriority() const
Calculates the priority for the feature.
Definition: feature.cpp:92
SearchMethod
Search method to use.
Definition: pal.h:62
int nblp
Definition: util.h:56
struct pal::_featCbackCtx FeatCallBackCtx
is the worst but fastest method
Definition: pal.h:64
int size() const
void registerCancellationCallback(FnIsCancelled fnCancelled, void *context)
Register a function that returns whether this job has been cancelled - PAL calls it during the comput...
Definition: pal.cpp:622
void append(const T &value)