QGIS API Documentation  2.99.0-Master (0a63d1f)
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  // behavior 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:248
FeaturePart * feature
Definition: util.h:56
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.
double getLabelDistance() const
Definition: feature.h:228
QgsPalLayerSettings::ObstacleType obstacleType() const
Returns the obstacle type, which controls how features within the layer act as obstacles for labels...
Definition: layer.h:153
Arranges candidates following the curvature of a line feature. Applies to line layers only...
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:1608
double * x
Definition: pointset.h:154
PolygonCostCalculator(LabelPosition *lp)
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:119
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:96
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:47
Main class to handle feature.
Definition: feature.h:92
int polygonIntersectionCost(PointSet *polygon) const
Returns cost of position intersection with polygon (testing area of intersection and center)...
double * y
Definition: pointset.h:155
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:75
int getGeosType() const
Definition: pointset.h:117
LabelPosition is a candidate feature label position.
Definition: labelposition.h:52
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
QList< LabelPosition * > lPos
Definition: util.h:59
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. Candidates are rotated to respect the pol...
double getDistanceToPoint(double xp, double yp) const
Get distance from this label to a point. If point lies inside, returns negative number.