QGIS API Documentation  3.9.0-Master (224899f119)
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 #include "qgsgeometry.h"
31 #include "pal.h"
32 #include "layer.h"
33 #include "palexception.h"
34 #include "palstat.h"
35 #include "rtree.hpp"
36 #include "costcalculator.h"
37 #include "feature.h"
38 #include "geomfunction.h"
39 #include "labelposition.h"
40 #include "problem.h"
41 #include "pointset.h"
42 #include "internalexception.h"
43 #include "util.h"
44 #include <cfloat>
45 
46 using namespace pal;
47 
49 {
50  // do not init and exit GEOS - we do it inside QGIS
51  //initGEOS( geosNotice, geosError );
52 }
53 
54 void Pal::removeLayer( Layer *layer )
55 {
56  if ( !layer )
57  return;
58 
59  mMutex.lock();
60  if ( QgsAbstractLabelProvider *key = mLayers.key( layer, nullptr ) )
61  {
62  mLayers.remove( key );
63  delete layer;
64  }
65  mMutex.unlock();
66 }
67 
69 {
70 
71  mMutex.lock();
72 
73  qDeleteAll( mLayers );
74  mLayers.clear();
75  mMutex.unlock();
76 
77  // do not init and exit GEOS - we do it inside QGIS
78  //finishGEOS();
79 }
80 
81 Layer *Pal::addLayer( QgsAbstractLabelProvider *provider, const QString &layerName, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, bool displayAll )
82 {
83  mMutex.lock();
84 
85  Q_ASSERT( !mLayers.contains( provider ) );
86 
87  Layer *layer = new Layer( provider, layerName, arrangement, defaultPriority, active, toLabel, this, displayAll );
88  mLayers.insert( provider, layer );
89  mMutex.unlock();
90 
91  return layer;
92 }
93 
94 typedef struct _featCbackCtx
95 {
96  Layer *layer = nullptr;
97  QLinkedList<Feats *> *fFeats;
98  RTree<FeaturePart *, double, 2, double> *obstacles;
99  RTree<LabelPosition *, double, 2, double> *candidates;
100  QList<LabelPosition *> *positionsWithNoCandidates;
101  const GEOSPreparedGeometry *mapBoundary = nullptr;
103 
104 
105 
106 /*
107  * Callback function
108  *
109  * Extract a specific shape from indexes
110  */
111 bool extractFeatCallback( FeaturePart *ft_ptr, void *ctx )
112 {
113  double amin[2], amax[2];
114  FeatCallBackCtx *context = reinterpret_cast< FeatCallBackCtx * >( ctx );
115 
116  // Holes of the feature are obstacles
117  for ( int i = 0; i < ft_ptr->getNumSelfObstacles(); i++ )
118  {
119  ft_ptr->getSelfObstacle( i )->getBoundingBox( amin, amax );
120  context->obstacles->Insert( amin, amax, ft_ptr->getSelfObstacle( i ) );
121 
122  if ( !ft_ptr->getSelfObstacle( i )->getHoleOf() )
123  {
124  //ERROR: SHOULD HAVE A PARENT!!!!!
125  }
126  }
127 
128  // generate candidates for the feature part
129  const QList< LabelPosition * > lPos = ft_ptr->createCandidates( context->mapBoundary, ft_ptr, context->candidates );
130  if ( !lPos.empty() )
131  {
132  // valid features are added to fFeats
133  Feats *ft = new Feats();
134  ft->feature = ft_ptr;
135  ft->shape = nullptr;
136  ft->lPos = lPos;
137  ft->priority = ft_ptr->calculatePriority();
138  context->fFeats->append( ft );
139  }
140  else
141  {
142  // features with no candidates are recorded in the unlabeled feature list
143  std::unique_ptr< LabelPosition > unplacedPosition = ft_ptr->createCandidatePointOnSurface( ft_ptr );
144  if ( unplacedPosition )
145  context->positionsWithNoCandidates->append( unplacedPosition.release() );
146  }
147 
148  return true;
149 }
150 
151 typedef struct _obstaclebackCtx
152 {
153  RTree<FeaturePart *, double, 2, double> *obstacles;
156 
157 /*
158  * Callback function
159  *
160  * Extract obstacles from indexes
161  */
162 bool extractObstaclesCallback( FeaturePart *ft_ptr, void *ctx )
163 {
164  double amin[2], amax[2];
165  ObstacleCallBackCtx *context = reinterpret_cast< ObstacleCallBackCtx * >( ctx );
166 
167  // insert into obstacles
168  ft_ptr->getBoundingBox( amin, amax );
169  context->obstacles->Insert( amin, amax, ft_ptr );
170  context->obstacleCount++;
171  return true;
172 }
173 
174 typedef struct _filterContext
175 {
176  RTree<LabelPosition *, double, 2, double> *cdtsIndex;
177  Pal *pal = nullptr;
178 } FilterContext;
179 
180 bool filteringCallback( FeaturePart *featurePart, void *ctx )
181 {
182 
183  RTree<LabelPosition *, double, 2, double> *cdtsIndex = ( reinterpret_cast< FilterContext * >( ctx ) )->cdtsIndex;
184  Pal *pal = ( reinterpret_cast< FilterContext * >( ctx ) )->pal;
185 
186  if ( pal->isCanceled() )
187  return false; // do not continue searching
188 
189  double amin[2], amax[2];
190  featurePart->getBoundingBox( amin, amax );
191 
192  LabelPosition::PruneCtx pruneContext;
193  pruneContext.obstacle = featurePart;
194  pruneContext.pal = pal;
195  cdtsIndex->Search( amin, amax, LabelPosition::pruneCallback, static_cast< void * >( &pruneContext ) );
196 
197  return true;
198 }
199 
200 std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeometry &mapBoundary )
201 {
202  // to store obstacles
203  RTree<FeaturePart *, double, 2, double> obstacles;
204  std::unique_ptr< Problem > prob = qgis::make_unique< Problem >();
205 
206  int i, j;
207 
208  double bbx[4];
209  double bby[4];
210 
211  double amin[2];
212  double amax[2];
213 
214  int max_p = 0;
215 
216  LabelPosition *lp = nullptr;
217 
218  bbx[0] = bbx[3] = amin[0] = prob->bbox[0] = extent.xMinimum();
219  bby[0] = bby[1] = amin[1] = prob->bbox[1] = extent.yMinimum();
220  bbx[1] = bbx[2] = amax[0] = prob->bbox[2] = extent.xMaximum();
221  bby[2] = bby[3] = amax[1] = prob->bbox[3] = extent.yMaximum();
222 
223  prob->pal = this;
224 
225  QLinkedList<Feats *> fFeats;
226 
227  FeatCallBackCtx context;
228 
229  // prepare map boundary
230  geos::unique_ptr mapBoundaryGeos( QgsGeos::asGeos( mapBoundary ) );
231  geos::prepared_unique_ptr mapBoundaryPrepared( GEOSPrepare_r( QgsGeos::getGEOSHandler(), mapBoundaryGeos.get() ) );
232 
233  context.fFeats = &fFeats;
234  context.obstacles = &obstacles;
235  context.candidates = prob->candidates;
236  context.positionsWithNoCandidates = prob->positionsWithNoCandidates();
237  context.mapBoundary = mapBoundaryPrepared.get();
238 
239  ObstacleCallBackCtx obstacleContext;
240  obstacleContext.obstacles = &obstacles;
241  obstacleContext.obstacleCount = 0;
242 
243  // first step : extract features from layers
244 
245  int previousFeatureCount = 0;
246  int previousObstacleCount = 0;
247 
248  QStringList layersWithFeaturesInBBox;
249 
250  mMutex.lock();
251  const auto constMLayers = mLayers;
252  for ( Layer *layer : constMLayers )
253  {
254  if ( !layer )
255  {
256  // invalid layer name
257  continue;
258  }
259 
260  // only select those who are active
261  if ( !layer->active() )
262  continue;
263 
264  // check for connected features with the same label text and join them
265  if ( layer->mergeConnectedLines() )
266  layer->joinConnectedFeatures();
267 
268  layer->chopFeaturesAtRepeatDistance();
269 
270  layer->mMutex.lock();
271 
272  // find features within bounding box and generate candidates list
273  context.layer = layer;
274  layer->mFeatureIndex->Search( amin, amax, extractFeatCallback, static_cast< void * >( &context ) );
275  // find obstacles within bounding box
276  layer->mObstacleIndex->Search( amin, amax, extractObstaclesCallback, static_cast< void * >( &obstacleContext ) );
277 
278  layer->mMutex.unlock();
279 
280  if ( context.fFeats->size() - previousFeatureCount > 0 || obstacleContext.obstacleCount > previousObstacleCount )
281  {
282  layersWithFeaturesInBBox << layer->name();
283  }
284  previousFeatureCount = context.fFeats->size();
285  previousObstacleCount = obstacleContext.obstacleCount;
286  }
287  mMutex.unlock();
288 
289  prob->nbLabelledLayers = layersWithFeaturesInBBox.size();
290  prob->labelledLayersName = layersWithFeaturesInBBox;
291 
292  prob->nbft = fFeats.size();
293  prob->nblp = 0;
294  prob->featNbLp = new int [prob->nbft];
295  prob->featStartId = new int [prob->nbft];
296  prob->inactiveCost = new double[prob->nbft];
297 
298 
299  if ( !fFeats.isEmpty() )
300  {
301  Feats *feat = nullptr;
302 
303  // Filtering label positions against obstacles
304  amin[0] = amin[1] = std::numeric_limits<double>::lowest();
305  amax[0] = amax[1] = std::numeric_limits<double>::max();
306  FilterContext filterCtx;
307  filterCtx.cdtsIndex = prob->candidates;
308  filterCtx.pal = this;
309  obstacles.Search( amin, amax, filteringCallback, static_cast< void * >( &filterCtx ) );
310 
311  if ( isCanceled() )
312  {
313  for ( Feats *feat : qgis::as_const( fFeats ) )
314  {
315  qDeleteAll( feat->lPos );
316  feat->lPos.clear();
317  }
318 
319  qDeleteAll( fFeats );
320  return nullptr;
321  }
322 
323  int idlp = 0;
324  for ( i = 0; i < prob->nbft; i++ ) /* foreach feature into prob */
325  {
326  feat = fFeats.takeFirst();
327 
328  prob->featStartId[i] = idlp;
329  prob->inactiveCost[i] = std::pow( 2, 10 - 10 * feat->priority );
330 
331  switch ( feat->feature->getGeosType() )
332  {
333  case GEOS_POINT:
334  max_p = point_p;
335  break;
336  case GEOS_LINESTRING:
337  max_p = line_p;
338  break;
339  case GEOS_POLYGON:
340  max_p = poly_p;
341  break;
342  }
343 
344  // sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
345  max_p = CostCalculator::finalizeCandidatesCosts( feat, max_p, &obstacles, bbx, bby );
346 
347  // only keep the 'max_p' best candidates
348  while ( feat->lPos.count() > max_p )
349  {
350  // TODO remove from index
351  feat->lPos.constLast()->removeFromIndex( prob->candidates );
352  delete feat->lPos.takeLast();
353  }
354 
355  // update problem's # candidate
356  prob->featNbLp[i] = feat->lPos.count();
357  prob->nblp += feat->lPos.count();
358 
359  // add all candidates into a rtree (to speed up conflicts searching)
360  for ( j = 0; j < feat->lPos.count(); j++, idlp++ )
361  {
362  lp = feat->lPos.at( j );
363  //lp->insertIntoIndex(prob->candidates);
364  lp->setProblemIds( i, idlp ); // bugfix #1 (maxence 10/23/2008)
365  }
366  fFeats.append( feat );
367  }
368 
369  int nbOverlaps = 0;
370 
371  while ( !fFeats.isEmpty() ) // foreach feature
372  {
373  if ( isCanceled() )
374  {
375  for ( Feats *feat : qgis::as_const( fFeats ) )
376  {
377  qDeleteAll( feat->lPos );
378  feat->lPos.clear();
379  }
380 
381  qDeleteAll( fFeats );
382  return nullptr;
383  }
384 
385  feat = fFeats.takeFirst();
386  while ( !feat->lPos.isEmpty() ) // foreach label candidate
387  {
388  lp = feat->lPos.takeFirst();
389  lp->resetNumOverlaps();
390 
391  // make sure that candidate's cost is less than 1
392  lp->validateCost();
393 
394  prob->addCandidatePosition( lp );
395  //prob->feat[idlp] = j;
396 
397  lp->getBoundingBox( amin, amax );
398 
399  // lookup for overlapping candidate
400  prob->candidates->Search( amin, amax, LabelPosition::countOverlapCallback, static_cast< void * >( lp ) );
401 
402  nbOverlaps += lp->getNumOverlaps();
403  }
404  delete feat;
405  }
406  nbOverlaps /= 2;
407  prob->all_nblp = prob->nblp;
408  prob->nbOverlap = nbOverlaps;
409  }
410 
411  return prob;
412 }
413 
414 void Pal::registerCancellationCallback( Pal::FnIsCanceled fnCanceled, void *context )
415 {
416  fnIsCanceled = fnCanceled;
417  fnIsCanceledContext = context;
418 }
419 
420 std::unique_ptr<Problem> Pal::extractProblem( const QgsRectangle &extent, const QgsGeometry &mapBoundary )
421 {
422  return extract( extent, mapBoundary );
423 }
424 
425 QList<LabelPosition *> Pal::solveProblem( Problem *prob, bool displayAll, QList<LabelPosition *> *unlabeled )
426 {
427  if ( !prob )
428  return QList<LabelPosition *>();
429 
430  prob->reduce();
431 
432  try
433  {
434  prob->chain_search();
435  }
436  catch ( InternalException::Empty & )
437  {
438  return QList<LabelPosition *>();
439  }
440 
441  return prob->getSolution( displayAll, unlabeled );
442 }
443 
444 
445 void Pal::setPointP( int point_p )
446 {
447  if ( point_p > 0 )
448  this->point_p = point_p;
449 }
450 
451 void Pal::setLineP( int line_p )
452 {
453  if ( line_p > 0 )
454  this->line_p = line_p;
455 }
456 
457 void Pal::setPolyP( int poly_p )
458 {
459  if ( poly_p > 0 )
460  this->poly_p = poly_p;
461 }
462 
463 
464 void Pal::setMinIt( int min_it )
465 {
466  if ( min_it >= 0 )
467  tabuMinIt = min_it;
468 }
469 
470 void Pal::setMaxIt( int max_it )
471 {
472  if ( max_it > 0 )
473  tabuMaxIt = max_it;
474 }
475 
476 void Pal::setPopmusicR( int r )
477 {
478  if ( r > 0 )
479  popmusic_r = r;
480 }
481 
482 void Pal::setEjChainDeg( int degree )
483 {
484  this->ejChainDeg = degree;
485 }
486 
487 void Pal::setTenure( int tenure )
488 {
489  this->tenure = tenure;
490 }
491 
492 void Pal::setCandListSize( double fact )
493 {
494  this->candListSize = fact;
495 }
496 
497 void Pal::setShowPartial( bool show )
498 {
499  this->showPartial = show;
500 }
501 
503 {
504  return point_p;
505 }
506 
508 {
509  return line_p;
510 }
511 
513 {
514  return poly_p;
515 }
516 
517 int Pal::getMinIt()
518 {
519  return tabuMaxIt;
520 }
521 
522 int Pal::getMaxIt()
523 {
524  return tabuMinIt;
525 }
526 
528 {
529  return showPartial;
530 }
struct _obstaclebackCtx ObstacleCallBackCtx
Layer * addLayer(QgsAbstractLabelProvider *provider, const QString &layerName, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, bool displayAll=false)
add a new layer
Definition: pal.cpp:81
struct _filterContext FilterContext
A rectangle specified with double values.
Definition: qgsrectangle.h:41
Pal * pal
Definition: pal.cpp:177
PointSet * getHoleOf()
Returns nullptr if this isn&#39;t a hole. Otherwise returns pointer to parent pointset.
Definition: pointset.h:152
FeaturePart * feature
Definition: util.h:56
struct _featCbackCtx FeatCallBackCtx
void reduce()
Definition: problem.cpp:91
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
std::unique_ptr< const GEOSPreparedGeometry, GeosDeleter > prepared_unique_ptr
Scoped GEOS prepared geometry pointer.
Definition: qgsgeos.h:84
void registerCancellationCallback(FnIsCanceled fnCanceled, void *context)
Register a function that returns whether this job has been canceled - PAL calls it during the computa...
Definition: pal.cpp:414
A set of features which influence the labeling process.
Definition: layer.h:63
RTree< LabelPosition *, double, 2, double > * candidates
Definition: pal.cpp:99
Main Pal labeling class.
Definition: pal.h:87
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:121
int getNumSelfObstacles() const
Gets number of holes (inner rings) - they are considered as obstacles.
Definition: feature.h:299
void setShowPartial(bool show)
Set flag show partial label.
Definition: pal.cpp:497
const GEOSPreparedGeometry * mapBoundary
Definition: pal.cpp:101
int getPointP()
Returns the number of candidates to generate for point features.
Definition: pal.cpp:502
PointSet * shape
Definition: util.h:57
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2825
void removeLayer(Layer *layer)
remove a layer
Definition: pal.cpp:54
std::unique_ptr< Problem > extractProblem(const QgsRectangle &extent, const QgsGeometry &mapBoundary)
Extracts the labeling problem for the specified map extent - only features within this extent will be...
Definition: pal.cpp:420
RTree< FeaturePart *, double, 2, double, 8, 4 > * mFeatureIndex
Definition: layer.h:272
int getPolyP()
Returns the number of candidates to generate for polygon features.
Definition: pal.cpp:512
void chain_search()
Test with very-large scale neighborhood.
Definition: problem.cpp:725
bool(* FnIsCanceled)(void *ctx)
Definition: pal.h:129
std::unique_ptr< LabelPosition > createCandidatePointOnSurface(PointSet *mapShape)
Creates a single candidate using the "point on sruface" algorithm.
Definition: feature.cpp:313
bool getShowPartial()
Returns whether partial labels should be allowed.
Definition: pal.cpp:527
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:143
bool isCanceled()
Check whether the job has been canceled.
Definition: pal.h:135
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:79
double calculatePriority() const
Calculates the priority for the feature.
Definition: feature.cpp:1804
void setPointP(int point_p)
set # candidates to generate for points features Higher the value is, longer Pal::labeller will spend...
Definition: pal.cpp:445
void setLineP(int line_p)
set maximum # candidates to generate for lines features Higher the value is, longer Pal::labeller wil...
Definition: pal.cpp:451
static int finalizeCandidatesCosts(Feats *feat, int max_p, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
void validateCost()
Make sure the cost is less than 1.
QList< LabelPosition * > lPos
Definition: util.h:59
For usage in problem solving algorithm.
Definition: util.h:50
double priority
Definition: util.h:58
bool extractObstaclesCallback(FeaturePart *ft_ptr, void *ctx)
Definition: pal.cpp:162
Main class to handle feature.
Definition: feature.h:96
The QgsAbstractLabelProvider class is an interface class.
static bool pruneCallback(LabelPosition *candidatePosition, void *ctx)
Check whether the candidate in ctx overlap with obstacle feat.
QLinkedList< Feats * > * fFeats
Definition: pal.cpp:97
friend class Layer
Definition: pal.h:91
Pal()
Create an new pal instance.
Definition: pal.cpp:48
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:177
QList< LabelPosition * > createCandidates(const GEOSPreparedGeometry *mapBoundary, PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
Generic method to generate label candidates for the feature.
Definition: feature.cpp:1610
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:162
Placement
Placement modes which determine how label candidates are generated for a feature. ...
RTree< LabelPosition *, double, 2, double > * cdtsIndex
Definition: pal.cpp:176
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
static geos::unique_ptr asGeos(const QgsGeometry &geometry, double precision=0)
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
Definition: qgsgeos.cpp:166
void setPolyP(int poly_p)
set maximum # candidates to generate for polygon features Higher the value is, longer Pal::labeller w...
Definition: pal.cpp:457
int getNumOverlaps() const
RTree< FeaturePart *, double, 2, double > * obstacles
Definition: pal.cpp:98
FeaturePart * getSelfObstacle(int i)
Gets hole (inner ring) - considered as obstacle.
Definition: feature.h:301
int getGeosType() const
Definition: pointset.h:141
int obstacleCount
Definition: pal.cpp:154
bool filteringCallback(FeaturePart *featurePart, void *ctx)
Definition: pal.cpp:180
LabelPosition is a candidate feature label position.
Definition: labelposition.h:55
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:167
RTree< FeaturePart *, double, 2, double > * obstacles
Definition: pal.cpp:153
Representation of a labeling problem.
Definition: problem.h:73
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:172
~Pal()
Definition: pal.cpp:68
QList< LabelPosition * > solveProblem(Problem *prob, bool displayAll, QList< pal::LabelPosition *> *unlabeled=nullptr)
Solves the labeling problem, selecting the best candidate locations for all labels and returns a list...
Definition: pal.cpp:425
QList< LabelPosition * > getSolution(bool returnInactive, QList< LabelPosition *> *unlabeled=nullptr)
Solves the labeling problem, selecting the best candidate locations for all labels and returns a list...
Definition: problem.cpp:824
bool extractFeatCallback(FeaturePart *ft_ptr, void *ctx)
Definition: pal.cpp:111
void setProblemIds(int probFid, int lpId)
Set problem feature ID and assigned label candidate ID.
Thrown when trying to access an empty data set.
Layer * layer
Definition: pal.cpp:96
QList< LabelPosition * > * positionsWithNoCandidates
Definition: pal.cpp:100
int getLineP()
Returns the number of candidates to generate for line features.
Definition: pal.cpp:507