QGIS API Documentation  2.15.0-Master (5773d0d)
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
107  for ( int i = 0; i < nblp; ++i )
108  {
109  toSort << lPos.at( i );
110  }
111  qSort( toSort.begin(), toSort.end(), candidateSortShrink );
112  for ( int i = 0; i < nblp; ++i )
113  {
114  lPos[i] = toSort.at( i );
115  }
116 
117  // define the value's range
118  double cost_max = lPos.at( 0 )->cost();
119  double cost_min = lPos.at( nblp - 1 )->cost();
120 
121  cost_max -= cost_min;
122 
123  if ( cost_max > EPSILON )
124  {
125  normalizer = 0.0020 / cost_max;
126  }
127  else
128  {
129  normalizer = 1;
130  }
131 
132  // adjust cost => the best is 0.0001, the worst is 0.0021
133  // others are set proportionally between best and worst
134  for ( int i = 0; i < nblp; ++i )
135  {
136  //if (cost_max - cost_min < EPSILON)
137  if ( cost_max > EPSILON )
138  {
139  lPos.at( i )->setCost( 0.0021 - ( lPos.at( i )->cost() - cost_min ) * normalizer );
140  }
141  else
142  {
143  //lPos[i]->cost = 0.0001 + (lPos[i]->cost - cost_min) * normalizer;
144  lPos.at( i )->setCost( 0.0001 );
145  }
146  }
147 }
148 
150 {
151  double amin[2];
152  double amax[2];
153 
154  PolygonCostCalculator *pCost = new PolygonCostCalculator( lp );
155 
156  // center
157  //cost = feat->getDistInside((this->x[0] + this->x[2])/2.0, (this->y[0] + this->y[2])/2.0 );
158 
159  pCost->update( lp->feature );
160 
161  PointSet *extent = new PointSet( 4, bbx, bby );
162 
163  pCost->update( extent );
164 
165  delete extent;
166 
167  lp->feature->getBoundingBox( amin, amax );
168 
169  obstacles->Search( amin, amax, LabelPosition::polygonObstacleCallback, pCost );
170 
171  lp->setCost( pCost->getCost() );
172 
173  delete pCost;
174 }
175 
176 int CostCalculator::finalizeCandidatesCosts( Feats* feat, int max_p, RTree <FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
177 {
178  // If candidates list is smaller than expected
179  if ( max_p > feat->lPos.count() )
180  max_p = feat->lPos.count();
181  //
182  // sort candidates list, best label to worst
183  qSort( feat->lPos.begin(), feat->lPos.end(), candidateSortGrow );
184 
185  // try to exclude all conflitual labels (good ones have cost < 1 by pruning)
186  double discrim = 0.0;
187  int stop;
188  do
189  {
190  discrim += 1.0;
191  for ( stop = 0; stop < feat->lPos.count() && feat->lPos.at( stop )->cost() < discrim; stop++ )
192  ;
193  }
194  while ( stop == 0 && discrim < feat->lPos.last()->cost() + 2.0 );
195 
196  if ( discrim > 1.5 )
197  {
198  int k;
199  for ( k = 0; k < stop; k++ )
200  feat->lPos.at( k )->setCost( 0.0021 );
201  }
202 
203  if ( max_p > stop )
204  max_p = stop;
205 
206  // Sets costs for candidates of polygon
207 
208  if ( feat->feature->getGeosType() == GEOS_POLYGON )
209  {
210  int arrangement = feat->feature->layer()->arrangement();
211  if ( arrangement == QgsPalLayerSettings::Free || arrangement == QgsPalLayerSettings::Horizontal )
212  setPolygonCandidatesCost( stop, feat->lPos, obstacles, bbx, bby );
213  }
214 
215  // add size penalty (small lines/polygons get higher cost)
216  feat->feature->addSizePenalty( max_p, feat->lPos, bbx, bby );
217 
218  return max_p;
219 }
220 
222 {
223  px = ( lp->x[0] + lp->x[2] ) / 2.0;
224  py = ( lp->y[0] + lp->y[2] ) / 2.0;
225 
226  dist = DBL_MAX;
227  ok = false;
228 }
229 
231 {
232  double d = pset->minDistanceToPoint( px, py );
233  if ( d < dist )
234  {
235  dist = d;
236  }
237 }
238 
240 {
241  return lp;
242 }
243 
245 {
246  return ( 4 * dist );
247 }
FeaturePart * feature
FeaturePart * feature
Definition: util.h:58
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.
const T & at(int i) const
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:1373
Arranges candidates following the curvature of a line feature.
void update(pal::PointSet *pset)
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:91
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:144
double getLabelDistance() const
Definition: feature.h:199
double * x
Definition: pointset.h:152
PolygonCostCalculator(LabelPosition *lp)
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point.
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:149
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:49
Main class to handle feature.
Definition: feature.h:90
iterator end()
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:77
double obstacleFactor()
Definition: feature.h:206
LabelPosition is a candidate feature label position.
Definition: labelposition.h:50
QList< LabelPosition * > lPos
Definition: util.h:61
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:763
iterator begin()
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.