QGIS API Documentation  2.11.0-Master
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 #include <QTime>
32 
33 #define _CRT_SECURE_NO_DEPRECATE
34 
35 #include <cstdarg>
36 #include <iostream>
37 #include <fstream>
38 #include <cstring>
39 #include <cfloat>
40 #include <list>
41 //#include <geos/geom/Geometry.h>
42 #include <geos_c.h>
43 
44 #include "pal.h"
45 #include "layer.h"
46 #include "palexception.h"
47 #include "palstat.h"
48 #include "linkedlist.hpp"
49 #include "rtree.hpp"
50 #include "costcalculator.h"
51 #include "feature.h"
52 #include "geomfunction.h"
53 #include "labelposition.h"
54 #include "problem.h"
55 #include "pointset.h"
56 #include "util.h"
57 
58 #include <qgsgeometry.h> // for GEOS context
59 
60 namespace pal
61 {
62 
63  void geosError( const char *fmt, ... )
64  {
65  va_list list;
66  va_start( list, fmt );
67  vfprintf( stderr, fmt, list );
68  va_end( list );
69  }
70 
71  void geosNotice( const char *fmt, ... )
72  {
73  va_list list;
74  va_start( list, fmt );
75  vfprintf( stdout, fmt, list );
76  va_end( list );
77  }
78 
79  GEOSContextHandle_t geosContext()
80  {
82  }
83 
85  {
86  // do not init and exit GEOS - we do it inside QGIS
87  //initGEOS( geosNotice, geosError );
88 
89  fnIsCancelled = 0;
90  fnIsCancelledContext = 0;
91 
92  layers = new QList<Layer*>();
93 
94  ejChainDeg = 50;
95  tenure = 10;
96  candListSize = 0.2;
97 
98  tabuMinIt = 3;
99  tabuMaxIt = 4;
100  searchMethod = POPMUSIC_CHAIN;
101  popmusic_r = 30;
102 
103  searchMethod = CHAIN;
104 
105  setSearch( CHAIN );
106 
107  dpi = 72;
108  point_p = 8;
109  line_p = 8;
110  poly_p = 8;
111 
112  showPartial = true;
113 
114  this->map_unit = pal::METER;
115 
116  std::cout.precision( 12 );
117  std::cerr.precision( 12 );
118 
119  }
120 
122  {
123  // TODO make const ! or whatever else
124  return layers;
125  }
126 
127  Layer *Pal::getLayer( const char *lyrName )
128  {
129  mMutex.lock();
130  for ( QList<Layer*>::iterator it = layers->begin(); it != layers->end(); ++it )
131  if ( strcmp(( *it )->name, lyrName ) == 0 )
132  {
133  mMutex.unlock();
134  return *it;
135  }
136 
137  mMutex.unlock();
138  throw new PalException::UnknownLayer();
139  }
140 
141 
142  void Pal::removeLayer( Layer *layer )
143  {
144  mMutex.lock();
145  if ( layer )
146  {
147  layers->removeOne( layer );
148  delete layer;
149  }
150  mMutex.unlock();
151  }
152 
153 
155  {
156 
157  mMutex.lock();
158  while ( layers->size() > 0 )
159  {
160  delete layers->front();
161  layers->pop_front();
162  }
163 
164  delete layers;
165  mMutex.unlock();
166 
167  // do not init and exit GEOS - we do it inside QGIS
168  //finishGEOS();
169  }
170 
171 
172  Layer * Pal::addLayer( const char *lyrName, double min_scale, double max_scale, Arrangement arrangement, Units label_unit, double defaultPriority, bool obstacle, bool active, bool toLabel, bool displayAll )
173  {
174  Layer *lyr;
175  mMutex.lock();
176 
177 #ifdef _DEBUG_
178  std::cout << "Pal::addLayer" << std::endl;
179  std::cout << "lyrName:" << lyrName << std::endl;
180  std::cout << "nbLayers:" << layers->size() << std::endl;
181 #endif
182 
183  for ( QList<Layer*>::iterator it = layers->begin(); it != layers->end(); ++it )
184  {
185  if ( strcmp(( *it )->name, lyrName ) == 0 ) // if layer already known
186  {
187  mMutex.unlock();
188  //There is already a layer with this name, so we just return the existing one.
189  //Sometimes the same layer is added twice (e.g. datetime split with otf-reprojection)
190  return *it;
191  }
192  }
193 
194  lyr = new Layer( lyrName, min_scale, max_scale, arrangement, label_unit, defaultPriority, obstacle, active, toLabel, this, displayAll );
195  layers->push_back( lyr );
196 
197  mMutex.unlock();
198 
199  return lyr;
200  }
201 
202 
203  typedef struct _featCbackCtx
204  {
206  double scale;
210  double priority;
211  double bbox_min[2];
212  double bbox_max[2];
213  } FeatCallBackCtx;
214 
215 
216 
217  /*
218  * Callback function
219  *
220  * Extract a specific shape from indexes
221  */
222  bool extractFeatCallback( FeaturePart *ft_ptr, void *ctx )
223  {
224  double amin[2], amax[2];
225 
226  FeatCallBackCtx *context = ( FeatCallBackCtx* ) ctx;
227 
228 #ifdef _DEBUG_FULL_
229  std::cout << "extract feat : " << ft_ptr->getLayer()->getName() << "/" << ft_ptr->getUID() << std::endl;
230 #endif
231 
232  // all feature which are obstacle will be inserted into obstacles
233  if ( context->layer->obstacle )
234  {
235  ft_ptr->getBoundingBox( amin, amax );
236  context->obstacles->Insert( amin, amax, ft_ptr );
237  }
238 
239  // first do some checks whether to extract candidates or not
240 
241  // feature has to be labeled?
242  if ( !context->layer->toLabel )
243  return true;
244 
245  // are we in a valid scale range for the layer?
246  if ( !context->layer->isScaleValid( context->scale ) )
247  return true;
248 
249  // is the feature well defined? TODO Check epsilon
250  if ( ft_ptr->getLabelWidth() < 0.0000001 || ft_ptr->getLabelHeight() < 0.0000001 )
251  return true;
252 
253  // OK, everything's fine, let's process the feature part
254 
255  // Holes of the feature are obstacles
256  for ( int i = 0; i < ft_ptr->getNumSelfObstacles(); i++ )
257  {
258  ft_ptr->getSelfObstacle( i )->getBoundingBox( amin, amax );
259  context->obstacles->Insert( amin, amax, ft_ptr->getSelfObstacle( i ) );
260 
261  if ( !ft_ptr->getSelfObstacle( i )->getHoleOf() )
262  {
263  std::cout << "ERROR: SHOULD HAVE A PARENT!!!!!" << std::endl;
264  }
265  }
266 
267  // generate candidates for the feature part
268  LabelPosition** lPos = NULL;
269  int nblp = ft_ptr->setPosition( context->scale, &lPos, context->bbox_min, context->bbox_max, ft_ptr, context->candidates );
270 
271  if ( nblp > 0 )
272  {
273  // valid features are added to fFeats
274  Feats *ft = new Feats();
275  ft->feature = ft_ptr;
276  ft->shape = NULL;
277  ft->nblp = nblp;
278  ft->lPos = lPos;
279  ft->priority = context->priority;
280  context->fFeats->push_back( ft );
281  }
282  else
283  {
284  // Others are deleted
285  delete[] lPos;
286  }
287 
288  return true;
289  }
290 
291 
292 
293 
294  typedef struct _filterContext
295  {
297  double scale;
299  } FilterContext;
300 
301  bool filteringCallback( PointSet *pset, void *ctx )
302  {
303 
304  RTree<LabelPosition*, double, 2, double> *cdtsIndex = (( FilterContext* ) ctx )->cdtsIndex;
305  double scale = (( FilterContext* ) ctx )->scale;
306  Pal* pal = (( FilterContext* )ctx )->pal;
307 
308  if ( pal->isCancelled() )
309  return false; // do not continue searching
310 
311  double amin[2], amax[2];
312  pset->getBoundingBox( amin, amax );
313 
314  LabelPosition::PruneCtx pruneContext;
315 
316  pruneContext.scale = scale;
317  pruneContext.obstacle = pset;
318  pruneContext.pal = pal;
319  cdtsIndex->Search( amin, amax, LabelPosition::pruneCallback, ( void* ) &pruneContext );
320 
321  return true;
322  }
323 
324  Problem* Pal::extract( int nbLayers, char **layersName, double *layersFactor, double lambda_min, double phi_min, double lambda_max, double phi_max, double scale )
325  {
326  // to store obstacles
327  RTree<PointSet*, double, 2, double> *obstacles = new RTree<PointSet*, double, 2, double>();
328 
329  Problem *prob = new Problem();
330 
331  int i, j;
332 
333  double bbx[4];
334  double bby[4];
335 
336  double amin[2];
337  double amax[2];
338 
339  int max_p = 0;
340 
341  LabelPosition* lp;
342 
343  bbx[0] = bbx[3] = amin[0] = prob->bbox[0] = lambda_min;
344  bby[0] = bby[1] = amin[1] = prob->bbox[1] = phi_min;
345  bbx[1] = bbx[2] = amax[0] = prob->bbox[2] = lambda_max;
346  bby[2] = bby[3] = amax[1] = prob->bbox[3] = phi_max;
347 
348 
349  prob->scale = scale;
350  prob->pal = this;
351 
352  LinkedList<Feats*> *fFeats = new LinkedList<Feats*> ( ptrFeatsCompare );
353 
354  FeatCallBackCtx *context = new FeatCallBackCtx();
355  context->fFeats = fFeats;
356  context->scale = scale;
357  context->obstacles = obstacles;
358  context->candidates = prob->candidates;
359 
360  context->bbox_min[0] = amin[0];
361  context->bbox_min[1] = amin[1];
362 
363  context->bbox_max[0] = amax[0];
364  context->bbox_max[1] = amax[1];
365 
366 #ifdef _VERBOSE_
367  std::cout << nbLayers << "/" << layers->size() << " layers to extract " << std::endl;
368  std::cout << "scale is 1:" << scale << std::endl << std::endl;
369 
370 #endif
371 
372 
373  /* First step : extract feature from layers
374  *
375  * */
376  int oldNbft = 0;
377  Layer *layer;
378 
379  QList<char*> *labLayers = new QList<char*>();
380 
381  mMutex.lock();
382  for ( i = 0; i < nbLayers; i++ )
383  {
384  for ( QList<Layer*>::iterator it = layers->begin(); it != layers->end(); ++it ) // iterate on pal->layers
385  {
386  layer = *it;
387  // Only select those who are active and labellable (with scale constraint) or those who are active and which must be treated as obstaclewhich must be treated as obstacle
388  if ( layer->active
389  && ( layer->obstacle || ( layer->toLabel && layer->isScaleValid( scale ) ) ) )
390  {
391 
392  // check if this selected layers has been selected by user
393  if ( strcmp( layersName[i], layer->name ) == 0 )
394  {
395  // check for connected features with the same label text and join them
396  if ( layer->getMergeConnectedLines() )
397  layer->joinConnectedFeatures();
398 
399  layer->chopFeaturesAtRepeatDistance();
400 
401 
402  context->layer = layer;
403  context->priority = layersFactor[i];
404  // lookup for feature (and generates candidates list)
405 
406  context->layer->mMutex.lock();
407  context->layer->rtree->Search( amin, amax, extractFeatCallback, ( void* ) context );
408  context->layer->mMutex.unlock();
409 
410 #ifdef _VERBOSE_
411  std::cout << "Layer's name: " << layer->getName() << std::endl;
412  std::cout << " scale range: " << layer->getMinScale() << "->" << layer->getMaxScale() << std::endl;
413  std::cout << " active:" << layer->isToLabel() << std::endl;
414  std::cout << " obstacle:" << layer->isObstacle() << std::endl;
415  std::cout << " toLabel:" << layer->isToLabel() << std::endl;
416  std::cout << " # features: " << layer->getNbFeatures() << std::endl;
417  std::cout << " # extracted features: " << context->fFeats->size() - oldNbft << std::endl;
418 #endif
419  if ( context->fFeats->size() - oldNbft > 0 )
420  {
421  char *name = new char[strlen( layer->getName() ) +1];
422  strcpy( name, layer->getName() );
423  labLayers->push_back( name );
424  }
425  oldNbft = context->fFeats->size();
426 
427 
428  break;
429  }
430  }
431  }
432  }
433  delete context;
434  mMutex.unlock();
435 
436  prob->nbLabelledLayers = labLayers->size();
437  prob->labelledLayersName = new char*[prob->nbLabelledLayers];
438  for ( i = 0; i < prob->nbLabelledLayers; i++ )
439  {
440  prob->labelledLayersName[i] = labLayers->front();
441  labLayers->pop_front();
442  }
443 
444  delete labLayers;
445 
446  if ( fFeats->size() == 0 )
447  {
448 #ifdef _VERBOSE_
449  std::cout << std::endl << "Empty problem" << std::endl;
450 #endif
451  delete fFeats;
452  delete prob;
453  delete obstacles;
454  return NULL;
455  }
456 
457  prob->nbft = fFeats->size();
458  prob->nblp = 0;
459  prob->featNbLp = new int [prob->nbft];
460  prob->featStartId = new int [prob->nbft];
461  prob->inactiveCost = new double[prob->nbft];
462 
463  Feats *feat;
464 
465 #ifdef _VERBOSE_
466  std::cout << "FIRST NBFT : " << prob->nbft << std::endl;
467 #endif
468 
469  // Filtering label positions against obstacles
470  amin[0] = amin[1] = -DBL_MAX;
471  amax[0] = amax[1] = DBL_MAX;
472  FilterContext filterCtx;
473  filterCtx.cdtsIndex = prob->candidates;
474  filterCtx.scale = prob->scale;
475  filterCtx.pal = this;
476  obstacles->Search( amin, amax, filteringCallback, ( void* ) &filterCtx );
477 
478  if ( isCancelled() )
479  {
480  delete fFeats;
481  delete prob;
482  delete obstacles;
483  return 0;
484  }
485 
486  int idlp = 0;
487  for ( i = 0; i < prob->nbft; i++ ) /* foreach feature into prob */
488  {
489  feat = fFeats->pop_front();
490 #ifdef _DEBUG_FULL_
491  std::cout << "Feature:" << feat->feature->getLayer()->getName() << "/" << feat->feature->getUID() << " candidates " << feat->nblp << std::endl;
492 #endif
493  prob->featStartId[i] = idlp;
494  prob->inactiveCost[i] = pow( 2, 10 - 10 * feat->priority );
495 
496  switch ( feat->feature->getGeosType() )
497  {
498  case GEOS_POINT:
499  max_p = point_p;
500  break;
501  case GEOS_LINESTRING:
502  max_p = line_p;
503  break;
504  case GEOS_POLYGON:
505  max_p = poly_p;
506  break;
507  }
508 
509  // sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
510  max_p = CostCalculator::finalizeCandidatesCosts( feat, max_p, obstacles, bbx, bby );
511 
512 #ifdef _DEBUG_FULL_
513  std::cout << "All costs are set" << std::endl;
514 #endif
515  // only keep the 'max_p' best candidates
516  for ( j = max_p; j < feat->nblp; j++ )
517  {
518  // TODO remove from index
519  feat->lPos[j]->removeFromIndex( prob->candidates );
520  delete feat->lPos[j];
521  }
522  feat->nblp = max_p;
523 
524  // update problem's # candidate
525  prob->featNbLp[i] = feat->nblp;
526  prob->nblp += feat->nblp;
527 
528  // add all candidates into a rtree (to speed up conflicts searching)
529  for ( j = 0; j < feat->nblp; j++, idlp++ )
530  {
531  lp = feat->lPos[j];
532  //lp->insertIntoIndex(prob->candidates);
533  lp->setProblemIds( i, idlp ); // bugfix #1 (maxence 10/23/2008)
534  }
535  fFeats->push_back( feat );
536  }
537 
538 #ifdef _DEBUG_FULL_
539  std::cout << "Malloc problem...." << std::endl;
540 #endif
541 
542 
543  idlp = 0;
544  int nbOverlaps = 0;
545  prob->labelpositions = new LabelPosition*[prob->nblp];
546  //prob->feat = new int[prob->nblp];
547 
548 #ifdef _DEBUG_FULL_
549  std::cout << "problem malloc'd" << std::endl;
550 #endif
551 
552 
553  j = 0;
554  while ( fFeats->size() > 0 ) // foreach feature
555  {
556  if ( isCancelled() )
557  {
558  delete fFeats;
559  delete prob;
560  delete obstacles;
561  return 0;
562  }
563 
564  feat = fFeats->pop_front();
565  for ( i = 0; i < feat->nblp; i++, idlp++ ) // foreach label candidate
566  {
567  lp = feat->lPos[i];
568  lp->resetNumOverlaps();
569 
570  // make sure that candidate's cost is less than 1
571  lp->validateCost();
572 
573  prob->labelpositions[idlp] = lp;
574  //prob->feat[idlp] = j;
575 
576  lp->getBoundingBox( amin, amax );
577 
578  // lookup for overlapping candidate
579  prob->candidates->Search( amin, amax, LabelPosition::countOverlapCallback, ( void* ) lp );
580 
581  nbOverlaps += lp->getNumOverlaps();
582 #ifdef _DEBUG_FULL_
583  std::cout << "Nb overlap for " << idlp << "/" << prob->nblp - 1 << " : " << lp->getNumOverlaps() << std::endl;
584 #endif
585  }
586  j++;
587  delete[] feat->lPos;
588  delete feat;
589  }
590  delete fFeats;
591 
592  //delete candidates;
593  delete obstacles;
594 
595 
596  nbOverlaps /= 2;
597  prob->all_nblp = prob->nblp;
598  prob->nbOverlap = nbOverlaps;
599 
600 
601 #ifdef _VERBOSE_
602  std::cout << "nbOverlap: " << prob->nbOverlap << std::endl;
603  std::cerr << scale << "\t"
604  << prob->nbft << "\t"
605  << prob->nblp << "\t"
606  << prob->nbOverlap << "\t";
607 #endif
608 
609  return prob;
610  }
611 
612  std::list<LabelPosition*>* Pal::labeller( double scale, double bbox[4], PalStat **stats, bool displayAll )
613  {
614 
615 #ifdef _DEBUG_FULL_
616  std::cout << "LABELLER (active)" << std::endl;
617 #endif
618  int i;
619 
620  mMutex.lock();
621  int nbLayers = layers->size();
622 
623  char **layersName = new char*[nbLayers];
624  double *priorities = new double[nbLayers];
625  Layer *layer;
626  i = 0;
627  for ( QList<Layer*>::iterator it = layers->begin(); it != layers->end(); ++it )
628  {
629  layer = *it;
630  layersName[i] = layer->name;
631  priorities[i] = layer->defaultPriority;
632  i++;
633  }
634  mMutex.unlock();
635 
636  std::list<LabelPosition*> * solution = labeller( nbLayers, layersName, priorities, scale, bbox, stats, displayAll );
637 
638  delete[] layersName;
639  delete[] priorities;
640  return solution;
641  }
642 
643 
644  /*
645  * BIG MACHINE
646  */
647  std::list<LabelPosition*>* Pal::labeller( int nbLayers, char **layersName, double *layersFactor, double scale, double bbox[4], PalStat **stats, bool displayAll )
648  {
649 #ifdef _DEBUG_
650  std::cout << "LABELLER (selection)" << std::endl;
651 #endif
652 
653  Problem *prob;
654 
655  SearchMethod old_searchMethod = searchMethod;
656 
657  if ( displayAll )
658  {
660  }
661 
662 #ifdef _VERBOSE_
663  clock_t start = clock();
664  double create_time;
665  std::cout << std::endl << "bbox: " << bbox[0] << " " << bbox[1] << " " << bbox[2] << " " << bbox[3] << std::endl;
666 #endif
667 
668  QTime t;
669  t.start();
670 
671  // First, extract the problem
672  // TODO which is the minimum scale? (> 0, >= 0, >= 1, >1 )
673  if ( scale < 1 || ( prob = extract( nbLayers, layersName, layersFactor, bbox[0], bbox[1], bbox[2], bbox[3], scale ) ) == NULL )
674  {
675 
676 #ifdef _VERBOSE_
677  if ( scale < 1 )
678  std::cout << "Scale is 1:" << scale << std::endl;
679  else
680  std::cout << "empty problem... finishing" << std::endl;
681 #endif
682 
683  // nothing to be done => return an empty result set
684  if ( stats )
685  ( *stats ) = new PalStat();
686  return new std::list<LabelPosition*>();
687  }
688 
689  std::cout << "PAL EXTRACT: " << t.elapsed() / 1000.0 << " s" << std::endl;
690  t.restart();
691 
692  // reduce number of candidates
693  // (remove candidates which surely won't be used)
694  prob->reduce();
695 
696 #ifdef _VERBOSE_
697  std::cerr << prob->nblp << "\t"
698  << prob->nbOverlap;
699 #endif
700 
701 
702  prob->displayAll = displayAll;
703 
704 #ifdef _VERBOSE_
705  create_time = double( clock() - start ) / double( CLOCKS_PER_SEC );
706 
707  std::cout << std::endl << "Problem : " << prob->nblp << " candidates for " << prob->nbft << " features makes " << prob->nbOverlap << " overlaps" << std::endl;
708  std::cout << std::endl << "Times:" << std::endl << " to create problem: " << create_time << std::endl;
709 #endif
710 
711  // search a solution
712  if ( searchMethod == FALP )
713  prob->init_sol_falp();
714  else if ( searchMethod == CHAIN )
715  prob->chain_search();
716  else
717  prob->popmusic();
718 
719  std::cout << "PAL SEARCH (" << searchMethod << "): " << t.elapsed() / 1000.0 << " s" << std::endl;
720  t.restart();
721 
722  // Post-Optimization
723  //prob->post_optimization();
724 
725 
726  std::list<LabelPosition*> * solution = prob->getSolution( displayAll );
727 
728  if ( stats )
729  *stats = prob->getStats();
730 
731 #ifdef _VERBOSE_
732  clock_t total_time = clock() - start;
733  std::cout << " Total time: " << double( total_time ) / double( CLOCKS_PER_SEC ) << std::endl;
734  std::cerr << "\t" << create_time << "\t" << double( total_time ) / double( CLOCKS_PER_SEC ) << std::endl;
735 #endif
736 
737  delete prob;
738 
739 
740  if ( displayAll )
741  {
742  setSearch( old_searchMethod );
743  }
744 
745  return solution;
746  }
747 
748  void Pal::registerCancellationCallback( Pal::FnIsCancelled fnCancelled, void *context )
749  {
750  fnIsCancelled = fnCancelled;
751  fnIsCancelledContext = context;
752  }
753 
754  Problem* Pal::extractProblem( double scale, double bbox[4] )
755  {
756  // find out: nbLayers, layersName, layersFactor
757  mMutex.lock();
758  int nbLayers = layers->size();
759 
760  char **layersName = new char*[nbLayers];
761  double *priorities = new double[nbLayers];
762  Layer *layer;
763  int i = 0;
764  for ( QList<Layer*>::iterator it = layers->begin(); it != layers->end(); ++it )
765  {
766  layer = *it;
767  layersName[i] = layer->name;
768  priorities[i] = layer->defaultPriority;
769  i++;
770  }
771  mMutex.unlock();
772 
773  Problem* prob = extract( nbLayers, layersName, priorities, bbox[0], bbox[1], bbox[2], bbox[3], scale );
774 
775  delete[] layersName;
776  delete[] priorities;
777 
778  return prob;
779  }
780 
781  std::list<LabelPosition*>* Pal::solveProblem( Problem* prob, bool displayAll )
782  {
783  if ( prob == NULL )
784  return new std::list<LabelPosition*>();
785 
786  prob->reduce();
787 
788  if ( searchMethod == FALP )
789  prob->init_sol_falp();
790  else if ( searchMethod == CHAIN )
791  prob->chain_search();
792  else
793  prob->popmusic();
794 
795  return prob->getSolution( displayAll );
796  }
797 
798 
799  void Pal::setPointP( int point_p )
800  {
801  if ( point_p > 0 )
802  this->point_p = point_p;
803  }
804 
805  void Pal::setLineP( int line_p )
806  {
807  if ( line_p > 0 )
808  this->line_p = line_p;
809  }
810 
811  void Pal::setPolyP( int poly_p )
812  {
813  if ( poly_p > 0 )
814  this->poly_p = poly_p;
815  }
816 
817 
818  void Pal::setMinIt( int min_it )
819  {
820  if ( min_it >= 0 )
821  tabuMinIt = min_it;
822  }
823 
824  void Pal::setMaxIt( int max_it )
825  {
826  if ( max_it > 0 )
827  tabuMaxIt = max_it;
828  }
829 
830  void Pal::setPopmusicR( int r )
831  {
832  if ( r > 0 )
833  popmusic_r = r;
834  }
835 
836  void Pal::setEjChainDeg( int degree )
837  {
838  this->ejChainDeg = degree;
839  }
840 
841  void Pal::setTenure( int tenure )
842  {
843  this->tenure = tenure;
844  }
845 
846  void Pal::setCandListSize( double fact )
847  {
848  this->candListSize = fact;
849  }
850 
851 
852  void Pal::setDpi( int dpi )
853  {
854  if ( dpi > 0 )
855  this->dpi = dpi;
856  }
857 
858  void Pal::setShowPartial( bool show )
859  {
860  this->showPartial = show;
861  }
862 
864  {
865  return point_p;
866  }
867 
869  {
870  return line_p;
871  }
872 
874  {
875  return poly_p;
876  }
877 
878  int Pal::getMinIt()
879  {
880  return tabuMaxIt;
881  }
882 
883  int Pal::getMaxIt()
884  {
885  return tabuMinIt;
886  }
887 
889  {
890  return dpi;
891  }
892 
894  {
895  return showPartial;
896  }
897 
899  {
900  return searchMethod;
901  }
902 
904  {
905  switch ( method )
906  {
907  case POPMUSIC_CHAIN:
908  searchMethod = method;
909  popmusic_r = 30;
910  tabuMinIt = 2;
911  tabuMaxIt = 4;
912  tenure = 10;
913  ejChainDeg = 50;
914  candListSize = 0.2;
915  break;
916  case CHAIN:
917  searchMethod = method;
918  ejChainDeg = 50;
919  break;
920  case POPMUSIC_TABU:
921  searchMethod = method;
922  popmusic_r = 25;
923  tabuMinIt = 2;
924  tabuMaxIt = 4;
925  tenure = 10;
926  ejChainDeg = 50;
927  candListSize = 0.2;
928  break;
929  case POPMUSIC_TABU_CHAIN:
930  searchMethod = method;
931  popmusic_r = 25;
932  tabuMinIt = 2;
933  tabuMaxIt = 4;
934  tenure = 10;
935  ejChainDeg = 50;
936  candListSize = 0.2;
937  break;
938  case FALP:
939  searchMethod = method;
940  break;
941  default:
942  std::cerr << "Unknown search method..." << std::endl;
943  }
944  }
945 
947  {
948  return map_unit;
949  }
950 
951  void Pal::setMapUnit( Units map_unit )
952  {
953  if ( map_unit == pal::PIXEL || map_unit == pal::METER
954  || map_unit == pal::FOOT || map_unit == pal::DEGREE )
955  {
956  this->map_unit = map_unit;
957  }
958  }
959 
960 
961 
962 } // namespace pal
963 
void removeLayer(Layer *layer)
remove a layer
Definition: pal.cpp:142
PointSet * getHoleOf()
Returns NULL if this isn't a hole.
Definition: pointset.h:147
std::list< LabelPosition * > * solveProblem(Problem *prob, bool displayAll)
Definition: pal.cpp:781
foot [ft]
Definition: pal.h:67
double scale
Definition: pal.cpp:206
FeaturePart * feature
Definition: util.h:57
bool toLabel
Definition: layer.h:276
RTree< PointSet *, double, 2, double > * obstacles
Definition: pal.cpp:208
void push_back(const T &value)
bool isScaleValid(double scale)
check if the scal is in the scale range min_scale -> max_scale
Definition: layer.cpp:134
double getLabelHeight() const
Definition: feature.h:248
bool obstacle
Definition: layer.h:274
void setMapUnit(Units map_unit)
set map unit
Definition: pal.cpp:951
int getNumSelfObstacles() const
Definition: feature.h:258
friend class Problem
Definition: pal.h:123
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
A layer of spacial entites.
Definition: layer.h:60
is the best but slowest
Definition: pal.h:78
void setPointP(int point_p)
set # candidates to generate for points features Higher the value is, longer Pal::labeller will spend...
Definition: pal.cpp:799
RTree< LabelPosition *, double, 2, double > * cdtsIndex
Definition: pal.cpp:296
LinkedList< Feats * > * fFeats
Definition: pal.cpp:207
degree [°]
Definition: pal.h:68
void setPolyP(int poly_p)
set maximum # candidates to generate for polygon features Higher the value is, longer Pal::labeller w...
Definition: pal.cpp:811
Layer * layer
Definition: pal.cpp:205
void popmusic()
popmusic framework
Definition: problem.cpp:423
Pal main class.
Definition: pal.h:121
double defaultPriority
Definition: layer.h:272
bool isCancelled()
Check whether the job has been cancelled.
Definition: pal.h:227
double getLabelWidth() const
Definition: feature.h:247
void unlock()
QList< Layer * > * getLayers()
get all layers
Definition: pal.cpp:121
double priority
Definition: pal.cpp:210
Layer * getLayer()
return the layer that feature belongs to
Definition: feature.cpp:257
char * name
Definition: layer.h:262
Problem * extractProblem(double scale, double bbox[4])
Definition: pal.cpp:754
double bbox_min[2]
Definition: pal.cpp:211
int getLineP()
get maximum # candidates to generate for line features
Definition: pal.cpp:868
std::list< LabelPosition * > * getSolution(bool returnInactive)
Definition: problem.cpp:2625
PointSet * shape
Definition: util.h:58
int size() const
bool(* FnIsCancelled)(void *ctx)
Definition: pal.h:221
int elapsed() const
Try to access an unknown layer.
Definition: palexception.h:67
void pop_front()
void chain_search()
Test with very-large scale neighborhood.
Definition: problem.cpp:2462
void setSearch(SearchMethod method)
Select the search method to use.
Definition: pal.cpp:903
Layer * getLayer(const char *lyrName)
Look for a layer.
Definition: pal.cpp:127
bool filteringCallback(PointSet *pset, void *ctx)
Definition: pal.cpp:301
Layer * addLayer(const char *lyrName, double min_scale, double max_scale, Arrangement arrangement, Units label_unit, double defaultPriority, bool obstacle, bool active, bool toLabel, bool displayAll=false)
add a new layer
Definition: pal.cpp:172
int setPosition(double scale, LabelPosition ***lPos, double bbox_min[2], double bbox_max[2], PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
generic method to generate candidates This method will call either setPositionFromPoint(), setPositionFromLine or setPositionFromPolygon
Definition: feature.cpp:1319
int getPointP()
get # candidates to generate for point features
Definition: pal.cpp:863
void setDpi(int dpi)
Set map resolution.
Definition: pal.cpp:852
PointSet * getSelfObstacle(int i)
Definition: feature.h:259
void geosNotice(const char *fmt,...)
Definition: pal.cpp:71
int restart()
T & front()
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
Definition: pal.cpp:79
For usage in problem solving algorithm.
Definition: util.h:54
double priority
Definition: util.h:59
static int finalizeCandidatesCosts(Feats *feat, int max_p, RTree< PointSet *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
const char * getUID()
get the unique id of the feature
Definition: feature.cpp:263
Main class to handle feature.
Definition: feature.h:133
pixel [px]
Definition: pal.h:65
friend class Layer
Definition: pal.h:125
static bool pruneCallback(LabelPosition *lp, void *ctx)
Check whether the candidate in ctx overlap with obstacle feat.
bool ptrFeatsCompare(Feats *a, Feats *b)
Definition: util.h:249
RTree< LabelPosition *, double, 2, double > * candidates
Definition: pal.cpp:209
bool extractFeatCallback(FeaturePart *ft_ptr, void *ctx)
Definition: pal.cpp:222
void lock()
enum _searchMethod SearchMethod
Typedef for _Units enumeration.
Definition: pal.h:85
void setShowPartial(bool show)
Set flag show partial label.
Definition: pal.cpp:858
is slower and best than TABU, worse and faster than TABU_CHAIN
Definition: pal.h:80
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:140
PalStat * getStats()
Definition: problem.cpp:2659
const char * getName()
get layer's name
Definition: layer.cpp:146
bool getShowPartial()
Get flag show partial label.
Definition: pal.cpp:893
enum _arrangement Arrangement
Typedef for _arrangement enumeration.
Definition: pal.h:102
meter [m]
Definition: pal.h:66
double bbox_max[2]
Definition: pal.cpp:212
Definition: pal.h:81
static GEOSContextHandle_t getGEOSHandler()
return GEOS context handle
~Pal()
delete an instance
Definition: pal.cpp:154
struct pal::_filterContext FilterContext
void init_sol_falp()
Definition: problem.cpp:307
LabelPosition ** lPos
Definition: util.h:61
Units getMapUnit()
get current map unit
Definition: pal.cpp:946
Summury of problem.
Definition: palstat.h:40
LabelPosition is a candidate feature label position.
Definition: labelposition.h:50
SearchMethod getSearch()
get the search method in use
Definition: pal.cpp:898
std::list< LabelPosition * > * labeller(double scale, double bbox[4], PalStat **stats, bool displayAll)
the labeling machine Will extract all active layers
Definition: pal.cpp:612
Pal()
Create an new pal instance.
Definition: pal.cpp:84
Represent a problem.
Definition: problem.h:92
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:805
void reduce()
Definition: problem.cpp:152
int getPolyP()
get maximum # candidates to generate for polygon features
Definition: pal.cpp:873
enum _Units Units
Typedef for _Units enumeration.
Definition: pal.h:72
int nblp
Definition: util.h:60
struct pal::_featCbackCtx FeatCallBackCtx
is a little bit better than CHAIN but slower
Definition: pal.h:79
int getDpi()
get map resolution
Definition: pal.cpp:888
is the worst but fastest method
Definition: pal.h:77
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:748
void geosError(const char *fmt,...)
Definition: pal.cpp:63