QGIS API Documentation 3.28.0-Firenze (ed3ad0430f)
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
26using namespace pal;
27
28bool 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
110void 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
143void 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
183double 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
210void 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 Qgis::LabelPlacement arrangement = feat->feature->layer()->arrangement();
249 if ( arrangement == Qgis::LabelPlacement::Free || arrangement == Qgis::LabelPlacement::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}
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,...
@ PlacementEngineVersion1
Version 1, matches placement from QGIS <= 3.10.1.
@ PlacementEngineVersion2
Version 2 (default for new projects since QGIS 3.12)
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) 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).
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:80
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:2527
#define EPSILON
Definition: util.h:78