QGIS API Documentation  2.17.0-Master (0497e4a)
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
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 containsPoint(double x, double y) const
Tests whether point set contains a specified point.
Definition: pointset.cpp:268
bool isInConflictMultiPart(LabelPosition *lp)
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
bool intersectsWithPolygon(PointSet *polygon) const
Returns true if if any intersection between polygon and position exists.
double getY(int i=0) const
get the down-left y coordinate
void offsetPosition(double xOffset, double yOffset)
Shift the label by specified offset.
void createGeosGeom() const
Definition: pointset.cpp:150
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
UpsideDownLabels upsidedownLabels() const
Returns how upside down labels are handled within the layer.
Definition: layer.h:200
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 ?
static void addObstacleCostPenalty(LabelPosition *lp, pal::FeaturePart *obstacle)
Increase candidate&#39;s cost according to its collision with passed feature.
double cost() const
Returns the candidate label position&#39;s geographical cost.
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
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
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
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:94
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
void validateCost()
Make sure the cost is less than 1.
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
Definition: pal.cpp:48
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.
int getId() const
return id
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center)...
double * y
Definition: pointset.h:154
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 hasSameLabelFeatureAs(FeaturePart *part) const
Tests whether this feature part belongs to the same QgsLabelFeature as another feature part...
Definition: feature.cpp:160
double getAlpha() const
get alpha
double getX(int i=0) const
get the down-left x coordinate
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
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:192
bool isInConflictSinglePart(LabelPosition *lp)
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
double xmax
Definition: pointset.h:174
Data structure to compute polygon&#39;s candidates costs.
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
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
LabelPosition::Quadrant quadrant
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point.