QGIS API Documentation  2.99.0-Master (c558d51)
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 
29 {
30  return c1->cost() < c2->cost();
31 }
32 
34 {
35  return c1->cost() > c2->cost();
36 }
37 
39 {
40  int n = 0;
41  double dist;
42  double distlabel = lp->feature->getLabelDistance();
43 
44  switch ( obstacle->getGeosType() )
45  {
46  case GEOS_POINT:
47 
48  dist = lp->getDistanceToPoint( obstacle->x[0], obstacle->y[0] );
49  if ( dist < 0 )
50  n = 2;
51  else if ( dist < distlabel )
52  //note this never happens at the moment - points are not obstacles if they don't fall
53  //within the label
54  n = 1;
55  else
56  n = 0;
57  break;
58 
59  case GEOS_LINESTRING:
60 
61  // Is one of label's borders crossing the line ?
62  n = ( lp->crossesLine( obstacle ) ? 1 : 0 );
63  break;
64 
65  case GEOS_POLYGON:
66  // behaviour depends on obstacle avoid type
67  switch ( obstacle->layer()->obstacleType() )
68  {
70  // n ranges from 0 -> 12
71  n = lp->polygonIntersectionCost( obstacle );
72  break;
74  // penalty may need tweaking, given that interior mode ranges up to 12
75  n = ( lp->crossesBoundary( obstacle ) ? 6 : 0 );
76  break;
78  // n is either 0 or 12
79  n = ( lp->intersectsWithPolygon( obstacle ) ? 12 : 0 );
80  break;
81  }
82 
83  break;
84  }
85 
86  if ( n > 0 )
87  lp->setConflictsWithObstacle( true );
88 
89  //scale cost by obstacle's factor
90  double obstacleCost = obstacle->obstacleFactor() * double( n );
91 
92  // label cost is penalized
93  lp->setCost( lp->cost() + obstacleCost );
94 }
95 
96 void CostCalculator::setPolygonCandidatesCost( int nblp, QList< LabelPosition* >& lPos, RTree<FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
97 {
98  double normalizer;
99  // compute raw cost
100  for ( int i = 0; i < nblp; ++i )
101  setCandidateCostFromPolygon( lPos.at( i ), obstacles, bbx, bby );
102 
103  // lPos with big values came first (value = min distance from label to Polygon's Perimeter)
104  // IMPORTANT - only want to sort first nblp positions. The rest have not had the cost
105  // calculated so will have nonsense values
106  QList< LabelPosition* > toSort;
107  toSort.reserve( nblp );
108  for ( int i = 0; i < nblp; ++i )
109  {
110  toSort << lPos.at( i );
111  }
112  qSort( toSort.begin(), toSort.end(), candidateSortShrink );
113  for ( int i = 0; i < nblp; ++i )
114  {
115  lPos[i] = toSort.at( i );
116  }
117 
118  // define the value's range
119  double cost_max = lPos.at( 0 )->cost();
120  double cost_min = lPos.at( nblp - 1 )->cost();
121 
122  cost_max -= cost_min;
123 
124  if ( cost_max > EPSILON )
125  {
126  normalizer = 0.0020 / cost_max;
127  }
128  else
129  {
130  normalizer = 1;
131  }
132 
133  // adjust cost => the best is 0.0001, the worst is 0.0021
134  // others are set proportionally between best and worst
135  for ( int i = 0; i < nblp; ++i )
136  {
137  //if (cost_max - cost_min < EPSILON)
138  if ( cost_max > EPSILON )
139  {
140  lPos.at( i )->setCost( 0.0021 - ( lPos.at( i )->cost() - cost_min ) * normalizer );
141  }
142  else
143  {
144  //lPos[i]->cost = 0.0001 + (lPos[i]->cost - cost_min) * normalizer;
145  lPos.at( i )->setCost( 0.0001 );
146  }
147  }
148 }
149 
150 void CostCalculator::setCandidateCostFromPolygon( LabelPosition* lp, RTree <FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
151 {
152  double amin[2];
153  double amax[2];
154 
155  PolygonCostCalculator *pCost = new PolygonCostCalculator( lp );
156 
157  // center
158  //cost = feat->getDistInside((this->x[0] + this->x[2])/2.0, (this->y[0] + this->y[2])/2.0 );
159 
160  pCost->update( lp->feature );
161 
162  PointSet *extent = new PointSet( 4, bbx, bby );
163 
164  pCost->update( extent );
165 
166  delete extent;
167 
168  lp->feature->getBoundingBox( amin, amax );
169 
170  obstacles->Search( amin, amax, LabelPosition::polygonObstacleCallback, pCost );
171 
172  lp->setCost( pCost->getCost() );
173 
174  delete pCost;
175 }
176 
177 int CostCalculator::finalizeCandidatesCosts( Feats* feat, int max_p, RTree <FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
178 {
179  // If candidates list is smaller than expected
180  if ( max_p > feat->lPos.count() )
181  max_p = feat->lPos.count();
182  //
183  // sort candidates list, best label to worst
184  qSort( feat->lPos.begin(), feat->lPos.end(), candidateSortGrow );
185 
186  // try to exclude all conflitual labels (good ones have cost < 1 by pruning)
187  double discrim = 0.0;
188  int stop;
189  do
190  {
191  discrim += 1.0;
192  for ( stop = 0; stop < feat->lPos.count() && feat->lPos.at( stop )->cost() < discrim; stop++ )
193  ;
194  }
195  while ( stop == 0 && discrim < feat->lPos.last()->cost() + 2.0 );
196 
197  if ( discrim > 1.5 )
198  {
199  int k;
200  for ( k = 0; k < stop; k++ )
201  feat->lPos.at( k )->setCost( 0.0021 );
202  }
203 
204  if ( max_p > stop )
205  max_p = stop;
206 
207  // Sets costs for candidates of polygon
208 
209  if ( feat->feature->getGeosType() == GEOS_POLYGON )
210  {
211  int arrangement = feat->feature->layer()->arrangement();
212  if ( arrangement == QgsPalLayerSettings::Free || arrangement == QgsPalLayerSettings::Horizontal )
213  setPolygonCandidatesCost( stop, feat->lPos, obstacles, bbx, bby );
214  }
215 
216  // add size penalty (small lines/polygons get higher cost)
217  feat->feature->addSizePenalty( max_p, feat->lPos, bbx, bby );
218 
219  return max_p;
220 }
221 
223 {
224  px = ( lp->x[0] + lp->x[2] ) / 2.0;
225  py = ( lp->y[0] + lp->y[2] ) / 2.0;
226 
227  dist = DBL_MAX;
228  ok = false;
229 }
230 
232 {
233  double d = pset->minDistanceToPoint( px, py );
234  if ( d < dist )
235  {
236  dist = d;
237  }
238 }
239 
241 {
242  return lp;
243 }
244 
246 {
247  return ( 4 * dist );
248 }
FeaturePart * feature
double obstacleFactor() const
Returns the feature&#39;s obstacle factor, which represents the penalty incurred for a label to overlap t...
Definition: feature.h:245
FeaturePart * feature
Definition: util.h:56
static bool candidateSortGrow(const LabelPosition *c1, const LabelPosition *c2)
Sorts label candidates in ascending order of cost.
void setCost(double newCost)
Sets the candidate label position&#39;s geographical cost.
double cost() const
Returns the candidate label position&#39;s geographical cost.
int getGeosType() const
Definition: pointset.h:115
void addSizePenalty(int nbp, QList< LabelPosition * > &lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1608
Arranges candidates following the curvature of a line feature. Applies to line layers only...
void update(pal::PointSet *pset)
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:95
static void addObstacleCostPenalty(LabelPosition *lp, pal::FeaturePart *obstacle)
Increase candidate&#39;s cost according to its collision with passed feature.
QgsPalLayerSettings::ObstacleType obstacleType() const
Returns the obstacle type, which controls how features within the layer act as obstacles for labels...
Definition: layer.h:152
double getLabelDistance() const
Definition: feature.h:225
double * x
Definition: pointset.h:152
PolygonCostCalculator(LabelPosition *lp)
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point. If point lies inside, returns negative number.
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:150
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center)...
static int finalizeCandidatesCosts(Feats *feat, int max_p, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
For usage in problem solving algorithm.
Definition: util.h:47
Main class to handle feature.
Definition: feature.h:89
double * y
Definition: pointset.h:153
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:117
bool intersectsWithPolygon(PointSet *polygon) const
Returns true if if any intersection between polygon and position exists.
static void setPolygonCandidatesCost(int nblp, QList< LabelPosition * > &lPos, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
void setConflictsWithObstacle(bool conflicts)
Sets whether the position is marked as conflicting with an obstacle feature.
static bool polygonObstacleCallback(pal::FeaturePart *obstacle, void *ctx)
static void setCandidateCostFromPolygon(LabelPosition *lp, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Set cost to the smallest distance between lPos&#39;s centroid and a polygon stored in geoetry field...
#define EPSILON
Definition: util.h:75
LabelPosition is a candidate feature label position.
Definition: labelposition.h:51
QList< LabelPosition * > lPos
Definition: util.h:59
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:720
static bool candidateSortShrink(const LabelPosition *c1, const LabelPosition *c2)
Sorts label candidates in descending order of cost.
Data structure to compute polygon&#39;s candidates costs.
Arranges candidates scattered throughout a polygon feature. Candidates are rotated to respect the pol...