QGIS API Documentation  2.11.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
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 <iostream>
24 #include <fstream>
25 #include <cmath>
26 #include <cfloat>
27 
28 namespace pal
29 {
30 
32  {
33  int n = 0;
34  double dist;
35  double distlabel = lp->feature->getLabelDistance();
36 
37  switch ( obstacle->getGeosType() )
38  {
39  case GEOS_POINT:
40 
41  dist = lp->getDistanceToPoint( obstacle->x[0], obstacle->y[0] );
42  if ( dist < 0 )
43  n = 2;
44  else if ( dist < distlabel )
45  //note this never happens at the moment - points are not obstacles if they don't fall
46  //within the label
47  n = 1;
48  else
49  n = 0;
50  break;
51 
52  case GEOS_LINESTRING:
53 
54  // Is one of label's borders crossing the line ?
55  n = ( lp->isBorderCrossingLine( obstacle ) ? 1 : 0 );
56  break;
57 
58  case GEOS_POLYGON:
59  // behaviour depends on obstacle avoid type
60  switch ( obstacle->layer()->obstacleType() )
61  {
62  case PolygonInterior:
63  // n ranges from 0 -> 12
64  n = lp->getNumPointsInPolygon( obstacle );
65  break;
66  case PolygonBoundary:
67  // penalty may need tweaking, given that interior mode ranges up to 12
68  n = ( lp->isBorderCrossingLine( obstacle ) ? 6 : 0 );
69  break;
70  }
71 
72  break;
73  }
74 
75  if ( n > 0 )
76  lp->setConflictsWithObstacle( true );
77 
78  //scale cost by obstacle's factor
79  double obstacleCost = obstacle->getFeature()->obstacleFactor() * double( n );
80 
81  // label cost is penalized
82  lp->setCost( lp->cost() + obstacleCost );
83  }
84 
85 
87 
88  void CostCalculator::setPolygonCandidatesCost( int nblp, LabelPosition **lPos, int max_p, RTree<FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
89  {
90  int i;
91 
92  double normalizer;
93  // compute raw cost
94 #ifdef _DEBUG_
95  std::cout << "LabelPosition for feat: " << lPos[0]->feature->uid << std::endl;
96 #endif
97 
98  for ( i = 0; i < nblp; i++ )
99  setCandidateCostFromPolygon( lPos[i], obstacles, bbx, bby );
100 
101  // lPos with big values came fisrts (value = min distance from label to Polygon's Perimeter)
102  //sort ( (void**) lPos, nblp, costGrow);
103  sort(( void** ) lPos, nblp, LabelPosition::costShrink );
104 
105 
106  // define the value's range
107  double cost_max = lPos[0]->cost();
108  double cost_min = lPos[max_p-1]->cost();
109 
110  cost_max -= cost_min;
111 
112  if ( cost_max > EPSILON )
113  {
114  normalizer = 0.0020 / cost_max;
115  }
116  else
117  {
118  normalizer = 1;
119  }
120 
121  // adjust cost => the best is 0.0001, the worst is 0.0021
122  // others are set proportionally between best and worst
123  for ( i = 0; i < max_p; i++ )
124  {
125 #ifdef _DEBUG_
126  std::cout << " lpos[" << i << "] = " << lPos[i]->cost;
127 #endif
128  //if (cost_max - cost_min < EPSILON)
129  if ( cost_max > EPSILON )
130  {
131  lPos[i]->mCost = 0.0021 - ( lPos[i]->cost() - cost_min ) * normalizer;
132  }
133  else
134  {
135  //lPos[i]->cost = 0.0001 + (lPos[i]->cost - cost_min) * normalizer;
136  lPos[i]->mCost = 0.0001;
137  }
138 
139 #ifdef _DEBUG_
140  std::cout << " ==> " << lPos[i]->cost << std::endl;
141 #endif
142  }
143  }
144 
145 
147  {
148 
149  double amin[2];
150  double amax[2];
151 
152  PolygonCostCalculator *pCost = new PolygonCostCalculator( lp );
153 
154  // center
155  //cost = feat->getDistInside((this->x[0] + this->x[2])/2.0, (this->y[0] + this->y[2])/2.0 );
156 
157  pCost->update( lp->feature );
158 
159  PointSet *extent = new PointSet( 4, bbx, bby );
160 
161  pCost->update( extent );
162 
163  delete extent;
164 
165  lp->feature->getBoundingBox( amin, amax );
166 
167  obstacles->Search( amin, amax, LabelPosition::polygonObstacleCallback, pCost );
168 
169  lp->setCost( pCost->getCost() );
170 
171  delete pCost;
172  }
173 
174  int CostCalculator::finalizeCandidatesCosts( Feats* feat, int max_p, RTree <FeaturePart*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
175  {
176  // If candidates list is smaller than expected
177  if ( max_p > feat->nblp )
178  max_p = feat->nblp;
179  //
180  // sort candidates list, best label to worst
181  sort(( void** ) feat->lPos, feat->nblp, LabelPosition::costGrow );
182 
183  // try to exclude all conflitual labels (good ones have cost < 1 by pruning)
184  double discrim = 0.0;
185  int stop;
186  do
187  {
188  discrim += 1.0;
189  for ( stop = 0; stop < feat->nblp && feat->lPos[stop]->cost() < discrim; stop++ )
190  ;
191  }
192  while ( stop == 0 && discrim < feat->lPos[feat->nblp-1]->cost() + 2.0 );
193 
194  if ( discrim > 1.5 )
195  {
196  int k;
197  for ( k = 0; k < stop; k++ )
198  feat->lPos[k]->setCost( 0.0021 );
199  }
200 
201  if ( max_p > stop )
202  max_p = stop;
203 
204 #ifdef _DEBUG_FULL_
205  std::cout << "Nblabel kept for feat " << feat->feature->getUID() << "/" << feat->feature->getLayer()->getName() << ": " << max_p << "/" << feat->nblp << std::endl;
206 #endif
207 
208  // Sets costs for candidates of polygon
209 
210  if ( feat->feature->getGeosType() == GEOS_POLYGON )
211  {
212  int arrangement = feat->feature->layer()->arrangement();
213  if ( arrangement == P_FREE || arrangement == P_HORIZ )
214  setPolygonCandidatesCost( stop, ( LabelPosition** ) feat->lPos, max_p, obstacles, bbx, bby );
215  }
216 
217  // add size penalty (small lines/polygons get higher cost)
218  feat->feature->addSizePenalty( max_p, feat->lPos, bbx, bby );
219 
220  return max_p;
221  }
222 
223 
224 
226 
228  {
229  px = ( lp->x[0] + lp->x[2] ) / 2.0;
230  py = ( lp->y[0] + lp->y[2] ) / 2.0;
231 
232  dist = DBL_MAX;
233  ok = false;
234  }
235 
237  {
238  double d = pset->minDistanceToPoint( px, py );
239  if ( d < dist )
240  {
241  dist = d;
242  }
243  }
244 
246  {
247  return lp;
248  }
249 
251  {
252  return ( 4 * dist );
253  }
254 }
bool isBorderCrossingLine(PointSet *line) const
Returns true if this label crosses the specified line.
double obstacleFactor() const
Returns the obstacle factor for the feature.
Definition: feature.h:136
FeaturePart * feature
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:157
FeaturePart * feature
Definition: util.h:53
Feature * getFeature()
Returns the parent feature.
Definition: feature.h:264
Arrangement arrangement() const
Returns the layer's arrangement policy.
Definition: layer.h:91
void setCost(double newCost)
Sets the candidate label position's geographical cost.
double cost() const
Returns the candidate label position's geographical cost.
static bool costGrow(void *l, void *r)
int getGeosType() const
Definition: pointset.h:113
Only for polygon, arranges candidates with respect of polygon orientation.
Definition: pal.h:82
void addSizePenalty(int nbp, LabelPosition **lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1313
static void setPolygonCandidatesCost(int nblp, LabelPosition **lPos, int max_p, RTree< pal::FeaturePart *, double, 2, double > *obstacles, double bbx[4], double bby[4])
QString getUID() const
Returns the unique ID of the feature.
Definition: feature.cpp:188
double getLabelDistance() const
Definition: feature.h:300
double * x
Definition: pointset.h:146
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:183
For usage in problem solving algorithm.
Definition: util.h:50
Main class to handle feature.
Definition: feature.h:203
static void addObstacleCostPenalty(LabelPosition *lp, pal::FeaturePart *obstacle)
Increase candidate's cost according to its collision with passed feature.
double * y
Definition: pointset.h:147
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:115
Only for lines, labels along the line.
Definition: pal.h:81
LabelPosition ** lPos
Definition: util.h:57
int getNumPointsInPolygon(PointSet *polygon) const
Returns number of intersections with polygon (testing border and center)
#define EPSILON
Definition: util.h:73
void update(pal::PointSet *pset)
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:881
void sort(void **items, int N, bool(*greater)(void *l, void *r))
Sort an array of pointers.
Definition: util.cpp:61
int nblp
Definition: util.h:56
Data structure to compute polygon's candidates costs.
static bool costShrink(void *l, void *r)