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