Branch data Line data Source code
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 : 0 : bool CostCalculator::candidateSortGrow( const std::unique_ptr< LabelPosition > &c1, const std::unique_ptr< LabelPosition > &c2 )
29 : : {
30 : 0 : return c1->cost() < c2->cost();
31 : : }
32 : :
33 : 0 : void CostCalculator::addObstacleCostPenalty( LabelPosition *lp, FeaturePart *obstacle, Pal *pal )
34 : : {
35 : 0 : int n = 0;
36 : : double dist;
37 : 0 : double distlabel = lp->feature->getLabelDistance();
38 : :
39 : 0 : switch ( obstacle->getGeosType() )
40 : : {
41 : : case GEOS_POINT:
42 : :
43 : 0 : dist = lp->getDistanceToPoint( obstacle->x[0], obstacle->y[0] );
44 : 0 : if ( dist < 0 )
45 : 0 : n = 2;
46 : 0 : 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 : 0 : n = 1;
50 : : else
51 : 0 : n = 0;
52 : 0 : break;
53 : :
54 : : case GEOS_LINESTRING:
55 : :
56 : : // Is one of label's borders crossing the line ?
57 : 0 : n = ( lp->crossesLine( obstacle ) ? 1 : 0 );
58 : 0 : break;
59 : :
60 : : case GEOS_POLYGON:
61 : : // behavior depends on obstacle avoid type
62 : 0 : switch ( obstacle->layer()->obstacleType() )
63 : : {
64 : : case QgsLabelObstacleSettings::PolygonInterior:
65 : : // n ranges from 0 -> 12
66 : 0 : n = lp->polygonIntersectionCost( obstacle );
67 : 0 : break;
68 : : case QgsLabelObstacleSettings::PolygonBoundary:
69 : : // penalty may need tweaking, given that interior mode ranges up to 12
70 : 0 : n = ( lp->crossesBoundary( obstacle ) ? 6 : 0 );
71 : 0 : break;
72 : : case QgsLabelObstacleSettings::PolygonWhole:
73 : : // n is either 0 or 12
74 : 0 : n = ( lp->intersectsWithPolygon( obstacle ) ? 12 : 0 );
75 : 0 : break;
76 : : }
77 : :
78 : 0 : break;
79 : : }
80 : :
81 : : //scale cost by obstacle's factor
82 : 0 : double obstacleCost = obstacle->obstacleSettings().factor() * double( n );
83 : 0 : if ( n > 0 )
84 : 0 : lp->setConflictsWithObstacle( true );
85 : :
86 : 0 : switch ( pal->placementVersion() )
87 : : {
88 : : case QgsLabelingEngineSettings::PlacementEngineVersion1:
89 : 0 : break;
90 : :
91 : : case QgsLabelingEngineSettings::PlacementEngineVersion2:
92 : : {
93 : : // obstacle factor is from 0 -> 2, label priority is from 1 -> 0. argh!
94 : 0 : const double priority = 2 * ( 1 - lp->feature->calculatePriority() );
95 : 0 : const double obstaclePriority = obstacle->obstacleSettings().factor();
96 : :
97 : : // if feature priority is < obstaclePriorty, there's a hard conflict...
98 : 0 : if ( n > 0 && ( priority < obstaclePriority && !qgsDoubleNear( priority, obstaclePriority, 0.001 ) ) )
99 : : {
100 : 0 : lp->setHasHardObstacleConflict( true );
101 : 0 : }
102 : 0 : break;
103 : : }
104 : : }
105 : :
106 : : // label cost is penalized
107 : 0 : lp->setCost( lp->cost() + obstacleCost );
108 : 0 : }
109 : :
110 : 0 : 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 : 0 : QHash< LabelPosition *, double > polygonRingDistances;
115 : 0 : double minCandidateRingDistance = std::numeric_limits< double >::max();
116 : 0 : double maxCandidateRingDistance = std::numeric_limits< double >::lowest();
117 : 0 : for ( std::unique_ptr< LabelPosition > &pos : lPos )
118 : : {
119 : 0 : const double candidatePolygonRingDistance = calculatePolygonRingDistance( pos.get(), bbx, bby );
120 : :
121 : 0 : minCandidateRingDistance = std::min( minCandidateRingDistance, candidatePolygonRingDistance );
122 : 0 : maxCandidateRingDistance = std::max( maxCandidateRingDistance, candidatePolygonRingDistance );
123 : :
124 : 0 : 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 : 0 : const double costRange = maxCandidateRingDistance - minCandidateRingDistance;
129 : 0 : if ( costRange <= EPSILON )
130 : 0 : return;
131 : :
132 : 0 : 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 : 0 : for ( std::unique_ptr< LabelPosition > &pos : lPos )
137 : : {
138 : 0 : const double polygonRingDistanceCost = polygonRingDistances.value( pos.get() );
139 : 0 : pos->setCost( pos->cost() + 0.002 - ( polygonRingDistanceCost - minCandidateRingDistance ) * normalizer );
140 : : }
141 : 0 : }
142 : :
143 : 0 : void CostCalculator::calculateCandidatePolygonCentroidDistanceCosts( pal::FeaturePart *feature, std::vector<std::unique_ptr<LabelPosition> > &lPos )
144 : : {
145 : : double cx, cy;
146 : 0 : 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 : 0 : QHash< LabelPosition *, double > polygonCentroidDistances;
151 : 0 : double minCandidateCentroidDistance = std::numeric_limits< double >::max();
152 : 0 : double maxCandidateCentroidDistance = std::numeric_limits< double >::lowest();
153 : 0 : for ( std::unique_ptr< LabelPosition > &pos : lPos )
154 : : {
155 : 0 : const double lPosX = ( pos->x[0] + pos->x[2] ) / 2.0;
156 : 0 : const double lPosY = ( pos->y[0] + pos->y[2] ) / 2.0;
157 : :
158 : 0 : const double candidatePolygonCentroidDistance = std::sqrt( ( cx - lPosX ) * ( cx - lPosX ) + ( cy - lPosY ) * ( cy - lPosY ) );
159 : :
160 : 0 : minCandidateCentroidDistance = std::min( minCandidateCentroidDistance, candidatePolygonCentroidDistance );
161 : 0 : maxCandidateCentroidDistance = std::max( maxCandidateCentroidDistance, candidatePolygonCentroidDistance );
162 : :
163 : 0 : 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 : 0 : const double costRange = maxCandidateCentroidDistance - minCandidateCentroidDistance;
168 : 0 : if ( costRange <= EPSILON )
169 : 0 : return;
170 : :
171 : 0 : 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 : 0 : for ( std::unique_ptr< LabelPosition > &pos : lPos )
177 : : {
178 : 0 : const double polygonCentroidDistance = polygonCentroidDistances.value( pos.get() );
179 : 0 : pos->setCost( pos->cost() + ( polygonCentroidDistance - minCandidateCentroidDistance ) * normalizer );
180 : : }
181 : 0 : }
182 : :
183 : 0 : 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 : 0 : 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 : 0 : 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 : 0 : PointSet extent( 4, bbx, bby );
199 : 0 : ringDistanceCalculator.addRing( &extent );
200 : :
201 : : // prefer candidates which further from interior rings (holes) of the polygon
202 : 0 : for ( int i = 0; i < candidate->feature->getNumSelfObstacles(); ++i )
203 : : {
204 : 0 : ringDistanceCalculator.addRing( candidate->feature->getSelfObstacle( i ) );
205 : 0 : }
206 : :
207 : 0 : return ringDistanceCalculator.minimumDistance();
208 : 0 : }
209 : :
210 : 0 : void CostCalculator::finalizeCandidatesCosts( Feats *feat, double bbx[4], double bby[4] )
211 : : {
212 : : // sort candidates list, best label to worst
213 : 0 : 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 : 0 : double discrim = 0.0;
223 : 0 : std::size_t stop = 0;
224 : 0 : do
225 : : {
226 : 0 : discrim += 1.0;
227 : 0 : for ( stop = 0; stop < feat->candidates.size() && feat->candidates[ stop ]->cost() < discrim; stop++ )
228 : : ;
229 : 0 : }
230 : 0 : while ( stop == 0 && discrim < feat->candidates.back()->cost() + 2.0 );
231 : :
232 : : // THIS LOOKS SUSPICIOUS -- it clamps all costs to a fixed value??
233 : 0 : if ( discrim > 1.5 )
234 : : {
235 : 0 : for ( std::size_t k = 0; k < stop; k++ )
236 : 0 : feat->candidates[ k ]->setCost( 0.0021 );
237 : 0 : }
238 : :
239 : 0 : if ( feat->candidates.size() > stop )
240 : : {
241 : 0 : feat->candidates.resize( stop );
242 : 0 : }
243 : :
244 : : // Sets costs for candidates of polygon
245 : :
246 : 0 : if ( feat->feature->getGeosType() == GEOS_POLYGON )
247 : : {
248 : 0 : int arrangement = feat->feature->layer()->arrangement();
249 : 0 : if ( arrangement == QgsPalLayerSettings::Free || arrangement == QgsPalLayerSettings::Horizontal )
250 : : {
251 : : // prefer positions closer to the pole of inaccessibilities
252 : 0 : calculateCandidatePolygonRingDistanceCosts( feat->candidates, bbx, bby );
253 : : // ...of these, prefer positions closer to the overall polygon centroid
254 : 0 : calculateCandidatePolygonCentroidDistanceCosts( feat->feature, feat->candidates );
255 : 0 : }
256 : 0 : }
257 : :
258 : : // add size penalty (small lines/polygons get higher cost)
259 : 0 : feat->feature->addSizePenalty( feat->candidates, bbx, bby );
260 : 0 : }
261 : :
262 : 0 : CandidatePolygonRingDistanceCalculator::CandidatePolygonRingDistanceCalculator( LabelPosition *candidate )
263 : 0 : : mPx( ( candidate->x[0] + candidate->x[2] ) / 2.0 )
264 : 0 : , mPy( ( candidate->y[0] + candidate->y[2] ) / 2.0 )
265 : : {
266 : 0 : }
267 : :
268 : 0 : void CandidatePolygonRingDistanceCalculator::addRing( const pal::PointSet *ring )
269 : : {
270 : 0 : double d = ring->minDistanceToPoint( mPx, mPy );
271 : 0 : if ( d < mMinDistance )
272 : : {
273 : 0 : mMinDistance = d;
274 : 0 : }
275 : 0 : }
276 : :
277 : 0 : double CandidatePolygonRingDistanceCalculator::minimumDistance() const
278 : : {
279 : 0 : return mMinDistance;
280 : : }
|
