Skip to content

Commit

Permalink
Also draw unlabel features which correspond to features where no
Browse files Browse the repository at this point in the history 
candidates could be generated

E.g. lines too short for label, polygons too small for labels

(and fix some gross oldschool memory management)
  • Loading branch information
@nyalldawson
nyalldawson committed Jul 21, 2019
1 parent bae321a commit 2a829f0
Show file tree
Hide file tree
Showing 5 changed files with 157 additions and 124 deletions.
31 changes: 27 additions & 4 deletions src/core/pal/feature.cpp
View file
Expand Up @@ -300,6 +300,29 @@ int FeaturePart::createCandidatesOverPoint( double x, double y, QList< LabelPosi
return nbp;
}

std::unique_ptr<LabelPosition> FeaturePart::createCandidatePointOnSurface( PointSet *mapShape )
{
double px, py;
try
{
GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
geos::unique_ptr pointGeom( GEOSPointOnSurface_r( geosctxt, mapShape->geos() ) );
if ( pointGeom )
{
const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
}
}
catch ( GEOSException &e )
{
QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
return nullptr;
}

return qgis::make_unique< LabelPosition >( 0, px, py, getLabelWidth(), getLabelHeight(), 0.0, 0.0, this );
}

int FeaturePart::createCandidatesAtOrderedPositionsOverPoint( double x, double y, QList<LabelPosition *> &lPos, double angle )
{
QVector< QgsPalLayerSettings::PredefinedPointPosition > positions = mLF->predefinedPositionOrder();
Expand Down Expand Up @@ -1534,10 +1557,10 @@ int FeaturePart::createCandidatesForPolygon( QList< LabelPosition *> &lPos, Poin
return nbp;
}

int FeaturePart::createCandidates( QList< LabelPosition *> &lPos,
const GEOSPreparedGeometry *mapBoundary,
PointSet *mapShape, RTree<LabelPosition *, double, 2, double> *candidates )
QList<LabelPosition *> FeaturePart::createCandidates( const GEOSPreparedGeometry *mapBoundary,
PointSet *mapShape, RTree<LabelPosition *, double, 2, double> *candidates )
{
QList<LabelPosition *> lPos;
double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;

if ( mLF->hasFixedPosition() )
Expand Down Expand Up @@ -1612,7 +1635,7 @@ int FeaturePart::createCandidates( QList< LabelPosition *> &lPos,
}

std::sort( lPos.begin(), lPos.end(), CostCalculator::candidateSortGrow );
return lPos.count();
return lPos;
}

void FeaturePart::addSizePenalty( int nbp, QList< LabelPosition * > &lPos, double bbx[4], double bby[4] )
Expand Down
13 changes: 10 additions & 3 deletions src/core/pal/feature.h
View file
Expand Up @@ -129,13 +129,12 @@ namespace pal

/**
* Generic method to generate label candidates for the feature.
* \param lPos pointer to an array of candidates, will be filled by generated candidates
* \param mapBoundary map boundary geometry
* \param mapShape generate candidates for this spatial entity
* \param candidates index for candidates
* \returns the number of candidates generated in lPos
* \returns a list of generated candidates positions
*/
int createCandidates( QList<LabelPosition *> &lPos, const GEOSPreparedGeometry *mapBoundary, PointSet *mapShape, RTree<LabelPosition *, double, 2, double> *candidates );
QList<LabelPosition *> createCandidates( const GEOSPreparedGeometry *mapBoundary, PointSet *mapShape, RTree<LabelPosition *, double, 2, double> *candidates );

/**
* Generate candidates for point feature, located around a specified point.
Expand All @@ -157,6 +156,14 @@ namespace pal
*/
int createCandidatesOverPoint( double x, double y, QList<LabelPosition *> &lPos, double angle );

/**
* Creates a single candidate using the "point on sruface" algorithm.
*
* \note Unlike the other create candidates methods, this method
* bypasses the usual candidate filtering steps and ALWAYS returns a single candidate.
*/
std::unique_ptr< LabelPosition > createCandidatePointOnSurface( PointSet *mapShape );

/**
* Generates candidates following a prioritized list of predefined positions around a point.
* \param x x coordinate of the point
Expand Down
213 changes: 101 additions & 112 deletions src/core/pal/pal.cpp
View file
Expand Up @@ -119,6 +119,7 @@ typedef struct _featCbackCtx
QLinkedList<Feats *> *fFeats;
RTree<FeaturePart *, double, 2, double> *obstacles;
RTree<LabelPosition *, double, 2, double> *candidates;
QList<LabelPosition *> *positionsWithNoCandidates;
const GEOSPreparedGeometry *mapBoundary = nullptr;
} FeatCallBackCtx;

Expand Down Expand Up @@ -147,8 +148,8 @@ bool extractFeatCallback( FeaturePart *ft_ptr, void *ctx )
}

// generate candidates for the feature part
QList< LabelPosition * > lPos;
if ( ft_ptr->createCandidates( lPos, context->mapBoundary, ft_ptr, context->candidates ) )
const QList< LabelPosition * > lPos = ft_ptr->createCandidates( context->mapBoundary, ft_ptr, context->candidates );
if ( !lPos.empty() )
{
// valid features are added to fFeats
Feats *ft = new Feats();
Expand All @@ -160,8 +161,10 @@ bool extractFeatCallback( FeaturePart *ft_ptr, void *ctx )
}
else
{
// Others are deleted
qDeleteAll( lPos );
// features with no candidates are recorded in the unlabeled feature list
std::unique_ptr< LabelPosition > unplacedPosition = ft_ptr->createCandidatePointOnSurface( ft_ptr );
if ( unplacedPosition )
context->positionsWithNoCandidates->append( unplacedPosition.release() );
}

return true;
Expand Down Expand Up @@ -219,8 +222,7 @@ bool filteringCallback( FeaturePart *featurePart, void *ctx )
std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeometry &mapBoundary )
{
// to store obstacles
RTree<FeaturePart *, double, 2, double> *obstacles = new RTree<FeaturePart *, double, 2, double>();

RTree<FeaturePart *, double, 2, double> obstacles;
std::unique_ptr< Problem > prob = qgis::make_unique< Problem >();

int i, j;
Expand All @@ -242,21 +244,22 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom

prob->pal = this;

QLinkedList<Feats *> *fFeats = new QLinkedList<Feats *>;
QLinkedList<Feats *> fFeats;

FeatCallBackCtx context;

// prepare map boundary
geos::unique_ptr mapBoundaryGeos( QgsGeos::asGeos( mapBoundary ) );
geos::prepared_unique_ptr mapBoundaryPrepared( GEOSPrepare_r( QgsGeos::getGEOSHandler(), mapBoundaryGeos.get() ) );

context.fFeats = fFeats;
context.obstacles = obstacles;
context.fFeats = &fFeats;
context.obstacles = &obstacles;
context.candidates = prob->candidates;
context.positionsWithNoCandidates = prob->positionsWithNoCandidates();
context.mapBoundary = mapBoundaryPrepared.get();

ObstacleCallBackCtx obstacleContext;
obstacleContext.obstacles = obstacles;
obstacleContext.obstacles = &obstacles;
obstacleContext.obstacleCount = 0;

// first step : extract features from layers
Expand Down Expand Up @@ -308,138 +311,124 @@ std::unique_ptr<Problem> Pal::extract( const QgsRectangle &extent, const QgsGeom
prob->nbLabelledLayers = layersWithFeaturesInBBox.size();
prob->labelledLayersName = layersWithFeaturesInBBox;

if ( fFeats->isEmpty() )
{
delete fFeats;
delete obstacles;
return nullptr;
}

prob->nbft = fFeats->size();
prob->nbft = fFeats.size();
prob->nblp = 0;
prob->featNbLp = new int [prob->nbft];
prob->featStartId = new int [prob->nbft];
prob->inactiveCost = new double[prob->nbft];

Feats *feat = nullptr;

// Filtering label positions against obstacles
amin[0] = amin[1] = std::numeric_limits<double>::lowest();
amax[0] = amax[1] = std::numeric_limits<double>::max();
FilterContext filterCtx;
filterCtx.cdtsIndex = prob->candidates;
filterCtx.pal = this;
obstacles->Search( amin, amax, filteringCallback, static_cast< void * >( &filterCtx ) );

if ( isCanceled() )
{
const auto constFFeats = *fFeats;
for ( Feats *feat : constFFeats )
{
qDeleteAll( feat->lPos );
feat->lPos.clear();
}

qDeleteAll( *fFeats );
delete fFeats;
delete obstacles;
return nullptr;
}

int idlp = 0;
for ( i = 0; i < prob->nbft; i++ ) /* foreach feature into prob */
if ( !fFeats.isEmpty() )
{
feat = fFeats->takeFirst();
Feats *feat = nullptr;

prob->featStartId[i] = idlp;
prob->inactiveCost[i] = std::pow( 2, 10 - 10 * feat->priority );
// Filtering label positions against obstacles
amin[0] = amin[1] = std::numeric_limits<double>::lowest();
amax[0] = amax[1] = std::numeric_limits<double>::max();
FilterContext filterCtx;
filterCtx.cdtsIndex = prob->candidates;
filterCtx.pal = this;
obstacles.Search( amin, amax, filteringCallback, static_cast< void * >( &filterCtx ) );

switch ( feat->feature->getGeosType() )
if ( isCanceled() )
{
case GEOS_POINT:
max_p = point_p;
break;
case GEOS_LINESTRING:
max_p = line_p;
break;
case GEOS_POLYGON:
max_p = poly_p;
break;
}
for ( Feats *feat : qgis::as_const( fFeats ) )
{
qDeleteAll( feat->lPos );
feat->lPos.clear();
}

// sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
max_p = CostCalculator::finalizeCandidatesCosts( feat, max_p, obstacles, bbx, bby );
qDeleteAll( fFeats );
return nullptr;
}

// only keep the 'max_p' best candidates
while ( feat->lPos.count() > max_p )
int idlp = 0;
for ( i = 0; i < prob->nbft; i++ ) /* foreach feature into prob */
{
// TODO remove from index
feat->lPos.last()->removeFromIndex( prob->candidates );
delete feat->lPos.takeLast();
}
feat = fFeats.takeFirst();

// update problem's # candidate
prob->featNbLp[i] = feat->lPos.count();
prob->nblp += feat->lPos.count();
prob->featStartId[i] = idlp;
prob->inactiveCost[i] = std::pow( 2, 10 - 10 * feat->priority );

// add all candidates into a rtree (to speed up conflicts searching)
for ( j = 0; j < feat->lPos.count(); j++, idlp++ )
{
lp = feat->lPos.at( j );
//lp->insertIntoIndex(prob->candidates);
lp->setProblemIds( i, idlp ); // bugfix #1 (maxence 10/23/2008)
}
fFeats->append( feat );
}
switch ( feat->feature->getGeosType() )
{
case GEOS_POINT:
max_p = point_p;
break;
case GEOS_LINESTRING:
max_p = line_p;
break;
case GEOS_POLYGON:
max_p = poly_p;
break;
}

int nbOverlaps = 0;
// sort candidates by cost, skip less interesting ones, calculate polygon costs (if using polygons)
max_p = CostCalculator::finalizeCandidatesCosts( feat, max_p, &obstacles, bbx, bby );

while ( !fFeats->isEmpty() ) // foreach feature
{
if ( isCanceled() )
{
const auto constFFeats = *fFeats;
for ( Feats *feat : constFFeats )
// only keep the 'max_p' best candidates
while ( feat->lPos.count() > max_p )
{
qDeleteAll( feat->lPos );
feat->lPos.clear();
// TODO remove from index
feat->lPos.constLast()->removeFromIndex( prob->candidates );
delete feat->lPos.takeLast();
}

qDeleteAll( *fFeats );
delete fFeats;
delete obstacles;
return nullptr;
// update problem's # candidate
prob->featNbLp[i] = feat->lPos.count();
prob->nblp += feat->lPos.count();

// add all candidates into a rtree (to speed up conflicts searching)
for ( j = 0; j < feat->lPos.count(); j++, idlp++ )
{
lp = feat->lPos.at( j );
//lp->insertIntoIndex(prob->candidates);
lp->setProblemIds( i, idlp ); // bugfix #1 (maxence 10/23/2008)
}
fFeats.append( feat );
}

feat = fFeats->takeFirst();
while ( !feat->lPos.isEmpty() ) // foreach label candidate
int nbOverlaps = 0;

while ( !fFeats.isEmpty() ) // foreach feature
{
lp = feat->lPos.takeFirst();
lp->resetNumOverlaps();
if ( isCanceled() )
{
for ( Feats *feat : qgis::as_const( fFeats ) )
{
qDeleteAll( feat->lPos );
feat->lPos.clear();
}

qDeleteAll( fFeats );
return nullptr;
}

// make sure that candidate's cost is less than 1
lp->validateCost();
feat = fFeats.takeFirst();
while ( !feat->lPos.isEmpty() ) // foreach label candidate
{
lp = feat->lPos.takeFirst();
lp->resetNumOverlaps();

// make sure that candidate's cost is less than 1
lp->validateCost();

prob->addCandidatePosition( lp );
//prob->feat[idlp] = j;
prob->addCandidatePosition( lp );
//prob->feat[idlp] = j;

lp->getBoundingBox( amin, amax );
lp->getBoundingBox( amin, amax );

// lookup for overlapping candidate
prob->candidates->Search( amin, amax, LabelPosition::countOverlapCallback, static_cast< void * >( lp ) );
// lookup for overlapping candidate
prob->candidates->Search( amin, amax, LabelPosition::countOverlapCallback, static_cast< void * >( lp ) );

nbOverlaps += lp->getNumOverlaps();
nbOverlaps += lp->getNumOverlaps();
}
delete feat;
}
delete feat;
nbOverlaps /= 2;
prob->all_nblp = prob->nblp;
prob->nbOverlap = nbOverlaps;
}
delete fFeats;

//delete candidates;
delete obstacles;

nbOverlaps /= 2;
prob->all_nblp = prob->nblp;
prob->nbOverlap = nbOverlaps;

return prob;
}
Expand Down

0 comments on commit 2a829f0

Please sign in to comment.