52 delete[] chain->
label;
58 : mAllCandidatesIndex( extent )
59 , mActiveCandidatesIndex( extent )
76 bool *ok =
new bool[mTotalCandidates];
79 for ( i = 0; i < mTotalCandidates; i++ )
90 for ( i = 0; i < static_cast< int >( mFeatureCount ); i++ )
93 for ( j = 0; j < mFeatNbLp[i]; j++ )
95 if ( !ok[mFeatStartId[i] + j] )
97 if ( mLabelPositions.at( mFeatStartId[i] + j )->getNumOverlaps() == 0 )
100 ok[mFeatStartId[i] + j] =
true;
103 counter += mFeatNbLp[i] - j - 1;
105 for ( k = j + 1; k < mFeatNbLp[i]; k++ )
108 lpid = mFeatStartId[i] + k;
110 lp2 = mLabelPositions[lpid ].get();
115 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2](
const LabelPosition * lp ) ->
bool 128 mFeatNbLp[i] = j + 1;
136 this->mTotalCandidates -= counter;
167 mSol.init( mFeatureCount );
176 for (
int i = 0; i < static_cast< int >( mFeatureCount ); i++ )
177 for (
int j = 0; j < mFeatNbLp[i]; j++ )
179 label = mFeatStartId[i] + j;
182 list.
insert( label, mLabelPositions.at( label )->getNumOverlaps() );
192 if (
pal->isCanceled() )
199 lp = mLabelPositions[ label ].get();
201 if ( lp->
getId() != label )
207 mSol.activeLabelIds[probFeatId] = label;
209 for (
int i = mFeatStartId[probFeatId]; i < mFeatStartId[probFeatId] + mFeatNbLp[probFeatId]; i++ )
211 ignoreLabel( mLabelPositions[ i ].
get(), list, mAllCandidatesIndex );
217 std::vector< const LabelPosition * > conflictingPositions;
218 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions](
const LabelPosition * lp2 ) ->
bool 222 conflictingPositions.emplace_back( lp2 );
229 ignoreLabel( conflict, list, mAllCandidatesIndex );
232 mActiveCandidatesIndex.insert( lp,
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
242 for ( std::size_t i = 0; i < mFeatureCount; i++ )
244 if ( mSol.activeLabelIds[i] == -1 )
246 nbOverlap = std::numeric_limits<int>::max();
247 start_p = mFeatStartId[i];
248 for ( p = 0; p < mFeatNbLp[i]; p++ )
250 lp = mLabelPositions[ start_p + p ].get();
256 mActiveCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp](
const LabelPosition * lp2 )->
bool 271 mSol.activeLabelIds[i] = retainedLabel->
getId();
280 inline Chain *Problem::chain(
int seed )
286 double delta_best = std::numeric_limits<double>::max();
291 Chain *retainedChain =
nullptr;
293 int max_degree =
pal->mEjChainDeg;
297 QLinkedList<ElemTrans *> currentChain;
298 QLinkedList<int> conflicts;
300 std::vector< int > tmpsol( mSol.activeLabelIds );
310 seedNbLp = mFeatNbLp[seed];
311 delta_min = std::numeric_limits<double>::max();
317 if ( tmpsol[seed] == -1 )
318 delta -= mInactiveCost[seed];
320 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
322 for (
int i = -1; i < seedNbLp; i++ )
327 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFeatStartId[seed] != tmpsol[seed] )
331 lid = mFeatStartId[seed] + i;
334 lp = mLabelPositions[ lid ].get();
339 mActiveCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, ¤tChain,
this](
const LabelPosition * lp2 ) ->
bool 346 QLinkedList< ElemTrans * >::iterator cur;
347 for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
349 if ( ( *cur )->feat == feat )
355 if ( !conflicts.contains( feat ) )
357 conflicts.append( feat );
358 delta_tmp += lp2->
cost() + mInactiveCost[feat];
365 if ( conflicts.isEmpty() )
367 if ( !retainedChain || delta + lp->
cost() < delta_best )
371 delete[] retainedChain->
label;
372 delete[] retainedChain->
feat;
376 retainedChain =
new Chain();
379 delta_best = delta + lp->
cost();
381 retainedChain->
degree = currentChain.size() + 1;
382 retainedChain->
feat =
new int[retainedChain->
degree];
383 retainedChain->
label =
new int[retainedChain->
degree];
384 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
387 while ( current != currentChain.end() )
390 retainedChain->
feat[j] = move->
feat;
395 retainedChain->
feat[j] = seed;
396 retainedChain->
label[j] = lid;
397 retainedChain->
delta = delta + lp->
cost();
402 else if ( conflicts.size() == 1 )
404 if ( delta_tmp < delta_min )
406 delta_min = delta_tmp;
408 next_seed = conflicts.takeFirst();
412 conflicts.takeFirst();
420 newChain->
degree = currentChain.size() + 1 + conflicts.size();
423 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
427 while ( current != currentChain.end() )
437 newChain->
feat[j] = seed;
438 newChain->
label[j] = lid;
439 newChain->
delta = delta + mLabelPositions.at( newChain->
label[j] )->cost();
443 while ( !conflicts.isEmpty() )
445 int ftid = conflicts.takeFirst();
446 newChain->
feat[j] = ftid;
447 newChain->
label[j] = -1;
448 newChain->
delta += mInactiveCost[ftid];
452 if ( newChain->
delta < delta_best )
457 delta_best = newChain->
delta;
458 retainedChain = newChain;
469 if ( !retainedChain || delta + mInactiveCost[seed] < delta_best )
473 delete[] retainedChain->
label;
474 delete[] retainedChain->
feat;
477 retainedChain =
new Chain();
479 delta_best = delta + mInactiveCost[seed];
481 retainedChain->
degree = currentChain.size() + 1;
482 retainedChain->
feat =
new int[retainedChain->
degree];
483 retainedChain->
label =
new int[retainedChain->
degree];
484 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
487 while ( current != currentChain.end() )
490 retainedChain->
feat[j] = move->
feat;
495 retainedChain->
feat[j] = seed;
496 retainedChain->
label[j] = -1;
497 retainedChain->
delta = delta + mInactiveCost[seed];
508 if ( next_seed == -1 )
512 else if ( currentChain.size() > max_degree )
523 currentChain.append( et );
527 mLabelPositions.at( et->
old_label )->removeFromIndex( mActiveCandidatesIndex );
532 mLabelPositions.at( et->
new_label )->insertIntoIndex( mActiveCandidatesIndex );
536 tmpsol[seed] = retainedLabel;
537 delta += mLabelPositions.at( retainedLabel )->cost();
542 while ( !currentChain.isEmpty() )
544 std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
546 if ( et->new_label != -1 )
548 mLabelPositions.at( et->new_label )->removeFromIndex( mActiveCandidatesIndex );
551 if ( et->old_label != -1 )
553 mLabelPositions.at( et->old_label )->insertIntoIndex( mActiveCandidatesIndex );
557 return retainedChain;
563 if ( mFeatureCount == 0 )
568 bool *ok =
new bool[mFeatureCount];
573 Chain *retainedChain =
nullptr;
575 std::fill( ok, ok + mFeatureCount,
false );
593 for ( seed = ( iter + 1 ) % mFeatureCount;
594 ok[seed] && seed != iter;
595 seed = ( seed + 1 ) % mFeatureCount )
604 iter = ( iter + 1 ) % mFeatureCount;
605 retainedChain = chain( seed );
607 if ( retainedChain && retainedChain->
delta < -
EPSILON )
610 for ( i = 0; i < retainedChain->
degree; i++ )
612 fid = retainedChain->
feat[i];
613 lid = retainedChain->
label[i];
615 if ( mSol.activeLabelIds[fid] >= 0 )
617 LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
620 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old](
const LabelPosition * lp ) ->
bool 631 mSol.activeLabelIds[fid] = lid;
633 if ( mSol.activeLabelIds[fid] >= 0 )
635 mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex );
640 mSol.totalCost += retainedChain->
delta;
658 QList<LabelPosition *> solList;
660 for ( std::size_t i = 0; i < mFeatureCount; i++ )
662 if ( mSol.activeLabelIds[i] != -1 )
664 solList.push_back( mLabelPositions[ mSol.activeLabelIds[i] ].get() );
666 else if ( returnInactive
667 || ( mFeatStartId[i] < static_cast< int >( mLabelPositions.size() ) &&
668 ( mLabelPositions.at( mFeatStartId[i] )->getFeaturePart()->layer()->displayAll()
669 || mLabelPositions.at( mFeatStartId[i] )->getFeaturePart()->alwaysShow() ) ) )
671 solList.push_back( mLabelPositions[ mFeatStartId[i] ].
get() );
673 else if ( unlabeled )
675 if ( mFeatStartId[i] < static_cast< int >( mLabelPositions.size() ) )
676 unlabeled->push_back( mLabelPositions[ mFeatStartId[i] ].
get() );
683 for (
const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
684 unlabeled->append( position.get() );
690 void Problem::solution_cost()
692 mSol.totalCost = 0.0;
699 for ( std::size_t i = 0; i < mFeatureCount; i++ )
701 if ( mSol.activeLabelIds[i] == -1 )
703 mSol.totalCost += mInactiveCost[i];
707 lp = mLabelPositions[ mSol.activeLabelIds[i] ].get();
710 mActiveCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp,
this](
const LabelPosition * lp2 )->
bool 720 mSol.totalCost += lp->
cost();
A rectangle specified with double values.
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
Thrown when something is added in a Full set.
bool isInConflict(const LabelPosition *ls) const
Check whether or not this overlap with another labelPosition.
int getProblemFeatureId() const
A rtree spatial index for use in the pal labeling engine.
Problem(const QgsRectangle &extent)
Constructor for Problem.
double cost() const
Returns the candidate label position's geographical cost.
bool intersects(const QgsRectangle &bounds, const std::function< bool(T *data)> &callback) const
Performs an intersection check against the index, for data intersecting the specified bounds...
void chain_search()
Test with very-large scale neighborhood.
void decrementNumOverlaps()
Decreases the number of overlaps recorded against this position by 1.
void insert(int key, double p)
int getId() const
Returns the id.
void incrementNumOverlaps()
Increases the number of overlaps recorded against this position by 1.
int getNumOverlaps() const
void delete_chain(Chain *chain)
void ignoreLabel(const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelPosition > &candidatesIndex)
LabelPosition is a candidate feature label position.
QList< LabelPosition * > getSolution(bool returnInactive, QList< LabelPosition *> *unlabeled=nullptr)
Solves the labeling problem, selecting the best candidate locations for all labels and returns a list...
void removeFromIndex(PalRtree< LabelPosition > &index)
Removes the label position from the specified index.
void insertIntoIndex(PalRtree< LabelPosition > &index)
Inserts the label position into the specified index.
void decreaseKey(int key)