QGIS API Documentation  3.8.0-Zanzibar (11aff65)
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 = new double[nbPoints];
62  y = new double[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:135
void invalidateGeos()
Definition: pointset.cpp:179
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:242
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.
void createGeosGeom() const
Definition: pointset.cpp:125
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:2815
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 * x
Definition: pointset.h:169
double ymax
Definition: pointset.h:192
double xmin
Definition: pointset.h:189
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:191
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)...
double * y
Definition: pointset.h:170
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:165
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:167
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:190
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:693
bool isCurved() const
Returns true if the layer has curved labels.
Definition: layer.h:107
bool showUprightLabels() const
Returns true if feature&#39;s label must be displayed upright.
Definition: feature.cpp:1744
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.