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