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