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