QGIS API Documentation  2.17.0-Master (6f7b933)
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 &&
103  this->alpha > M_PI / 2 && this->alpha <= 3*M_PI / 2 )
104  {
105  bool uprightLabel = false;
106 
107  switch ( feature->layer()->upsidedownLabels() )
108  {
109  case Layer::Upright:
110  uprightLabel = true;
111  break;
112  case Layer::ShowDefined:
113  // upright only dynamic labels
114  if ( !feature->getFixedRotation() || ( !feature->getFixedPosition() && feature->getLabelAngle() == 0.0 ) )
115  {
116  uprightLabel = true;
117  }
118  break;
119  case Layer::ShowAll:
120  break;
121  default:
122  uprightLabel = true;
123  }
124 
125  if ( uprightLabel )
126  {
127  tx = x[0];
128  ty = y[0];
129 
130  x[0] = x[2];
131  y[0] = y[2];
132 
133  x[2] = tx;
134  y[2] = ty;
135 
136  tx = x[1];
137  ty = y[1];
138 
139  x[1] = x[3];
140  y[1] = y[3];
141 
142  x[3] = tx;
143  y[3] = ty;
144 
145  if ( this->alpha < M_PI )
146  this->alpha += M_PI;
147  else
148  this->alpha -= M_PI;
149 
150  // labels with text shown upside down are not classified as upsideDown,
151  // only those whose boundary points have been inverted
152  upsideDown = true;
153  }
154  }
155 
156  for ( int i = 0; i < nbPoints; ++i )
157  {
158  xmin = qMin( xmin, x[i] );
159  xmax = qMax( xmax, x[i] );
160  ymin = qMin( ymin, y[i] );
161  ymax = qMax( ymax, y[i] );
162  }
163 }
164 
166  : PointSet( other )
167 {
168  id = other.id;
169  mCost = other.mCost;
170  feature = other.feature;
171  probFeat = other.probFeat;
172  nbOverlap = other.nbOverlap;
173 
174  alpha = other.alpha;
175  w = other.w;
176  h = other.h;
177 
178  if ( other.nextPart )
179  nextPart = new LabelPosition( *other.nextPart );
180  else
181  nextPart = nullptr;
182  partId = other.partId;
183  upsideDown = other.upsideDown;
184  reversed = other.reversed;
185  quadrant = other.quadrant;
186  mHasObstacleConflict = other.mHasObstacleConflict;
187 }
188 
189 bool LabelPosition::isIn( double *bbox )
190 {
191  int i;
192 
193  for ( i = 0; i < 4; i++ )
194  {
195  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
196  y[i] >= bbox[1] && y[i] <= bbox[3] )
197  return true;
198  }
199 
200  if ( nextPart )
201  return nextPart->isIn( bbox );
202  else
203  return false;
204 }
205 
206 bool LabelPosition::isIntersect( double *bbox )
207 {
208  int i;
209 
210  for ( i = 0; i < 4; i++ )
211  {
212  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
213  y[i] >= bbox[1] && y[i] <= bbox[3] )
214  return true;
215  }
216 
217  if ( nextPart )
218  return nextPart->isIntersect( bbox );
219  else
220  return false;
221 }
222 
223 bool LabelPosition::isInside( double *bbox )
224 {
225  for ( int i = 0; i < 4; i++ )
226  {
227  if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
228  y[i] >= bbox[1] && y[i] <= bbox[3] ) )
229  return false;
230  }
231 
232  if ( nextPart )
233  return nextPart->isInside( bbox );
234  else
235  return true;
236 }
237 
239 {
240  if ( this->probFeat == lp->probFeat ) // bugfix #1
241  return false; // always overlaping itself !
242 
243  if ( !nextPart && !lp->nextPart )
244  return isInConflictSinglePart( lp );
245  else
246  return isInConflictMultiPart( lp );
247 }
248 
250 {
251  if ( !mGeos )
252  createGeosGeom();
253 
254  if ( !lp->mGeos )
255  lp->createGeosGeom();
256 
257  GEOSContextHandle_t geosctxt = geosContext();
258  try
259  {
260  bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
261  return result;
262  }
263  catch ( GEOSException &e )
264  {
265  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
266  return false;
267  }
268 }
269 
271 {
272  // check all parts against all parts of other one
273  LabelPosition* tmp1 = this;
274  while ( tmp1 )
275  {
276  // check tmp1 against parts of other label
277  LabelPosition* tmp2 = lp;
278  while ( tmp2 )
279  {
280  if ( tmp1->isInConflictSinglePart( tmp2 ) )
281  return true;
282  tmp2 = tmp2->nextPart;
283  }
284 
285  tmp1 = tmp1->nextPart;
286  }
287  return false; // no conflict found
288 }
289 
290 int LabelPosition::partCount() const
291 {
292  if ( nextPart )
293  return nextPart->partCount() + 1;
294  else
295  return 1;
296 }
297 
298 void LabelPosition::offsetPosition( double xOffset, double yOffset )
299 {
300  for ( int i = 0; i < 4; i++ )
301  {
302  x[i] += xOffset;
303  y[i] += yOffset;
304  }
305 
306  if ( nextPart )
307  nextPart->offsetPosition( xOffset, yOffset );
308 
309  invalidateGeos();
310 }
311 
313 {
314  return id;
315 }
316 
317 double LabelPosition::getX( int i ) const
318 {
319  return ( i >= 0 && i < 4 ? x[i] : -1 );
320 }
321 
322 double LabelPosition::getY( int i ) const
323 {
324  return ( i >= 0 && i < 4 ? y[i] : -1 );
325 }
326 
328 {
329  return alpha;
330 }
331 
333 {
334  if ( mCost >= 1 )
335  {
336  mCost -= int ( mCost ); // label cost up to 1
337  }
338 }
339 
341 {
342  return feature;
343 }
344 
345 void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
346 {
347  if ( nextPart )
348  {
349  nextPart->getBoundingBox( amin, amax );
350  }
351  else
352  {
353  amin[0] = DBL_MAX;
354  amax[0] = -DBL_MAX;
355  amin[1] = DBL_MAX;
356  amax[1] = -DBL_MAX;
357  }
358  for ( int c = 0; c < 4; c++ )
359  {
360  if ( x[c] < amin[0] )
361  amin[0] = x[c];
362  if ( x[c] > amax[0] )
363  amax[0] = x[c];
364  if ( y[c] < amin[1] )
365  amin[1] = y[c];
366  if ( y[c] > amax[1] )
367  amax[1] = y[c];
368  }
369 }
370 
372 {
373  mHasObstacleConflict = conflicts;
374  if ( nextPart )
375  nextPart->setConflictsWithObstacle( conflicts );
376 }
377 
379 {
380  PolygonCostCalculator *pCost = reinterpret_cast< PolygonCostCalculator* >( ctx );
381 
382  LabelPosition *lp = pCost->getLabel();
383  if (( obstacle == lp->feature ) || ( obstacle->getHoleOf() && obstacle->getHoleOf() != lp->feature ) )
384  {
385  return true;
386  }
387 
388  pCost->update( obstacle );
389 
390  return true;
391 }
392 
393 void LabelPosition::removeFromIndex( RTree<LabelPosition*, double, 2, double> *index )
394 {
395  double amin[2];
396  double amax[2];
397  getBoundingBox( amin, amax );
398  index->Remove( amin, amax, this );
399 }
400 
401 void LabelPosition::insertIntoIndex( RTree<LabelPosition*, double, 2, double> *index )
402 {
403  double amin[2];
404  double amax[2];
405  getBoundingBox( amin, amax );
406  index->Insert( amin, amax, this );
407 }
408 
409 bool LabelPosition::pruneCallback( LabelPosition *candidatePosition, void *ctx )
410 {
411  FeaturePart *obstaclePart = ( reinterpret_cast< PruneCtx* >( ctx ) )->obstacle;
412 
413  // test whether we should ignore this obstacle for the candidate. We do this if:
414  // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (eg
415  // features aren't obstacles for their own labels)
416  // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (eg, holes
417  // are ONLY obstacles for the labels of the feature they belong to)
418  if (( !obstaclePart->getHoleOf() && candidatePosition->feature->hasSameLabelFeatureAs( obstaclePart ) )
419  || ( obstaclePart->getHoleOf() && !candidatePosition->feature->hasSameLabelFeatureAs( dynamic_cast< FeaturePart* >( obstaclePart->getHoleOf() ) ) ) )
420  {
421  return true;
422  }
423 
424  CostCalculator::addObstacleCostPenalty( candidatePosition, obstaclePart );
425 
426  return true;
427 }
428 
430 {
431  LabelPosition *lp2 = reinterpret_cast< LabelPosition* >( ctx );
432 
433  if ( lp2->isInConflict( lp ) )
434  {
435  lp2->nbOverlap++;
436  }
437 
438  return true;
439 }
440 
442 {
443  CountContext* context = reinterpret_cast< CountContext* >( ctx );
444  LabelPosition *lp2 = context->lp;
445  double *cost = context->cost;
446  int *nbOv = context->nbOv;
447  double *inactiveCost = context->inactiveCost;
448  if ( lp2->isInConflict( lp ) )
449  {
450  ( *nbOv ) ++;
451  *cost += inactiveCost[lp->probFeat] + lp->cost();
452  }
453 
454  return true;
455 }
456 
458 {
459  LabelPosition *lp2 = reinterpret_cast< LabelPosition * >( ctx );
460 
461  if ( lp2->isInConflict( lp ) )
462  {
463  lp->nbOverlap--;
464  lp2->nbOverlap--;
465  }
466 
467  return true;
468 }
469 
470 double LabelPosition::getDistanceToPoint( double xp, double yp ) const
471 {
472  //first check if inside, if so then distance is -1
473  double distance = ( containsPoint( xp, yp ) ? -1
474  : sqrt( minDistanceToPoint( xp, yp ) ) );
475 
476  if ( nextPart && distance > 0 )
477  return qMin( distance, nextPart->getDistanceToPoint( xp, yp ) );
478 
479  return distance;
480 }
481 
483 {
484  if ( !mGeos )
485  createGeosGeom();
486 
487  if ( !line->mGeos )
488  line->createGeosGeom();
489 
490  GEOSContextHandle_t geosctxt = geosContext();
491  try
492  {
493  if ( GEOSPreparedIntersects_r( geosctxt, line->preparedGeom(), mGeos ) == 1 )
494  {
495  return true;
496  }
497  else if ( nextPart )
498  {
499  return nextPart->crossesLine( line );
500  }
501  }
502  catch ( GEOSException &e )
503  {
504  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
505  return false;
506  }
507 
508  return false;
509 }
510 
512 {
513  if ( !mGeos )
514  createGeosGeom();
515 
516  if ( !polygon->mGeos )
517  polygon->createGeosGeom();
518 
519  GEOSContextHandle_t geosctxt = geosContext();
520  try
521  {
522  if ( GEOSPreparedOverlaps_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1
523  || GEOSPreparedTouches_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
524  {
525  return true;
526  }
527  else if ( nextPart )
528  {
529  return nextPart->crossesBoundary( polygon );
530  }
531  }
532  catch ( GEOSException &e )
533  {
534  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
535  return false;
536  }
537 
538  return false;
539 }
540 
542 {
543  //effectively take the average polygon intersection cost for all label parts
544  double totalCost = polygonIntersectionCostForParts( polygon );
545  int n = partCount();
546  return ceil( totalCost / n );
547 }
548 
550 {
551  if ( !mGeos )
552  createGeosGeom();
553 
554  if ( !polygon->mGeos )
555  polygon->createGeosGeom();
556 
557  GEOSContextHandle_t geosctxt = geosContext();
558  try
559  {
560  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
561  {
562  return true;
563  }
564  }
565  catch ( GEOSException &e )
566  {
567  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
568  }
569 
570  if ( nextPart )
571  {
572  return nextPart->intersectsWithPolygon( polygon );
573  }
574  else
575  {
576  return false;
577  }
578 }
579 
580 double LabelPosition::polygonIntersectionCostForParts( PointSet *polygon ) const
581 {
582  if ( !mGeos )
583  createGeosGeom();
584 
585  if ( !polygon->mGeos )
586  polygon->createGeosGeom();
587 
588  GEOSContextHandle_t geosctxt = geosContext();
589  double cost = 0;
590  try
591  {
592  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
593  {
594  //at least a partial intersection
595  cost += 1;
596 
597  double px, py;
598 
599  // check each corner
600  for ( int i = 0; i < 4; ++i )
601  {
602  px = x[i];
603  py = y[i];
604 
605  for ( int a = 0; a < 2; ++a ) // and each middle of segment
606  {
607  if ( polygon->containsPoint( px, py ) )
608  cost++;
609  px = ( x[i] + x[( i+1 ) %4] ) / 2.0;
610  py = ( y[i] + y[( i+1 ) %4] ) / 2.0;
611  }
612  }
613 
614  px = ( x[0] + x[2] ) / 2.0;
615  py = ( y[0] + y[2] ) / 2.0;
616 
617  //check the label center. if covered by polygon, cost of 4
618  if ( polygon->containsPoint( px, py ) )
619  cost += 4;
620  }
621  }
622  catch ( GEOSException &e )
623  {
624  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
625  }
626 
627  //maintain scaling from 0 -> 12
628  cost = 12.0 * cost / 13.0;
629 
630  if ( nextPart )
631  {
632  cost += nextPart->polygonIntersectionCostForParts( polygon );
633  }
634 
635  return cost;
636 }
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:200
static unsigned index
PointSet * getHoleOf()
Returns NULL if this isn&#39;t a hole.
Definition: pointset.h:127
bool getFixedRotation()
Definition: feature.h:218
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:94
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:160
LabelPosition * nextPart
double * x
Definition: pointset.h:153
bool getFixedPosition()
Definition: feature.h:220
double ymax
Definition: pointset.h:176
double xmin
Definition: pointset.h:173
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
double ymin
Definition: pointset.h:175
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:150
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:91
double getLabelAngle()
Definition: feature.h:219
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:154
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:149
LabelPosition is a candidate feature label position.
Definition: labelposition.h:51
Quadrant
Position of label candidate relative to feature.
Definition: labelposition.h:61
bool isInConflictSinglePart(LabelPosition *lp)
double xmax
Definition: pointset.h:174
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:720
Data structure to compute polygon&#39;s candidates costs.
LabelPosition::Quadrant quadrant