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