QGIS API Documentation  2.11.0-Master
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 <iostream>
17 #include <fstream>
18 #include <cmath>
19 #include <cstring>
20 #include <cfloat>
21 
22 #include "layer.h"
23 #include "pal.h"
24 #include "feature.h"
25 #include "geomfunction.h"
26 #include "labelposition.h"
27 #include "util.h"
28 #include "costcalculator.h"
29 
30 namespace pal
31 {
32 
34  {
35  int n = 0;
36  double dist;
37  double distlabel = lp->feature->getLabelDistance();
38 
39  switch ( feat->getGeosType() )
40  {
41  case GEOS_POINT:
42 
43  dist = lp->getDistanceToPoint( feat->x[0], feat->y[0] );
44  if ( dist < 0 )
45  n = 2;
46  else if ( dist < distlabel )
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( feat ) ? 1 : 0 );
56  break;
57 
58  case GEOS_POLYGON:
59  n = lp->getNumPointsInPolygon( feat->getNumPoints(), feat->x, feat->y );
60  break;
61  }
62 
63  // label cost is penalized
64  lp->setCost( lp->getCost() + double( n ) );
65  }
66 
67 
69 
70  void CostCalculator::setPolygonCandidatesCost( int nblp, LabelPosition **lPos, int max_p, RTree<PointSet*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
71  {
72  int i;
73 
74  double normalizer;
75  // compute raw cost
76 #ifdef _DEBUG_
77  std::cout << "LabelPosition for feat: " << lPos[0]->feature->uid << std::endl;
78 #endif
79 
80  for ( i = 0; i < nblp; i++ )
81  setCandidateCostFromPolygon( lPos[i], obstacles, bbx, bby );
82 
83  // lPos with big values came fisrts (value = min distance from label to Polygon's Perimeter)
84  //sort ( (void**) lPos, nblp, costGrow);
85  sort(( void** ) lPos, nblp, LabelPosition::costShrink );
86 
87 
88  // define the value's range
89  double cost_max = lPos[0]->getCost();
90  double cost_min = lPos[max_p-1]->getCost();
91 
92  cost_max -= cost_min;
93 
94  if ( cost_max > EPSILON )
95  {
96  normalizer = 0.0020 / cost_max;
97  }
98  else
99  {
100  normalizer = 1;
101  }
102 
103  // adjust cost => the best is 0.0001, the worst is 0.0021
104  // others are set proportionally between best and worst
105  for ( i = 0; i < max_p; i++ )
106  {
107 #ifdef _DEBUG_
108  std::cout << " lpos[" << i << "] = " << lPos[i]->cost;
109 #endif
110  //if (cost_max - cost_min < EPSILON)
111  if ( cost_max > EPSILON )
112  {
113  lPos[i]->cost = 0.0021 - ( lPos[i]->getCost() - cost_min ) * normalizer;
114  }
115  else
116  {
117  //lPos[i]->cost = 0.0001 + (lPos[i]->cost - cost_min) * normalizer;
118  lPos[i]->cost = 0.0001;
119  }
120 
121 #ifdef _DEBUG_
122  std::cout << " ==> " << lPos[i]->cost << std::endl;
123 #endif
124  }
125  }
126 
127 
129  {
130 
131  double amin[2];
132  double amax[2];
133 
134  PolygonCostCalculator *pCost = new PolygonCostCalculator( lp );
135 
136  // center
137  //cost = feat->getDistInside((this->x[0] + this->x[2])/2.0, (this->y[0] + this->y[2])/2.0 );
138 
139  pCost->update( lp->feature );
140 
141  PointSet *extent = new PointSet( 4, bbx, bby );
142 
143  pCost->update( extent );
144 
145  delete extent;
146 
147  lp->feature->getBoundingBox( amin, amax );
148 
149  obstacles->Search( amin, amax, LabelPosition::polygonObstacleCallback, pCost );
150 
151  lp->setCost( pCost->getCost() );
152 
153  delete pCost;
154  }
155 
156  int CostCalculator::finalizeCandidatesCosts( Feats* feat, int max_p, RTree <PointSet*, double, 2, double> *obstacles, double bbx[4], double bby[4] )
157  {
158  // If candidates list is smaller than expected
159  if ( max_p > feat->nblp )
160  max_p = feat->nblp;
161  //
162  // sort candidates list, best label to worst
163  sort(( void** ) feat->lPos, feat->nblp, LabelPosition::costGrow );
164 
165  // try to exclude all conflitual labels (good ones have cost < 1 by pruning)
166  double discrim = 0.0;
167  int stop;
168  do
169  {
170  discrim += 1.0;
171  for ( stop = 0; stop < feat->nblp && feat->lPos[stop]->getCost() < discrim; stop++ )
172  ;
173  }
174  while ( stop == 0 && discrim < feat->lPos[feat->nblp-1]->getCost() + 2.0 );
175 
176  if ( discrim > 1.5 )
177  {
178  int k;
179  for ( k = 0; k < stop; k++ )
180  feat->lPos[k]->setCost( 0.0021 );
181  }
182 
183  if ( max_p > stop )
184  max_p = stop;
185 
186 #ifdef _DEBUG_FULL_
187  std::cout << "Nblabel kept for feat " << feat->feature->getUID() << "/" << feat->feature->getLayer()->getName() << ": " << max_p << "/" << feat->nblp << std::endl;
188 #endif
189 
190  // Sets costs for candidates of polygon
191 
192  if ( feat->feature->getGeosType() == GEOS_POLYGON )
193  {
194  int arrangement = feat->feature->getLayer()->getArrangement();
195  if ( arrangement == P_FREE || arrangement == P_HORIZ )
196  setPolygonCandidatesCost( stop, ( LabelPosition** ) feat->lPos, max_p, obstacles, bbx, bby );
197  }
198 
199  // add size penalty (small lines/polygons get higher cost)
200  feat->feature->addSizePenalty( max_p, feat->lPos, bbx, bby );
201 
202  return max_p;
203  }
204 
205 
206 
208 
210  {
211  px = ( lp->x[0] + lp->x[2] ) / 2.0;
212  py = ( lp->y[0] + lp->y[2] ) / 2.0;
213 
214  dist = DBL_MAX;
215  ok = false;
216  }
217 
219  {
220  double rx, ry;
221  pset->getDist( px, py, &rx, &ry );
222  double d = dist_euc2d_sq( px, py, rx, ry );
223  if ( d < dist )
224  {
225  dist = d;
226  }
227  }
228 
230  {
231  return lp;
232  }
233 
235  {
236  return ( 4 * dist );
237  }
238 }
FeaturePart * feature
bool isBorderCrossingLine(PointSet *feat)
Returns true if this label crosses the specified line.
double getCost() const
get the position geographical cost
FeaturePart * feature
Definition: util.h:57
static void setCandidateCostFromPolygon(LabelPosition *lp, RTree< PointSet *, 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...
static void setPolygonCandidatesCost(int nblp, LabelPosition **lPos, int max_p, RTree< PointSet *, double, 2, double > *obstacles, double bbx[4], double bby[4])
void setCost(double newCost)
Modify candidate's cost.
static bool costGrow(void *l, void *r)
double dist_euc2d_sq(double x1, double y1, double x2, double y2)
Definition: geomfunction.h:57
int getGeosType() const
Definition: pointset.h:138
Layer * getLayer()
return the layer that feature belongs to
Definition: feature.cpp:257
static void addObstacleCostPenalty(LabelPosition *lp, PointSet *feat)
Increase candidate's cost according to its collision with passed feature.
void addSizePenalty(int nbp, LabelPosition **lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1411
static bool polygonObstacleCallback(PointSet *feat, void *ctx)
double getLabelDistance() const
Definition: feature.h:250
double * x
Definition: pointset.h:204
double getDistanceToPoint(double xp, double yp)
Get distance from this label to a point.
void update(PointSet *pset)
Only for lines, labels along the line.
Definition: pal.h:97
For usage in problem solving algorithm.
Definition: util.h:54
static int finalizeCandidatesCosts(Feats *feat, int max_p, RTree< PointSet *, double, 2, double > *obstacles, double bbx[4], double bby[4])
Sort candidates by costs, skip the worse ones, evaluate polygon candidates.
const char * getUID()
get the unique id of the feature
Definition: feature.cpp:263
int getNumPoints() const
Definition: pointset.h:149
Arrangement getArrangement()
get arrangement policy
Definition: layer.cpp:151
double * y
Definition: pointset.h:205
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:140
const char * getName()
get layer's name
Definition: layer.cpp:146
void sort(double *heap, int *x, int *y, int N)
Definition: util.cpp:67
double getDist(double px, double py, double *rx, double *ry)
return the minimum distance bw this and the point (px,py)
Definition: pointset.cpp:778
LabelPosition ** lPos
Definition: util.h:61
#define EPSILON
Definition: util.h:79
Only for polygon, arranges candidates with respect of polygon orientation.
Definition: pal.h:98
LabelPosition is a candidate feature label position.
Definition: labelposition.h:50
PolygonCostCalculator(LabelPosition *lp)
int nblp
Definition: util.h:60
Data structure to compute polygon's candidates costs.
int getNumPointsInPolygon(int npol, double *xp, double *yp)
Returns number of intersections with polygon (testing border and center)
static bool costShrink(void *l, void *r)