Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Browse files
Browse the repository at this point in the history
Another round of refactoring.
Moved most of the candidate cost handling code to separate CostCalculator source. Some more "friend class" removals. git-svn-id: http://svn.osgeo.org/qgis/branches/symbology-ng-branch@11045 c8812cc2-4d05-0410-92ff-de0c093fc19c
- Loading branch information
wonder
committed
Jul 11, 2009
1 parent
5cfe487
commit 166b183
Showing
12 changed files
with
575 additions
and
566 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,344 @@ | ||
|
||
#include <iostream> | ||
#include <fstream> | ||
#include <cmath> | ||
#include <cstring> | ||
#include <cfloat> | ||
|
||
#include <pal/layer.h> | ||
#include <pal/pal.h> | ||
#include <pal/label.h> | ||
|
||
#include "feature.h" | ||
#include "geomfunction.h" | ||
#include "labelposition.h" | ||
#include "util.h" | ||
|
||
#include "costcalculator.h" | ||
|
||
namespace pal | ||
{ | ||
|
||
void CostCalculator::addObstacleCostPenalty(LabelPosition* lp, PointSet* feat) | ||
{ | ||
int n = 0; | ||
double dist; | ||
double distlabel = lp->feature->getLabelDistance(); | ||
/*unit_convert( double( lp->feature->distlabel ), | ||
pal::PIXEL, | ||
pal->map_unit, | ||
pal->dpi, scale, 1 );*/ | ||
|
||
switch ( feat->getGeosType() ) | ||
{ | ||
case GEOS_POINT: | ||
|
||
dist = lp->getDistanceToPoint( feat->x[0], feat->y[0] ); | ||
if ( dist < 0 ) | ||
n = 2; | ||
else if ( dist < distlabel ) | ||
n = 1; | ||
else | ||
n = 0; | ||
break; | ||
|
||
case GEOS_LINESTRING: | ||
|
||
// Is one of label's borders crossing the line ? | ||
n = ( lp->isBorderCrossingLine( feat ) ? 1 : 0 ); | ||
break; | ||
|
||
case GEOS_POLYGON: | ||
n = lp->getNumPointsInPolygon( feat->getNumPoints(), feat->x, feat->y ); | ||
break; | ||
} | ||
|
||
// label cost is penalized | ||
lp->setCost( lp->getCost() + double( n ) ); | ||
} | ||
|
||
|
||
//////// | ||
|
||
void CostCalculator::setPolygonCandidatesCost( int nblp, LabelPosition **lPos, int max_p, RTree<PointSet*, double, 2, double> *obstacles, double bbx[4], double bby[4] ) | ||
{ | ||
int i; | ||
|
||
double normalizer; | ||
// compute raw cost | ||
#ifdef _DEBUG_ | ||
std::cout << "LabelPosition for feat: " << lPos[0]->feature->uid << std::endl; | ||
#endif | ||
|
||
for ( i = 0;i < nblp;i++ ) | ||
setCandidateCostFromPolygon( lPos[i], obstacles, bbx, bby ); | ||
|
||
// lPos with big values came fisrts (value = min distance from label to Polygon's Perimeter) | ||
//sort ( (void**) lPos, nblp, costGrow); | ||
sort(( void** ) lPos, nblp, LabelPosition::costShrink ); | ||
|
||
|
||
// define the value's range | ||
double cost_max = lPos[0]->getCost(); | ||
double cost_min = lPos[max_p-1]->getCost(); | ||
|
||
cost_max -= cost_min; | ||
|
||
if ( cost_max > EPSILON ) | ||
{ | ||
normalizer = 0.0020 / cost_max; | ||
} | ||
else | ||
{ | ||
normalizer = 1; | ||
} | ||
|
||
// adjust cost => the best is 0.0001, the worst is 0.0021 | ||
// others are set proportionally between best and worst | ||
for ( i = 0;i < max_p;i++ ) | ||
{ | ||
#ifdef _DEBUG_ | ||
std::cout << " lpos[" << i << "] = " << lPos[i]->cost; | ||
#endif | ||
//if (cost_max - cost_min < EPSILON) | ||
if ( cost_max > EPSILON ) | ||
{ | ||
lPos[i]->cost = 0.0021 - ( lPos[i]->getCost() - cost_min ) * normalizer; | ||
} | ||
else | ||
{ | ||
//lPos[i]->cost = 0.0001 + (lPos[i]->cost - cost_min) * normalizer; | ||
lPos[i]->cost = 0.0001; | ||
} | ||
|
||
#ifdef _DEBUG_ | ||
std::cout << " ==> " << lPos[i]->cost << std::endl; | ||
#endif | ||
} | ||
} | ||
|
||
|
||
void CostCalculator::setCandidateCostFromPolygon( LabelPosition* lp, RTree <PointSet*, double, 2, double> *obstacles, double bbx[4], double bby[4] ) | ||
{ | ||
|
||
double amin[2]; | ||
double amax[2]; | ||
|
||
PolygonCostCalculator *pCost = new PolygonCostCalculator( lp ); | ||
|
||
// center | ||
//cost = feat->getDistInside((this->x[0] + this->x[2])/2.0, (this->y[0] + this->y[2])/2.0 ); | ||
|
||
lp->feature->fetchCoordinates(); | ||
pCost->update( lp->feature ); | ||
|
||
PointSet *extent = new PointSet( 4, bbx, bby ); | ||
|
||
pCost->update( extent ); | ||
|
||
delete extent; | ||
|
||
lp->feature->getBoundingBox(amin, amax); | ||
|
||
obstacles->Search( amin, amax, LabelPosition::polygonObstacleCallback, pCost ); | ||
|
||
lp->setCost( pCost->getCost() ); | ||
|
||
lp->feature->releaseCoordinates(); | ||
delete pCost; | ||
} | ||
|
||
|
||
int CostCalculator::finalizeCandidatesCosts( Feats* feat, int max_p, RTree <PointSet*, double, 2, double> *obstacles, double bbx[4], double bby[4] ) | ||
{ | ||
// If candidates list is smaller than expected | ||
if ( max_p > feat->nblp ) | ||
max_p = feat->nblp; | ||
// | ||
// sort candidates list, best label to worst | ||
sort(( void** ) feat->lPos, feat->nblp, LabelPosition::costGrow ); | ||
|
||
// try to exclude all conflitual labels (good ones have cost < 1 by pruning) | ||
double discrim = 0.0; | ||
int stop; | ||
do | ||
{ | ||
discrim += 1.0; | ||
for ( stop = 0;stop < feat->nblp && feat->lPos[stop]->getCost() < discrim;stop++ ); | ||
} | ||
while ( stop == 0 && discrim < feat->lPos[feat->nblp-1]->getCost() + 2.0 ); | ||
|
||
if ( discrim > 1.5 ) | ||
{ | ||
int k; | ||
for ( k = 0;k < stop;k++ ) | ||
feat->lPos[k]->setCost( 0.0021 ); | ||
} | ||
|
||
if ( max_p > stop ) | ||
max_p = stop; | ||
|
||
#ifdef _DEBUG_FULL_ | ||
std::cout << "Nblabel kept for feat " << feat->feature->uid << "/" << feat->feature->layer->name << ": " << max_p << "/" << feat->nblp << std::endl; | ||
#endif | ||
|
||
// Sets costs for candidates of polygon | ||
|
||
if ( feat->feature->getGeosType() == GEOS_POLYGON ) | ||
{ | ||
int arrangement = feat->feature->getLayer()->getArrangement(); | ||
if ( arrangement == P_FREE || arrangement == P_HORIZ ) | ||
setPolygonCandidatesCost( stop, feat->lPos, max_p, obstacles, bbx, bby ); | ||
} | ||
|
||
return max_p; | ||
} | ||
|
||
|
||
|
||
////////// | ||
|
||
PolygonCostCalculator::PolygonCostCalculator( LabelPosition *lp ) : lp( lp ) | ||
{ | ||
int i; | ||
double hyp = max( lp->feature->xmax - lp->feature->xmin, lp->feature->ymax - lp->feature->ymin ); | ||
hyp *= 10; | ||
|
||
px = ( lp->x[0] + lp->x[2] ) / 2.0; | ||
py = ( lp->y[0] + lp->y[2] ) / 2.0; | ||
dLp[0] = lp->w / 2; | ||
dLp[1] = lp->h / 2; | ||
dLp[2] = dLp[0] / cos( M_PI / 4 ); | ||
|
||
/* | ||
3 2 1 | ||
\ | / | ||
4 --x -- 0 | ||
/ | \ | ||
5 6 7 | ||
*/ | ||
|
||
double alpha = lp->getAlpha(); | ||
for ( i = 0;i < 8;i++, alpha += M_PI / 4 ) | ||
{ | ||
dist[i] = DBL_MAX; | ||
ok[i] = false; | ||
rpx[i] = px + cos( alpha ) * hyp; | ||
rpy[i] = py + sin( alpha ) * hyp; | ||
} | ||
} | ||
|
||
void PolygonCostCalculator::update( PointSet *pset ) | ||
{ | ||
if ( pset->type == GEOS_POINT ) | ||
{ | ||
updatePoint( pset ); | ||
} | ||
else | ||
{ | ||
double rx, ry; | ||
if ( pset->getDist( px, py, &rx, &ry ) < updateLinePoly( pset ) ) | ||
{ | ||
PointSet *point = new PointSet( ry, ry ); | ||
update( point ); | ||
delete point; | ||
} | ||
} | ||
} | ||
|
||
void PolygonCostCalculator::updatePoint( PointSet *pset ) | ||
{ | ||
double beta = atan2( pset->y[0] - py, pset->x[0] - px ) - lp->getAlpha(); | ||
|
||
while ( beta < 0 ) | ||
{ | ||
beta += 2 * M_PI; | ||
} | ||
|
||
double a45 = M_PI / 4; | ||
|
||
int i = ( int )( beta / a45 ); | ||
|
||
for ( int j = 0;j < 2;j++, i = ( i + 1 ) % 8 ) | ||
{ | ||
double rx, ry; | ||
rx = px - rpy[i] + py; | ||
ry = py + rpx[i] - px; | ||
double ix, iy; // the point that we look for | ||
if ( computeLineIntersection( px, py, rpx[i], rpy[i], pset->x[0], pset->y[0], rx, ry, &ix, &iy ) ) | ||
{ | ||
double d = dist_euc2d_sq( px, py, ix, iy ); | ||
if ( d < dist[i] ) | ||
{ | ||
dist[i] = d; | ||
ok[i] = true; | ||
} | ||
} | ||
else | ||
{ | ||
std::cout << "this shouldn't occurs !!!" << std::endl; | ||
} | ||
} | ||
} | ||
|
||
double PolygonCostCalculator::updateLinePoly( PointSet *pset ) | ||
{ | ||
int i, j, k; | ||
int nbP = ( pset->type == GEOS_POLYGON ? pset->nbPoints : pset->nbPoints - 1 ); | ||
double min_dist = DBL_MAX; | ||
|
||
for ( i = 0;i < nbP;i++ ) | ||
{ | ||
j = ( i + 1 ) % pset->nbPoints; | ||
|
||
for ( k = 0;k < 8;k++ ) | ||
{ | ||
double ix, iy; | ||
if ( computeSegIntersection( px, py, rpx[k], rpy[k], pset->x[i], pset->y[i], pset->x[j], pset->y[j], &ix, &iy ) ) | ||
{ | ||
double d = dist_euc2d_sq( px, py, ix, iy ); | ||
if ( d < dist[k] ) | ||
{ | ||
dist[k] = d; | ||
ok[k] = true; | ||
} | ||
if ( d < min_dist ) | ||
{ | ||
min_dist = d; | ||
} | ||
} | ||
} | ||
} | ||
return min_dist; | ||
} | ||
|
||
LabelPosition* PolygonCostCalculator::getLabel() | ||
{ | ||
return lp; | ||
} | ||
|
||
double PolygonCostCalculator::getCost() | ||
{ | ||
int i; | ||
|
||
for ( i = 0;i < 8;i++ ) | ||
{ | ||
dist[i] -= (( i % 2 ) ? dLp[2] : (( i == 0 || i == 4 ) ? dLp[0] : dLp[1] ) ); | ||
if ( !ok[i] || dist[i] < 0.1 ) | ||
{ | ||
dist[i] = 0.1; | ||
} | ||
} | ||
|
||
double a, b, c, d; | ||
|
||
a = min( dist[0], dist[4] ); | ||
b = min( dist[1], dist[5] ); | ||
c = min( dist[2], dist[6] ); | ||
d = min( dist[3], dist[7] ); | ||
|
||
//return (a+b+c+d); | ||
return ( a*b*c*d ); | ||
} | ||
|
||
} |
Oops, something went wrong.