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