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