Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
pal: added functions for more granular access to labeling. added poss…
…ibility to use only initial solution (FALP algorithm). Added some timing.

git-svn-id: http://svn.osgeo.org/qgis/branches/symbology-ng-branch@11018 c8812cc2-4d05-0410-92ff-de0c093fc19c
  • Loading branch information
wonder committed Jul 4, 2009
1 parent 315c22d commit cc51226
Show file tree
Hide file tree
Showing 5 changed files with 100 additions and 19 deletions.
3 changes: 3 additions & 0 deletions src/core/pal/labelposition.h
Expand Up @@ -103,6 +103,7 @@ namespace pal
//LabelPosition (int id, double x1, double y1, double w, double h, double cost, Feature *feature);
//LabelPosition (int id, int nbPart, double *x, double *y, double *alpha,

public:
/**
* \brief create a new LabelPosition
*
Expand Down Expand Up @@ -181,6 +182,8 @@ namespace pal
*/
double getY();

double getWidth() { return w; }
double getHeight() { return h; }

/**
* \brief get alpha
Expand Down
96 changes: 79 additions & 17 deletions src/core/pal/pal.cpp
Expand Up @@ -31,14 +31,17 @@
#include <config.h>
#endif

//#define _VERBOSE_
//#define _EXPORT_MAP_
#include <QTime>

#define _CRT_SECURE_NO_DEPRECATE

#include <cstdarg>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cfloat>
#include <ctime>
#include <list>
//#include <geos/geom/Geometry.h>
#include <geos_c.h>
Expand Down Expand Up @@ -114,7 +117,6 @@ namespace pal
std::cout.precision( 12 );
std::cerr.precision( 12 );

tmpTime = 0;
}

std::list<Layer*> *Pal::getLayers()
Expand Down Expand Up @@ -154,8 +156,6 @@ namespace pal
Pal::~Pal()
{

std::cout << "Acces/Concvert time: " << ( double ) tmpTime / CLOCKS_PER_SEC << std::endl;

lyrsMutex->lock();
while ( layers->size() > 0 )
{
Expand Down Expand Up @@ -280,6 +280,9 @@ namespace pal

LinkedList<Feats*> *feats = new LinkedList<Feats*> ( ptrFeatsCompare );

QTime t;
t.start();

if (( ft_ptr->type == GEOS_LINESTRING )
|| ft_ptr->type == GEOS_POLYGON )
{
Expand All @@ -301,8 +304,6 @@ namespace pal
ft_ptr->releaseCoordinates();




if ( inside )
{
// no extra treatment required
Expand Down Expand Up @@ -771,7 +772,6 @@ namespace pal
delete context;
lyrsMutex->unlock();


prob->nbLabelledLayers = labLayers->size();
prob->labelledLayersName = new char*[prob->nbLabelledLayers];
for ( i = 0;i < prob->nbLabelledLayers;i++ )
Expand Down Expand Up @@ -980,13 +980,6 @@ namespace pal
<< prob->nbOverlap << "\t";
#endif

prob->reduce();

#ifdef _VERBOSE_
std::cerr << prob->nblp << "\t"
<< prob->nbOverlap;
#endif

return prob;
}

Expand Down Expand Up @@ -1063,6 +1056,9 @@ namespace pal
<< "height=\"" << convert2pt( bbox[3] - bbox[1], scale, dpi ) << "\">" << std::endl; // TODO xmax ymax
#endif

QTime t;
t.start();

// First, extract the problem
// TODO which is the minimum scale ? (> 0, >= 0, >= 1, >1 )
if ( scale < 1 || ( prob = extract( nbLayers, layersName, layersFactor, bbox[0], bbox[1], bbox[2], bbox[3], scale,
Expand Down Expand Up @@ -1092,6 +1088,19 @@ namespace pal
return new std::list<Label*>();
}

std::cout << "PAL EXTRACT: " << t.elapsed() / 1000.0 << " s" << std::endl;
t.restart();

// reduce number of candidates
// (remove candidates which surely won't be used)
prob->reduce();

#ifdef _VERBOSE_
std::cerr << prob->nblp << "\t"
<< prob->nbOverlap;
#endif


prob->displayAll = displayAll;

#ifdef _VERBOSE_
Expand All @@ -1102,10 +1111,15 @@ namespace pal
#endif

// search a solution
if ( searchMethod != CHAIN )
prob->popmusic();
else
if ( searchMethod == FALP )
prob->init_sol_falp();
else if ( searchMethod == CHAIN )
prob->chain_search();
else
prob->popmusic();

std::cout << "PAL SEARCH (" << searchMethod << "): " << t.elapsed() / 1000.0 << " s" << std::endl;
t.restart();

// Post-Optimization
//prob->post_optimization();
Expand Down Expand Up @@ -1139,6 +1153,51 @@ namespace pal
return solution;
}

Problem* Pal::extractProblem(double scale, double bbox[4])
{
// find out: nbLayers, layersName, layersFactor
lyrsMutex->lock();
int nbLayers = layers->size();

char **layersName = new char*[nbLayers];
double *priorities = new double[nbLayers];
Layer *layer;
int i = 0;
for ( std::list<Layer*>::iterator it = layers->begin(); it != layers->end();it++ )
{
layer = *it;
layersName[i] = layer->name;
priorities[i] = layer->defaultPriority;
i++;
}
lyrsMutex->unlock();

Problem* prob = extract( nbLayers, layersName, priorities, bbox[0], bbox[1], bbox[2], bbox[3], scale, NULL);

delete[] layersName;
delete[] priorities;

return prob;
}

std::list<Label*>* Pal::solveProblem(Problem* prob)
{
if (prob == NULL)
return new std::list<Label*>();

prob->reduce();

if ( searchMethod == FALP )
prob->init_sol_falp();
else if ( searchMethod == CHAIN )
prob->chain_search();
else
prob->popmusic();

return prob->getSolution( false );
}


void Pal::setPointP( int point_p )
{
if ( point_p > 0 )
Expand Down Expand Up @@ -1268,6 +1327,9 @@ namespace pal
ejChainDeg = 50;
candListSize = 0.2;
break;
case FALP:
searchMethod = method;
break;
default:
std::cerr << "Unknown search method..." << std::endl;
}
Expand Down
8 changes: 7 additions & 1 deletion src/core/pal/pal.h
Expand Up @@ -84,7 +84,8 @@ namespace pal
CHAIN = 0, /**< is the worst but fastest method */
POPMUSIC_TABU_CHAIN = 1, /**< is the best but slowest */
POPMUSIC_TABU = 2, /**< is a little bit better than CHAIN but slower*/
POPMUSIC_CHAIN = 3 /**< is slower and best than TABU, worse and faster than TABU_CHAIN */
POPMUSIC_CHAIN = 3, /**< is slower and best than TABU, worse and faster than TABU_CHAIN */
FALP = 4 /** only initial solution */
};

/** Typedef for _Units enumeration */
Expand Down Expand Up @@ -330,6 +331,11 @@ namespace pal
PalStat **stat,
bool displayAll );


Problem* extractProblem(double scale, double bbox[4]);

std::list<Label*>* solveProblem(Problem* prob);

/**
* \brief Set map resolution
*
Expand Down
11 changes: 10 additions & 1 deletion src/core/pal/problem.h
Expand Up @@ -170,20 +170,29 @@ namespace pal
void solution_cost();
void check_solution();

public:
Problem();

//Problem(char *lorena_file, bool displayAll);

~Problem();

/////////////////
// problem inspection functions
int getNumFeatures() { return nbft; }
// features counted 0...n-1
int getFeatureCandidateCount(int i) { return featNbLp[i]; }
// both features and candidates counted 0..n-1
LabelPosition* getFeatureCandidate(int fi, int ci) { return labelpositions[ featStartId[fi] + ci]; }
/////////////////


void reduce();


void post_optimization();



/**
* \brief popmusic framework
*/
Expand Down
1 change: 1 addition & 0 deletions src/core/pal/util.cpp
Expand Up @@ -467,6 +467,7 @@ namespace pal
// ignore invalid geometries (e.g. polygons with self-intersecting rings)
if (check_valid && GEOSisValid( geom ) != 1) // 0=invalid, 1=valid, 2=exception
{
std::cerr << "ignoring invalid feature " << geom_id << std::endl;
continue;
}

Expand Down

0 comments on commit cc51226

Please sign in to comment.