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