QGIS API Documentation  2.99.0-Master (f1c3692)
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::isInside( double *bbox )
200 {
201  for ( int i = 0; i < 4; i++ )
202  {
203  if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
204  y[i] >= bbox[1] && y[i] <= bbox[3] ) )
205  return false;
206  }
207 
208  if ( nextPart )
209  return nextPart->isInside( bbox );
210  else
211  return true;
212 }
213 
215 {
216  if ( this->probFeat == lp->probFeat ) // bugfix #1
217  return false; // always overlaping itself !
218 
219  if ( !nextPart && !lp->nextPart )
220  return isInConflictSinglePart( lp );
221  else
222  return isInConflictMultiPart( lp );
223 }
224 
226 {
227  if ( !mGeos )
228  createGeosGeom();
229 
230  if ( !lp->mGeos )
231  lp->createGeosGeom();
232 
233  GEOSContextHandle_t geosctxt = geosContext();
234  try
235  {
236  bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
237  return result;
238  }
239  catch ( GEOSException &e )
240  {
241  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
242  return false;
243  }
244 }
245 
247 {
248  // check all parts against all parts of other one
249  LabelPosition *tmp1 = this;
250  while ( tmp1 )
251  {
252  // check tmp1 against parts of other label
253  LabelPosition *tmp2 = lp;
254  while ( tmp2 )
255  {
256  if ( tmp1->isInConflictSinglePart( tmp2 ) )
257  return true;
258  tmp2 = tmp2->nextPart;
259  }
260 
261  tmp1 = tmp1->nextPart;
262  }
263  return false; // no conflict found
264 }
265 
266 int LabelPosition::partCount() const
267 {
268  if ( nextPart )
269  return nextPart->partCount() + 1;
270  else
271  return 1;
272 }
273 
274 void LabelPosition::offsetPosition( double xOffset, double yOffset )
275 {
276  for ( int i = 0; i < 4; i++ )
277  {
278  x[i] += xOffset;
279  y[i] += yOffset;
280  }
281 
282  if ( nextPart )
283  nextPart->offsetPosition( xOffset, yOffset );
284 
285  invalidateGeos();
286 }
287 
289 {
290  return id;
291 }
292 
293 double LabelPosition::getX( int i ) const
294 {
295  return ( i >= 0 && i < 4 ? x[i] : -1 );
296 }
297 
298 double LabelPosition::getY( int i ) const
299 {
300  return ( i >= 0 && i < 4 ? y[i] : -1 );
301 }
302 
304 {
305  return alpha;
306 }
307 
309 {
310  if ( mCost >= 1 )
311  {
312  mCost -= int ( mCost ); // label cost up to 1
313  }
314 }
315 
317 {
318  return feature;
319 }
320 
321 void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
322 {
323  if ( nextPart )
324  {
325  nextPart->getBoundingBox( amin, amax );
326  }
327  else
328  {
329  amin[0] = DBL_MAX;
330  amax[0] = -DBL_MAX;
331  amin[1] = DBL_MAX;
332  amax[1] = -DBL_MAX;
333  }
334  for ( int c = 0; c < 4; c++ )
335  {
336  if ( x[c] < amin[0] )
337  amin[0] = x[c];
338  if ( x[c] > amax[0] )
339  amax[0] = x[c];
340  if ( y[c] < amin[1] )
341  amin[1] = y[c];
342  if ( y[c] > amax[1] )
343  amax[1] = y[c];
344  }
345 }
346 
348 {
349  mHasObstacleConflict = conflicts;
350  if ( nextPart )
351  nextPart->setConflictsWithObstacle( conflicts );
352 }
353 
355 {
356  PolygonCostCalculator *pCost = reinterpret_cast< PolygonCostCalculator * >( ctx );
357 
358  LabelPosition *lp = pCost->getLabel();
359  if ( ( obstacle == lp->feature ) || ( obstacle->getHoleOf() && obstacle->getHoleOf() != lp->feature ) )
360  {
361  return true;
362  }
363 
364  pCost->update( obstacle );
365 
366  return true;
367 }
368 
369 void LabelPosition::removeFromIndex( RTree<LabelPosition *, double, 2, double> *index )
370 {
371  double amin[2];
372  double amax[2];
373  getBoundingBox( amin, amax );
374  index->Remove( amin, amax, this );
375 }
376 
377 void LabelPosition::insertIntoIndex( RTree<LabelPosition *, double, 2, double> *index )
378 {
379  double amin[2];
380  double amax[2];
381  getBoundingBox( amin, amax );
382  index->Insert( amin, amax, this );
383 }
384 
385 bool LabelPosition::pruneCallback( LabelPosition *candidatePosition, void *ctx )
386 {
387  FeaturePart *obstaclePart = ( reinterpret_cast< PruneCtx * >( ctx ) )->obstacle;
388 
389  // test whether we should ignore this obstacle for the candidate. We do this if:
390  // 1. it's not a hole, and the obstacle belongs to the same label feature as the candidate (e.g.,
391  // features aren't obstacles for their own labels)
392  // 2. it IS a hole, and the hole belongs to a different label feature to the candidate (e.g., holes
393  // are ONLY obstacles for the labels of the feature they belong to)
394  if ( ( !obstaclePart->getHoleOf() && candidatePosition->feature->hasSameLabelFeatureAs( obstaclePart ) )
395  || ( obstaclePart->getHoleOf() && !candidatePosition->feature->hasSameLabelFeatureAs( dynamic_cast< FeaturePart * >( obstaclePart->getHoleOf() ) ) ) )
396  {
397  return true;
398  }
399 
400  CostCalculator::addObstacleCostPenalty( candidatePosition, obstaclePart );
401 
402  return true;
403 }
404 
406 {
407  LabelPosition *lp2 = reinterpret_cast< LabelPosition * >( ctx );
408 
409  if ( lp2->isInConflict( lp ) )
410  {
411  lp2->nbOverlap++;
412  }
413 
414  return true;
415 }
416 
418 {
419  CountContext *context = reinterpret_cast< CountContext * >( ctx );
420  LabelPosition *lp2 = context->lp;
421  double *cost = context->cost;
422  int *nbOv = context->nbOv;
423  double *inactiveCost = context->inactiveCost;
424  if ( lp2->isInConflict( lp ) )
425  {
426  ( *nbOv ) ++;
427  *cost += inactiveCost[lp->probFeat] + lp->cost();
428  }
429 
430  return true;
431 }
432 
434 {
435  LabelPosition *lp2 = reinterpret_cast< LabelPosition * >( ctx );
436 
437  if ( lp2->isInConflict( lp ) )
438  {
439  lp->nbOverlap--;
440  lp2->nbOverlap--;
441  }
442 
443  return true;
444 }
445 
446 double LabelPosition::getDistanceToPoint( double xp, double yp ) const
447 {
448  //first check if inside, if so then distance is -1
449  double distance = ( containsPoint( xp, yp ) ? -1
450  : std::sqrt( minDistanceToPoint( xp, yp ) ) );
451 
452  if ( nextPart && distance > 0 )
453  return std::min( distance, nextPart->getDistanceToPoint( xp, yp ) );
454 
455  return distance;
456 }
457 
459 {
460  if ( !mGeos )
461  createGeosGeom();
462 
463  if ( !line->mGeos )
464  line->createGeosGeom();
465 
466  GEOSContextHandle_t geosctxt = geosContext();
467  try
468  {
469  if ( GEOSPreparedIntersects_r( geosctxt, line->preparedGeom(), mGeos ) == 1 )
470  {
471  return true;
472  }
473  else if ( nextPart )
474  {
475  return nextPart->crossesLine( line );
476  }
477  }
478  catch ( GEOSException &e )
479  {
480  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
481  return false;
482  }
483 
484  return false;
485 }
486 
488 {
489  if ( !mGeos )
490  createGeosGeom();
491 
492  if ( !polygon->mGeos )
493  polygon->createGeosGeom();
494 
495  GEOSContextHandle_t geosctxt = geosContext();
496  try
497  {
498  if ( GEOSPreparedOverlaps_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1
499  || GEOSPreparedTouches_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
500  {
501  return true;
502  }
503  else if ( nextPart )
504  {
505  return nextPart->crossesBoundary( polygon );
506  }
507  }
508  catch ( GEOSException &e )
509  {
510  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
511  return false;
512  }
513 
514  return false;
515 }
516 
518 {
519  //effectively take the average polygon intersection cost for all label parts
520  double totalCost = polygonIntersectionCostForParts( polygon );
521  int n = partCount();
522  return std::ceil( totalCost / n );
523 }
524 
526 {
527  if ( !mGeos )
528  createGeosGeom();
529 
530  if ( !polygon->mGeos )
531  polygon->createGeosGeom();
532 
533  GEOSContextHandle_t geosctxt = geosContext();
534  try
535  {
536  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
537  {
538  return true;
539  }
540  }
541  catch ( GEOSException &e )
542  {
543  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
544  }
545 
546  if ( nextPart )
547  {
548  return nextPart->intersectsWithPolygon( polygon );
549  }
550  else
551  {
552  return false;
553  }
554 }
555 
556 double LabelPosition::polygonIntersectionCostForParts( PointSet *polygon ) const
557 {
558  if ( !mGeos )
559  createGeosGeom();
560 
561  if ( !polygon->mGeos )
562  polygon->createGeosGeom();
563 
564  GEOSContextHandle_t geosctxt = geosContext();
565  double cost = 0;
566  try
567  {
568  if ( GEOSPreparedIntersects_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
569  {
570  //at least a partial intersection
571  cost += 1;
572 
573  double px, py;
574 
575  // check each corner
576  for ( int i = 0; i < 4; ++i )
577  {
578  px = x[i];
579  py = y[i];
580 
581  for ( int a = 0; a < 2; ++a ) // and each middle of segment
582  {
583  if ( polygon->containsPoint( px, py ) )
584  cost++;
585  px = ( x[i] + x[( i + 1 ) % 4] ) / 2.0;
586  py = ( y[i] + y[( i + 1 ) % 4] ) / 2.0;
587  }
588  }
589 
590  px = ( x[0] + x[2] ) / 2.0;
591  py = ( y[0] + y[2] ) / 2.0;
592 
593  //check the label center. if covered by polygon, cost of 4
594  if ( polygon->containsPoint( px, py ) )
595  cost += 4;
596  }
597  }
598  catch ( GEOSException &e )
599  {
600  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
601  }
602 
603  //maintain scaling from 0 -> 12
604  cost = 12.0 * cost / 13.0;
605 
606  if ( nextPart )
607  {
608  cost += nextPart->polygonIntersectionCostForParts( polygon );
609  }
610 
611  return cost;
612 }
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: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:243
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:125
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:164
double ymax
Definition: pointset.h:187
double xmin
Definition: pointset.h:184
double ymin
Definition: pointset.h:186
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:96
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:165
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:160
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 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:185
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:694
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:1727
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.