QGIS API Documentation  2.15.0-Master (972fc9f)
labelposition.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 "layer.h"
31 #include "pal.h"
32 #include "costcalculator.h"
33 #include "feature.h"
34 #include "geomfunction.h"
35 #include "labelposition.h"
36 #include "qgsgeos.h"
37 #include "qgsmessagelog.h"
38 #include <cmath>
39 #include <cfloat>
40 
41 #ifndef M_PI
42 #define M_PI 3.1415926535897931159979634685
43 #endif
44 
45 using namespace pal;
46 
47 LabelPosition::LabelPosition( int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed, Quadrant quadrant )
48  : PointSet()
49  , id( id )
50  , feature( feature )
51  , probFeat( 0 )
52  , nbOverlap( 0 )
53  , alpha( alpha )
54  , w( w )
55  , h( h )
56  , nextPart( nullptr )
57  , partId( -1 )
58  , reversed( isReversed )
59  , upsideDown( false )
60  , quadrant( quadrant )
61  , mCost( cost )
62  , mHasObstacleConflict( false )
63 {
64  type = GEOS_POLYGON;
65  nbPoints = 4;
66  x = new double[nbPoints];
67  y = new double[nbPoints];
68 
69  // alpha take his value bw 0 and 2*pi rad
70  while ( this->alpha > 2*M_PI )
71  this->alpha -= 2 * M_PI;
72 
73  while ( this->alpha < 0 )
74  this->alpha += 2 * M_PI;
75 
76  double beta = this->alpha + ( M_PI / 2 );
77 
78  double dx1, dx2, dy1, dy2;
79 
80  double tx, ty;
81 
82  dx1 = cos( this->alpha ) * w;
83  dy1 = sin( this->alpha ) * w;
84 
85  dx2 = cos( beta ) * h;
86  dy2 = sin( beta ) * h;
87 
88  x[0] = x1;
89  y[0] = y1;
90 
91  x[1] = x1 + dx1;
92  y[1] = y1 + dy1;
93 
94  x[2] = x1 + dx1 + dx2;
95  y[2] = y1 + dy1 + dy2;
96 
97  x[3] = x1 + dx2;
98  y[3] = y1 + dy2;
99 
100  // upside down ? (curved labels are always correct)
101  if ( feature->layer()->arrangement() != QgsPalLayerSettings::Curved &&
102  this->alpha > M_PI / 2 && this->alpha <= 3*M_PI / 2 )
103  {
104  bool uprightLabel = false;
105 
106  switch ( feature->layer()->upsidedownLabels() )
107  {
108  case Layer::Upright:
109  uprightLabel = true;
110  break;
111  case Layer::ShowDefined:
112  // upright only dynamic labels
113  if ( !feature->getFixedRotation() || ( !feature->getFixedPosition() && feature->getLabelAngle() == 0.0 ) )
114  {
115  uprightLabel = true;
116  }
117  break;
118  case Layer::ShowAll:
119  break;
120  default:
121  uprightLabel = true;
122  }
123 
124  if ( uprightLabel )
125  {
126  tx = x[0];
127  ty = y[0];
128 
129  x[0] = x[2];
130  y[0] = y[2];
131 
132  x[2] = tx;
133  y[2] = ty;
134 
135  tx = x[1];
136  ty = y[1];
137 
138  x[1] = x[3];
139  y[1] = y[3];
140 
141  x[3] = tx;
142  y[3] = ty;
143 
144  if ( this->alpha < M_PI )
145  this->alpha += M_PI;
146  else
147  this->alpha -= M_PI;
148 
149  // labels with text shown upside down are not classified as upsideDown,
150  // only those whose boundary points have been inverted
151  upsideDown = true;
152  }
153  }
154 
155  for ( int i = 0; i < nbPoints; ++i )
156  {
157  xmin = qMin( xmin, x[i] );
158  xmax = qMax( xmax, x[i] );
159  ymin = qMin( ymin, y[i] );
160  ymax = qMax( ymax, y[i] );
161  }
162 }
163 
165  : PointSet( other )
166 {
167  id = other.id;
168  mCost = other.mCost;
169  feature = other.feature;
170  probFeat = other.probFeat;
171  nbOverlap = other.nbOverlap;
172 
173  alpha = other.alpha;
174  w = other.w;
175  h = other.h;
176 
177  if ( other.nextPart )
178  nextPart = new LabelPosition( *other.nextPart );
179  else
180  nextPart = nullptr;
181  partId = other.partId;
182  upsideDown = other.upsideDown;
183  reversed = other.reversed;
184  quadrant = other.quadrant;
185  mHasObstacleConflict = other.mHasObstacleConflict;
186 }
187 
188 bool LabelPosition::isIn( double *bbox )
189 {
190  int i;
191 
192  for ( i = 0; i < 4; i++ )
193  {
194  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
195  y[i] >= bbox[1] && y[i] <= bbox[3] )
196  return true;
197  }
198 
199  if ( nextPart )
200  return nextPart->isIn( bbox );
201  else
202  return false;
203 }
204 
205 bool LabelPosition::isIntersect( double *bbox )
206 {
207  int i;
208 
209  for ( i = 0; i < 4; i++ )
210  {
211  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
212  y[i] >= bbox[1] && y[i] <= bbox[3] )
213  return true;
214  }
215 
216  if ( nextPart )
217  return nextPart->isIntersect( bbox );
218  else
219  return false;
220 }
221 
222 bool LabelPosition::isInside( double *bbox )
223 {
224  for ( int i = 0; i < 4; i++ )
225  {
226  if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
227  y[i] >= bbox[1] && y[i] <= bbox[3] ) )
228  return false;
229  }
230 
231  if ( nextPart )
232  return nextPart->isInside( bbox );
233  else
234  return true;
235 }
236 
238 {
239  if ( this->probFeat == lp->probFeat ) // bugfix #1
240  return false; // always overlaping itself !
241 
242  if ( !nextPart && !lp->nextPart )
243  return isInConflictSinglePart( lp );
244  else
245  return isInConflictMultiPart( lp );
246 }
247 
249 {
250  if ( !mGeos )
251  createGeosGeom();
252 
253  if ( !lp->mGeos )
254  lp->createGeosGeom();
255 
256  GEOSContextHandle_t geosctxt = geosContext();
257  try
258  {
259  bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
260  return result;
261  }
262  catch ( GEOSException &e )
263  {
264  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
265  return false;
266  }
267 }
268 
270 {
271  // check all parts against all parts of other one
272  LabelPosition* tmp1 = this;
273  while ( tmp1 )
274  {
275  // check tmp1 against parts of other label
276  LabelPosition* tmp2 = lp;
277  while ( tmp2 )
278  {
279  if ( tmp1->isInConflictSinglePart( tmp2 ) )
280  return true;
281  tmp2 = tmp2->nextPart;
282  }
283 
284  tmp1 = tmp1->nextPart;
285  }
286  return false; // no conflict found
287 }
288 
289 int LabelPosition::partCount() const
290 {
291  if ( nextPart )
292  return nextPart->partCount() + 1;
293  else
294  return 1;
295 }
296 
297 void LabelPosition::offsetPosition( double xOffset, double yOffset )
298 {
299  for ( int i = 0; i < 4; i++ )
300  {
301  x[i] += xOffset;
302  y[i] += yOffset;
303  }
304 
305  if ( nextPart )
306  nextPart->offsetPosition( xOffset, yOffset );
307 
308  invalidateGeos();
309 }
310 
312 {
313  return id;
314 }
315 
316 double LabelPosition::getX( int i ) const
317 {
318  return ( i >= 0 && i < 4 ? x[i] : -1 );
319 }
320 
321 double LabelPosition::getY( int i ) const
322 {
323  return ( i >= 0 && i < 4 ? y[i] : -1 );
324 }
325 
327 {
328  return alpha;
329 }
330 
332 {
333  if ( mCost >= 1 )
334  {
335  mCost -= int ( mCost ); // label cost up to 1
336  }
337 }
338 
340 {
341  return feature;
342 }
343 
344 void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
345 {
346  if ( nextPart )
347  {
348  nextPart->getBoundingBox( amin, amax );
349  }
350  else
351  {
352  amin[0] = DBL_MAX;
353  amax[0] = -DBL_MAX;
354  amin[1] = DBL_MAX;
355  amax[1] = -DBL_MAX;
356  }
357  for ( int c = 0; c < 4; c++ )
358  {
359  if ( x[c] < amin[0] )
360  amin[0] = x[c];
361  if ( x[c] > amax[0] )
362  amax[0] = x[c];
363  if ( y[c] < amin[1] )
364  amin[1] = y[c];
365  if ( y[c] > amax[1] )
366  amax[1] = y[c];
367  }
368 }
369 
371 {
372  mHasObstacleConflict = conflicts;
373  if ( nextPart )
374  nextPart->setConflictsWithObstacle( conflicts );
375 }
376 
378 {
379  PolygonCostCalculator *pCost = reinterpret_cast< PolygonCostCalculator* >( ctx );
380 
381  LabelPosition *lp = pCost->getLabel();
382  if (( obstacle == lp->feature ) || ( obstacle->getHoleOf() && obstacle->getHoleOf() != lp->feature ) )
383  {
384  return true;
385  }
386 
387  pCost->update( obstacle );
388 
389  return true;
390 }
391 
393 {
394  double amin[2];
395  double amax[2];
396  getBoundingBox( amin, amax );
397  index->Remove( amin, amax, this );
398 }
399 
401 {
402  double amin[2];
403  double amax[2];
404  getBoundingBox( amin, amax );
405  index->Insert( amin, amax, this );
406 }
407 
408 bool LabelPosition::pruneCallback( LabelPosition *candidatePosition, void *ctx )
409 {
410  FeaturePart *obstaclePart = ( reinterpret_cast< PruneCtx* >( ctx ) )->obstacle;
411 
412  // test whether we should ignore this obstacle for the candidate. We do this if:
413  // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (eg
414  // features aren't obstacles for their own labels)
415  // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (eg, holes
416  // are ONLY obstacles for the labels of the feature they belong to)
417  if (( !obstaclePart->getHoleOf() && candidatePosition->feature->hasSameLabelFeatureAs( obstaclePart ) )
418  || ( obstaclePart->getHoleOf() && !candidatePosition->feature->hasSameLabelFeatureAs( dynamic_cast< FeaturePart* >( obstaclePart->getHoleOf() ) ) ) )
419  {
420  return true;
421  }
422 
423  CostCalculator::addObstacleCostPenalty( candidatePosition, obstaclePart );
424 
425  return true;
426 }
427 
429 {
430  LabelPosition *lp2 = reinterpret_cast< LabelPosition* >( ctx );
431 
432  if ( lp2->isInConflict( lp ) )
433  {
434  lp2->nbOverlap++;
435  }
436 
437  return true;
438 }
439 
441 {
442  CountContext* context = reinterpret_cast< CountContext* >( ctx );
443  LabelPosition *lp2 = context->lp;
444  double *cost = context->cost;
445  int *nbOv = context->nbOv;
446  double *inactiveCost = context->inactiveCost;
447  if ( lp2->isInConflict( lp ) )
448  {
449  ( *nbOv ) ++;
450  *cost += inactiveCost[lp->probFeat] + lp->cost();
451  }
452 
453  return true;
454 }
455 
457 {
458  LabelPosition *lp2 = reinterpret_cast< LabelPosition * >( ctx );
459 
460  if ( lp2->isInConflict( lp ) )
461  {
462  lp->nbOverlap--;
463  lp2->nbOverlap--;
464  }
465 
466  return true;
467 }
468 
469 double LabelPosition::getDistanceToPoint( double xp, double yp ) const
470 {
471  //first check if inside, if so then distance is -1
472  double distance = ( containsPoint( xp, yp ) ? -1
473  : sqrt( minDistanceToPoint( xp, yp ) ) );
474 
475  if ( nextPart && distance > 0 )
476  return qMin( distance, nextPart->getDistanceToPoint( xp, yp ) );
477 
478  return distance;
479 }
480 
482 {
483  if ( !mGeos )
484  createGeosGeom();
485 
486  if ( !line->mGeos )
487  line->createGeosGeom();
488 
489  GEOSContextHandle_t geosctxt = geosContext();
490  try
491  {
492  if ( GEOSPreparedIntersects_r( geosctxt, line->preparedGeom(), mGeos ) == 1 )
493  {
494  return true;
495  }
496  else if ( nextPart )
497  {
498  return nextPart->crossesLine( line );
499  }
500  }
501  catch ( GEOSException &e )
502  {
503  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
504  return false;
505  }
506 
507  return false;
508 }
509 
511 {
512  if ( !mGeos )
513  createGeosGeom();
514 
515  if ( !polygon->mGeos )
516  polygon->createGeosGeom();
517 
518  GEOSContextHandle_t geosctxt = geosContext();
519  try
520  {
521  if ( GEOSPreparedOverlaps_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1
522  || GEOSPreparedTouches_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
523  {
524  return true;
525  }
526  else if ( nextPart )
527  {
528  return nextPart->crossesBoundary( polygon );
529  }
530  }
531  catch ( GEOSException &e )
532  {
533  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
534  return false;
535  }
536 
537  return false;
538 }
539 
541 {
542  //effectively take the average polygon intersection cost for all label parts
543  double totalCost = polygonIntersectionCostForParts( polygon );
544  int n = partCount();
545  return ceil( totalCost / n );
546 }
547 
549 {
550  if ( !mGeos )
551  createGeosGeom();
552 
553  if ( !polygon->mGeos )
554  polygon->createGeosGeom();
555 
556  GEOSContextHandle_t geosctxt = geosContext();
557  try
558  {
559  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
560  {
561  return true;
562  }
563  }
564  catch ( GEOSException &e )
565  {
566  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
567  }
568 
569  if ( nextPart )
570  {
571  return nextPart->intersectsWithPolygon( polygon );
572  }
573  else
574  {
575  return false;
576  }
577 }
578 
579 double LabelPosition::polygonIntersectionCostForParts( PointSet *polygon ) const
580 {
581  if ( !mGeos )
582  createGeosGeom();
583 
584  if ( !polygon->mGeos )
585  polygon->createGeosGeom();
586 
587  GEOSContextHandle_t geosctxt = geosContext();
588  double cost = 0;
589  try
590  {
591  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
592  {
593  //at least a partial intersection
594  cost += 1;
595 
596  double px, py;
597 
598  // check each corner
599  for ( int i = 0; i < 4; ++i )
600  {
601  px = x[i];
602  py = y[i];
603 
604  for ( int a = 0; a < 2; ++a ) // and each middle of segment
605  {
606  if ( polygon->containsPoint( px, py ) )
607  cost++;
608  px = ( x[i] + x[( i+1 ) %4] ) / 2.0;
609  py = ( y[i] + y[( i+1 ) %4] ) / 2.0;
610  }
611  }
612 
613  px = ( x[0] + x[2] ) / 2.0;
614  py = ( y[0] + y[2] ) / 2.0;
615 
616  //check the label center. if covered by polygon, cost of 4
617  if ( polygon->containsPoint( px, py ) )
618  cost += 4;
619  }
620  }
621  catch ( GEOSException &e )
622  {
623  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
624  }
625 
626  //maintain scaling from 0 -> 12
627  cost = 12.0 * cost / 13.0;
628 
629  if ( nextPart )
630  {
631  cost += nextPart->polygonIntersectionCostForParts( polygon );
632  }
633 
634  return cost;
635 }
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
FeaturePart * feature
UpsideDownLabels upsidedownLabels() const
Returns how upside down labels are handled within the layer.
Definition: layer.h:197
static unsigned index
PointSet * getHoleOf()
Returns NULL if this isn&#39;t a hole.
Definition: pointset.h:126
bool getFixedRotation()
Definition: feature.h:201
void invalidateGeos()
Definition: pointset.cpp:204
bool isIntersect(double *bbox)
Is the labelposition intersect the bounding-box ?
bool isInConflictMultiPart(LabelPosition *lp)
void offsetPosition(double xOffset, double yOffset)
Shift the label by specified offset.
double cost() const
Returns the candidate label position&#39;s geographical cost.
void createGeosGeom() const
Definition: pointset.cpp:150
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
FeaturePart * getFeaturePart()
return the feature corresponding to this labelposition
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
QString tr(const char *sourceText, const char *disambiguation, int n)
void update(pal::PointSet *pset)
bool isInside(double *bbox)
Is the labelposition inside the bounding-box ?
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:91
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:192
static void addObstacleCostPenalty(LabelPosition *lp, pal::FeaturePart *obstacle)
Increase candidate&#39;s cost according to its collision with passed feature.
bool hasSameLabelFeatureAs(FeaturePart *part) const
Tests whether this feature part belongs to the same QgsLabelFeature as another feature part...
Definition: feature.cpp:159
LabelPosition * nextPart
double * x
Definition: pointset.h:152
bool getFixedPosition()
Definition: feature.h:203
double ymax
Definition: pointset.h:175
double xmin
Definition: pointset.h:172
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
double ymin
Definition: pointset.h:174
LabelPosition(int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed=false, Quadrant quadrant=QuadrantOver)
create a new LabelPosition
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point.
double getY(int i=0) const
get the down-left y coordinate
static void logMessage(const QString &message, const QString &tag=QString::null, MessageLevel level=WARNING)
add a message to the instance (and create it if necessary)
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:149
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center)...
void validateCost()
Make sure the cost is less than 1.
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
Definition: pal.cpp:48
double getX(int i=0) const
get the down-left x coordinate
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
Main class to handle feature.
Definition: feature.h:90
double getLabelAngle()
Definition: feature.h:202
static bool pruneCallback(LabelPosition *candidatePosition, void *ctx)
Check whether the candidate in ctx overlap with obstacle feat.
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
Definition: pointset.cpp:268
double * y
Definition: pointset.h:153
double getAlpha() const
get alpha
bool intersectsWithPolygon(PointSet *polygon) const
Returns true if if any intersection between polygon and position exists.
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
void setConflictsWithObstacle(bool conflicts)
Sets whether the position is marked as conflicting with an obstacle feature.
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
static bool polygonObstacleCallback(pal::FeaturePart *obstacle, void *ctx)
bool isIn(double *bbox)
Is the labelposition in the bounding-box ? (intersect or inside????)
#define M_PI
GEOSGeometry * mGeos
Definition: pointset.h:148
LabelPosition is a candidate feature label position.
Definition: labelposition.h:50
Quadrant
Position of label candidate relative to feature.
Definition: labelposition.h:60
bool isInConflictSinglePart(LabelPosition *lp)
double xmax
Definition: pointset.h:173
int getId() const
return id
double minDistanceToPoint(double px, double py, double *rx=nullptr, double *ry=nullptr) const
Returns the squared minimum distance between the point set geometry and the point (px...
Definition: pointset.cpp:763
Data structure to compute polygon&#39;s candidates costs.
LabelPosition::Quadrant quadrant