QGIS API Documentation  2.18.21-Las Palmas (9fba24a)
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 
149 void CostCalculator::setCandidateCostFromPolygon( LabelPosition* lp, RTree <FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
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
double obstacleFactor() const
Returns the feature&#39;s obstacle factor, which represents the penalty incurred for a label to overlap t...
Definition: feature.h:246
FeaturePart * feature
Definition: util.h:59
static bool candidateSortGrow(const LabelPosition *c1, const LabelPosition *c2)
Sorts label candidates in ascending order of cost.
bool intersectsWithPolygon(PointSet *polygon) const
Returns true if if any intersection between polygon and position exists.
void setCost(double newCost)
Sets the candidate label position&#39;s geographical cost.
const T & at(int i) const
double getLabelDistance() const
Definition: feature.h:226
QgsPalLayerSettings::ObstacleType obstacleType() const
Returns the obstacle type, which controls how features within the layer act as obstacles for labels...
Definition: layer.h:151
Arranges candidates following the curvature of a line feature.
void update(pal::PointSet *pset)
static void addObstacleCostPenalty(LabelPosition *lp, pal::FeaturePart *obstacle)
Increase candidate&#39;s cost according to its collision with passed feature.
double cost() const
Returns the candidate label position&#39;s geographical cost.
void addSizePenalty(int nbp, QList< LabelPosition *> &lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1604
double * x
Definition: pointset.h:153
PolygonCostCalculator(LabelPosition *lp)
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:118
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:150
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:94
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.
For usage in problem solving algorithm.
Definition: util.h:50
Main class to handle feature.
Definition: feature.h:91
iterator end()
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center)...
double * y
Definition: pointset.h:154
static void setPolygonCandidatesCost(int nblp, QList< LabelPosition * > &lPos, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
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:78
int getGeosType() const
Definition: pointset.h:116
LabelPosition is a candidate feature label position.
Definition: labelposition.h:51
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
QList< LabelPosition * > lPos
Definition: util.h:62
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.
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
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
Arranges candidates scattered throughout a polygon feature.
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point.