QGIS API Documentation 3.36.0-Maidenhead (09951dc0acf)
Loading...
Searching...
No Matches
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"
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], true );
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 = QgsGeometryUtilsBase::distance2D( cx, cy, lPosX, 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:914
@ 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...
@ Version2
Version 2 (default for new projects since QGIS 3.12)
@ Version1
Version 1, matches placement from QGIS <= 3.10.1.
static double distance2D(double x1, double y1, double x2, double y2)
Returns the 2D distance between (x1, y1) and (x2, y2).
double factor() const
Returns the obstacle factor, where 1.0 = default, < 1.0 more likely to be covered by labels,...
@ PolygonInterior
Avoid placing labels over interior of polygon (prefer placing labels totally outside or just slightly...
@ PolygonWhole
Avoid placing labels over ANY part of polygon. Where PolygonInterior will prefer to place labels with...
@ PolygonBoundary
Avoid placing labels over boundary of polygon (prefer placing outside or completely inside polygon)
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:57
std::vector< std::unique_ptr< LabelPosition > > candidates
Definition util.h:65
FeaturePart * feature
Definition util.h:62
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
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:163
FeaturePart * getSelfObstacle(int i)
Gets hole (inner ring) - considered as obstacle.
Definition feature.h:307
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:2251
double calculatePriority() const
Calculates the priority for the feature.
Definition feature.cpp:2382
LabelPosition is a candidate feature label position.
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:83
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:918
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:861
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition qgis.h:5144
#define EPSILON
Definition util.h:81