QGIS API Documentation  3.23.0-Master (eb871beae0)
costcalculator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  costcalculator.cpp
3  ---------------------
4  begin : November 2009
5  copyright : (C) 2009 by Martin Dobias
6  email : wonder dot sk at gmail dot com
7  ***************************************************************************
8  * *
9  * This program is free software; you can redistribute it and/or modify *
10  * it under the terms of the GNU General Public License as published by *
11  * the Free Software Foundation; either version 2 of the License, or *
12  * (at your option) any later version. *
13  * *
14  ***************************************************************************/
15 
16 #include "layer.h"
17 #include "pal.h"
18 #include "feature.h"
19 #include "geomfunction.h"
20 #include "labelposition.h"
21 #include "util.h"
22 #include "costcalculator.h"
23 #include <cmath>
24 #include <cfloat>
25 
26 using namespace pal;
27 
28 bool CostCalculator::candidateSortGrow( const std::unique_ptr< LabelPosition > &c1, const std::unique_ptr< LabelPosition > &c2 )
29 {
30  return c1->cost() < c2->cost();
31 }
32 
34 {
35  int n = 0;
36  double dist;
37  const double distlabel = lp->feature->getLabelDistance();
38 
39  switch ( obstacle->getGeosType() )
40  {
41  case GEOS_POINT:
42 
43  dist = lp->getDistanceToPoint( obstacle->x[0], obstacle->y[0] );
44  if ( dist < 0 )
45  n = 2;
46  else if ( dist < distlabel )
47  //note this never happens at the moment - points are not obstacles if they don't fall
48  //within the label
49  n = 1;
50  else
51  n = 0;
52  break;
53 
54  case GEOS_LINESTRING:
55 
56  // Is one of label's borders crossing the line ?
57  n = ( lp->crossesLine( obstacle ) ? 1 : 0 );
58  break;
59 
60  case GEOS_POLYGON:
61  // behavior depends on obstacle avoid type
62  switch ( obstacle->layer()->obstacleType() )
63  {
65  // n ranges from 0 -> 12
66  n = lp->polygonIntersectionCost( obstacle );
67  break;
69  // penalty may need tweaking, given that interior mode ranges up to 12
70  n = ( lp->crossesBoundary( obstacle ) ? 6 : 0 );
71  break;
73  // n is either 0 or 12
74  n = ( lp->intersectsWithPolygon( obstacle ) ? 12 : 0 );
75  break;
76  }
77 
78  break;
79  }
80 
81  //scale cost by obstacle's factor
82  const double obstacleCost = obstacle->obstacleSettings().factor() * double( n );
83  if ( n > 0 )
84  lp->setConflictsWithObstacle( true );
85 
86  switch ( pal->placementVersion() )
87  {
89  break;
90 
92  {
93  // obstacle factor is from 0 -> 2, label priority is from 1 -> 0. argh!
94  const double priority = 2 * ( 1 - lp->feature->calculatePriority() );
95  const double obstaclePriority = obstacle->obstacleSettings().factor();
96 
97  // if feature priority is < obstaclePriorty, there's a hard conflict...
98  if ( n > 0 && ( priority < obstaclePriority && !qgsDoubleNear( priority, obstaclePriority, 0.001 ) ) )
99  {
100  lp->setHasHardObstacleConflict( true );
101  }
102  break;
103  }
104  }
105 
106  // label cost is penalized
107  lp->setCost( lp->cost() + obstacleCost );
108 }
109 
110 void CostCalculator::calculateCandidatePolygonRingDistanceCosts( std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4] )
111 {
112  // first we calculate the ring distance cost for all candidates for this feature. We then use the range
113  // of distance costs to calculate a standardised scaling for the costs
114  QHash< LabelPosition *, double > polygonRingDistances;
115  double minCandidateRingDistance = std::numeric_limits< double >::max();
116  double maxCandidateRingDistance = std::numeric_limits< double >::lowest();
117  for ( const std::unique_ptr< LabelPosition > &pos : lPos )
118  {
119  const double candidatePolygonRingDistance = calculatePolygonRingDistance( pos.get(), bbx, bby );
120 
121  minCandidateRingDistance = std::min( minCandidateRingDistance, candidatePolygonRingDistance );
122  maxCandidateRingDistance = std::max( maxCandidateRingDistance, candidatePolygonRingDistance );
123 
124  polygonRingDistances.insert( pos.get(), candidatePolygonRingDistance );
125  }
126 
127  // define the cost's range, if range is too small, just ignore the ring distance cost
128  const double costRange = maxCandidateRingDistance - minCandidateRingDistance;
129  if ( costRange <= EPSILON )
130  return;
131 
132  const double normalizer = 0.0020 / costRange;
133 
134  // adjust cost => the best is 0, the worst is 0.002
135  // others are set proportionally between best and worst
136  for ( std::unique_ptr< LabelPosition > &pos : lPos )
137  {
138  const double polygonRingDistanceCost = polygonRingDistances.value( pos.get() );
139  pos->setCost( pos->cost() + 0.002 - ( polygonRingDistanceCost - minCandidateRingDistance ) * normalizer );
140  }
141 }
142 
143 void CostCalculator::calculateCandidatePolygonCentroidDistanceCosts( pal::FeaturePart *feature, std::vector<std::unique_ptr<LabelPosition> > &lPos )
144 {
145  double cx, cy;
146  feature->getCentroid( cx, cy );
147 
148  // first we calculate the centroid distance cost for all candidates for this feature. We then use the range
149  // of distance costs to calculate a standardised scaling for the costs
150  QHash< LabelPosition *, double > polygonCentroidDistances;
151  double minCandidateCentroidDistance = std::numeric_limits< double >::max();
152  double maxCandidateCentroidDistance = std::numeric_limits< double >::lowest();
153  for ( std::unique_ptr< LabelPosition > &pos : lPos )
154  {
155  const double lPosX = ( pos->x[0] + pos->x[2] ) / 2.0;
156  const double lPosY = ( pos->y[0] + pos->y[2] ) / 2.0;
157 
158  const double candidatePolygonCentroidDistance = std::sqrt( ( cx - lPosX ) * ( cx - lPosX ) + ( cy - lPosY ) * ( cy - lPosY ) );
159 
160  minCandidateCentroidDistance = std::min( minCandidateCentroidDistance, candidatePolygonCentroidDistance );
161  maxCandidateCentroidDistance = std::max( maxCandidateCentroidDistance, candidatePolygonCentroidDistance );
162 
163  polygonCentroidDistances.insert( pos.get(), candidatePolygonCentroidDistance );
164  }
165 
166  // define the cost's range, if range is too small, just ignore the ring distance cost
167  const double costRange = maxCandidateCentroidDistance - minCandidateCentroidDistance;
168  if ( costRange <= EPSILON )
169  return;
170 
171  const double normalizer = 0.001 / costRange;
172 
173  // adjust cost => the closest is 0, the furthest is 0.001
174  // others are set proportionally between best and worst
175  // NOTE: centroid cost range may need adjusting with respect to ring distance range!
176  for ( std::unique_ptr< LabelPosition > &pos : lPos )
177  {
178  const double polygonCentroidDistance = polygonCentroidDistances.value( pos.get() );
179  pos->setCost( pos->cost() + ( polygonCentroidDistance - minCandidateCentroidDistance ) * normalizer );
180  }
181 }
182 
183 double CostCalculator::calculatePolygonRingDistance( LabelPosition *candidate, double bbx[4], double bby[4] )
184 {
185  // TODO 1: Consider whether distance calculation should use min distance to the candidate rectangle
186  // instead of just the center
187  CandidatePolygonRingDistanceCalculator ringDistanceCalculator( candidate );
188 
189  // first, check max distance to outside of polygon
190  // TODO 2: there's a bug here -- if a candidate's center falls outside the polygon, then a larger
191  // distance to the polygon boundary is being considered as the best placement. That's clearly wrong --
192  // if any part of label candidate sits outside the polygon, we should first prefer candidates which sit
193  // entirely WITHIN the polygon, or failing that, candidates which are CLOSER to the polygon boundary, not further from it!
194  ringDistanceCalculator.addRing( candidate->feature );
195 
196  // prefer candidates further from the outside of map rather then those close to the outside of the map
197  // TODO 3: should be using the actual map boundary here, not the bounding box
198  const PointSet extent( 4, bbx, bby );
199  ringDistanceCalculator.addRing( &extent );
200 
201  // prefer candidates which further from interior rings (holes) of the polygon
202  for ( int i = 0; i < candidate->feature->getNumSelfObstacles(); ++i )
203  {
204  ringDistanceCalculator.addRing( candidate->feature->getSelfObstacle( i ) );
205  }
206 
207  return ringDistanceCalculator.minimumDistance();
208 }
209 
210 void CostCalculator::finalizeCandidatesCosts( Feats *feat, double bbx[4], double bby[4] )
211 {
212  // sort candidates list, best label to worst
213  std::sort( feat->candidates.begin(), feat->candidates.end(), candidateSortGrow );
214 
215  // Original nonsense comment from pal library:
216  // "try to exclude all conflitual labels (good ones have cost < 1 by pruning)"
217  // my interpretation: it appears this scans through the candidates and chooses some threshold
218  // based on the candidate cost, after which all remaining candidates are simply discarded
219  // my suspicion: I don't think this is needed (or wanted) here, and is reflective of the fact
220  // that obstacle costs are too low vs inferior candidate placement costs (i.e. without this,
221  // an "around point" label would rather be placed over an obstacle then be placed in a position > 6 o'clock
222  double discrim = 0.0;
223  std::size_t stop = 0;
224  do
225  {
226  discrim += 1.0;
227  for ( stop = 0; stop < feat->candidates.size() && feat->candidates[ stop ]->cost() < discrim; stop++ )
228  ;
229  }
230  while ( stop == 0 && discrim < feat->candidates.back()->cost() + 2.0 );
231 
232  // THIS LOOKS SUSPICIOUS -- it clamps all costs to a fixed value??
233  if ( discrim > 1.5 )
234  {
235  for ( std::size_t k = 0; k < stop; k++ )
236  feat->candidates[ k ]->setCost( 0.0021 );
237  }
238 
239  if ( feat->candidates.size() > stop )
240  {
241  feat->candidates.resize( stop );
242  }
243 
244  // Sets costs for candidates of polygon
245 
246  if ( feat->feature->getGeosType() == GEOS_POLYGON )
247  {
248  const int arrangement = feat->feature->layer()->arrangement();
249  if ( arrangement == QgsPalLayerSettings::Free || arrangement == QgsPalLayerSettings::Horizontal )
250  {
251  // prefer positions closer to the pole of inaccessibilities
253  // ...of these, prefer positions closer to the overall polygon centroid
255  }
256  }
257 
258  // add size penalty (small lines/polygons get higher cost)
259  feat->feature->addSizePenalty( feat->candidates, bbx, bby );
260 }
261 
263  : mPx( ( candidate->x[0] + candidate->x[2] ) / 2.0 )
264  , mPy( ( candidate->y[0] + candidate->y[2] ) / 2.0 )
265 {
266 }
267 
269 {
270  const double d = ring->minDistanceToPoint( mPx, mPy );
271  if ( d < mMinDistance )
272  {
273  mMinDistance = d;
274  }
275 }
276 
278 {
279  return mMinDistance;
280 }
double factor() const
Returns the obstacle factor, where 1.0 = default, < 1.0 more likely to be covered by labels,...
@ PlacementEngineVersion1
Version 1, matches placement from QGIS <= 3.10.1.
@ PlacementEngineVersion2
Version 2 (default for new projects since QGIS 3.12)
@ Horizontal
Arranges horizontal candidates scattered throughout a polygon feature. Applies to polygon layers only...
@ Free
Arranges candidates scattered throughout a polygon feature. Candidates are rotated to respect the pol...
Calculates distance from a label candidate to nearest polygon ring.
void addRing(const pal::PointSet *ring)
Adds a ring to the calculation, updating the minimumDistance() value if the rings is closer to the ca...
double minimumDistance() const
Returns the minimum distance between the candidate and all added rings.
CandidatePolygonRingDistanceCalculator(LabelPosition *candidate)
Constructor for PolygonRingDistanceCalculator, for the specified label candidate.
static double calculatePolygonRingDistance(LabelPosition *candidate, double bbx[4], double bby[4])
Calculates the distance between a label candidate and the closest ring for a polygon feature.
static void addObstacleCostPenalty(pal::LabelPosition *lp, pal::FeaturePart *obstacle, Pal *pal)
Increase candidate's cost according to its collision with passed feature.
static void finalizeCandidatesCosts(Feats *feat, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
static bool candidateSortGrow(const std::unique_ptr< pal::LabelPosition > &c1, const std::unique_ptr< pal::LabelPosition > &c2)
Sorts label candidates in ascending order of cost.
static void calculateCandidatePolygonRingDistanceCosts(std::vector< std::unique_ptr< pal::LabelPosition > > &lPos, double bbx[4], double bby[4])
Updates the costs for polygon label candidates by considering the distance between the candidates and...
static void calculateCandidatePolygonCentroidDistanceCosts(pal::FeaturePart *feature, std::vector< std::unique_ptr< pal::LabelPosition > > &lPos)
Updates the costs for polygon label candidates by considering the distance between the candidates and...
For usage in problem solving algorithm.
Definition: util.h:54
std::vector< std::unique_ptr< LabelPosition > > candidates
Definition: util.h:62
FeaturePart * feature
Definition: util.h:59
Main class to handle feature.
Definition: feature.h:65
double getLabelDistance() const
Returns the distance from the anchor point to the label.
Definition: feature.h:279
void addSizePenalty(std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4])
Increases the cost of the label candidates for this feature, based on the size of the feature.
Definition: feature.cpp:2055
int getNumSelfObstacles() const
Gets number of holes (inner rings) - they are considered as obstacles.
Definition: feature.h:305
const QgsLabelObstacleSettings & obstacleSettings() const
Returns the feature's obstacle settings.
Definition: feature.h:299
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:156
double calculatePriority() const
Calculates the priority for the feature.
Definition: feature.cpp:2191
FeaturePart * getSelfObstacle(int i)
Gets hole (inner ring) - considered as obstacle.
Definition: feature.h:307
LabelPosition is a candidate feature label position.
Definition: labelposition.h:56
bool intersectsWithPolygon(PointSet *polygon) const
Returns true if any intersection between polygon and position exists.
void setCost(double newCost)
Sets the candidate label position's geographical cost.
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
FeaturePart * feature
double cost() const
Returns the candidate label position's geographical cost.
void setConflictsWithObstacle(bool conflicts)
Sets whether the position is marked as conflicting with an obstacle feature.
void setHasHardObstacleConflict(bool conflicts)
Sets whether the position is marked as having a hard conflict with an obstacle feature.
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
double getDistanceToPoint(double xp, double yp) const
Gets distance from this label to a point. If point lies inside, returns negative number.
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center).
QgsPalLayerSettings::Placement arrangement() const
Returns the layer's arrangement policy.
Definition: layer.h:177
QgsLabelObstacleSettings::ObstacleType obstacleType() const
Returns the obstacle type, which controls how features within the layer act as obstacles for labels.
Definition: layer.h:229
Main Pal labeling class.
Definition: pal.h:80
The underlying raw pal geometry class.
Definition: pointset.h:76
std::vector< double > y
Definition: pointset.h:220
void getCentroid(double &px, double &py, bool forceInside=false) const
Definition: pointset.cpp:932
std::vector< double > x
Definition: pointset.h:219
int getGeosType() const
Definition: pointset.h:157
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:853
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:1504
#define EPSILON
Definition: util.h:78