52 delete[] chain->
label;
58 : mAllCandidatesIndex( extent )
59 , mActiveCandidatesIndex( extent )
76 bool *ok =
new bool[mTotalCandidates];
79 for ( i = 0; i < mTotalCandidates; i++ )
89 if (
pal->isCanceled() )
93 for ( i = 0; i < static_cast< int >( mFeatureCount ); i++ )
95 if (
pal->isCanceled() )
99 for ( j = 0; j < mFeatNbLp[i]; j++ )
101 if ( !ok[mFeatStartId[i] + j] )
103 if ( mLabelPositions.at( mFeatStartId[i] + j )->getNumOverlaps() == 0 )
106 ok[mFeatStartId[i] + j] =
true;
109 counter += mFeatNbLp[i] - j - 1;
111 for ( k = j + 1; k < mFeatNbLp[i]; k++ )
114 lpid = mFeatStartId[i] + k;
116 lp2 = mLabelPositions[lpid ].get();
121 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2,
this](
const LabelPosition * lp ) ->
bool
123 if ( candidatesAreConflicting( lp2, lp ) )
134 mFeatNbLp[i] = j + 1;
142 this->mTotalCandidates -= counter;
157 if ( lp2->
getId() != lp->
getId() && list.
isIn( lp2->
getId() ) && candidatesAreConflicting( lp2, lp ) )
173 mSol.init( mFeatureCount );
182 for (
int i = 0; i < static_cast< int >( mFeatureCount ); i++ )
183 for (
int j = 0; j < mFeatNbLp[i]; j++ )
185 label = mFeatStartId[i] + j;
188 list.
insert( label, mLabelPositions.at( label )->getNumOverlaps() );
198 if (
pal->isCanceled() )
205 lp = mLabelPositions[ label ].get();
207 if ( lp->
getId() != label )
213 mSol.activeLabelIds[probFeatId] = label;
215 for (
int i = mFeatStartId[probFeatId]; i < mFeatStartId[probFeatId] + mFeatNbLp[probFeatId]; i++ )
217 ignoreLabel( mLabelPositions[ i ].get(), list, mAllCandidatesIndex );
223 std::vector< const LabelPosition * > conflictingPositions;
224 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions,
this](
const LabelPosition * lp2 ) ->
bool
226 if ( candidatesAreConflicting( lp, lp2 ) )
228 conflictingPositions.emplace_back( lp2 );
235 ignoreLabel( conflict, list, mAllCandidatesIndex );
238 mActiveCandidatesIndex.insert( lp,
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
248 for ( std::size_t i = 0; i < mFeatureCount; i++ )
250 if ( mSol.activeLabelIds[i] == -1 )
252 nbOverlap = std::numeric_limits<int>::max();
253 start_p = mFeatStartId[i];
254 for ( p = 0; p < mFeatNbLp[i]; p++ )
256 lp = mLabelPositions[ start_p + p ].get();
262 mActiveCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp,
this](
const LabelPosition * lp2 )->
bool
264 if ( candidatesAreConflicting( lp, lp2 ) )
277 mSol.activeLabelIds[i] = retainedLabel->
getId();
288 return pal->candidatesAreConflicting( lp1, lp2 );
291inline Chain *Problem::chain(
int seed )
297 double delta_best = std::numeric_limits<double>::max();
302 Chain *retainedChain =
nullptr;
304 const int max_degree =
pal->mEjChainDeg;
308 QLinkedList<ElemTrans *> currentChain;
309 QLinkedList<int> conflicts;
311 std::vector< int > tmpsol( mSol.activeLabelIds );
321 seedNbLp = mFeatNbLp[seed];
322 delta_min = std::numeric_limits<double>::max();
328 if ( tmpsol[seed] == -1 )
329 delta -= mInactiveCost[seed];
331 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
333 for (
int i = -1; i < seedNbLp; i++ )
338 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFeatStartId[seed] != tmpsol[seed] )
342 lid = mFeatStartId[seed] + i;
345 lp = mLabelPositions[ lid ].get();
350 mActiveCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, ¤tChain,
this](
const LabelPosition * lp2 ) ->
bool
352 if ( candidatesAreConflicting( lp2, lp ) )
357 QLinkedList< ElemTrans * >::iterator cur;
358 for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
360 if ( ( *cur )->feat == feat )
366 if ( !conflicts.contains( feat ) )
368 conflicts.append( feat );
369 delta_tmp += lp2->cost() + mInactiveCost[feat];
376 if ( conflicts.isEmpty() )
378 if ( !retainedChain || delta + lp->
cost() < delta_best )
382 delete[] retainedChain->
label;
383 delete[] retainedChain->
feat;
387 retainedChain =
new Chain();
390 delta_best = delta + lp->
cost();
392 retainedChain->
degree = currentChain.size() + 1;
393 retainedChain->
feat =
new int[retainedChain->
degree];
394 retainedChain->
label =
new int[retainedChain->
degree];
395 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
398 while ( current != currentChain.end() )
401 retainedChain->
feat[j] = move->
feat;
406 retainedChain->
feat[j] = seed;
407 retainedChain->
label[j] = lid;
408 retainedChain->
delta = delta + lp->
cost();
413 else if ( conflicts.size() == 1 )
415 if ( delta_tmp < delta_min )
417 delta_min = delta_tmp;
419 next_seed = conflicts.takeFirst();
423 conflicts.takeFirst();
431 newChain->
degree = currentChain.size() + 1 + conflicts.size();
434 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
438 while ( current != currentChain.end() )
448 newChain->
feat[j] = seed;
449 newChain->
label[j] = lid;
450 newChain->
delta = delta + mLabelPositions.at( newChain->
label[j] )->cost();
454 while ( !conflicts.isEmpty() )
456 const int ftid = conflicts.takeFirst();
457 newChain->
feat[j] = ftid;
458 newChain->
label[j] = -1;
459 newChain->
delta += mInactiveCost[ftid];
463 if ( newChain->
delta < delta_best )
468 delta_best = newChain->
delta;
469 retainedChain = newChain;
480 if ( !retainedChain || delta + mInactiveCost[seed] < delta_best )
484 delete[] retainedChain->
label;
485 delete[] retainedChain->
feat;
488 retainedChain =
new Chain();
490 delta_best = delta + mInactiveCost[seed];
492 retainedChain->
degree = currentChain.size() + 1;
493 retainedChain->
feat =
new int[retainedChain->
degree];
494 retainedChain->
label =
new int[retainedChain->
degree];
495 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
498 while ( current != currentChain.end() )
501 retainedChain->
feat[j] = move->
feat;
506 retainedChain->
feat[j] = seed;
507 retainedChain->
label[j] = -1;
508 retainedChain->
delta = delta + mInactiveCost[seed];
519 if ( next_seed == -1 )
523 else if ( currentChain.size() > max_degree )
534 currentChain.append( et );
538 mLabelPositions.at( et->
old_label )->removeFromIndex( mActiveCandidatesIndex );
543 mLabelPositions.at( et->
new_label )->insertIntoIndex( mActiveCandidatesIndex );
547 tmpsol[seed] = retainedLabel;
549 delta += mLabelPositions.at( retainedLabel )->cost();
554 while ( !currentChain.isEmpty() )
556 std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
560 mLabelPositions.at( et->
new_label )->removeFromIndex( mActiveCandidatesIndex );
565 mLabelPositions.at( et->
old_label )->insertIntoIndex( mActiveCandidatesIndex );
569 return retainedChain;
575 if ( mFeatureCount == 0 )
580 bool *ok =
new bool[mFeatureCount];
585 Chain *retainedChain =
nullptr;
587 std::fill( ok, ok + mFeatureCount,
false );
598 for ( seed = ( iter + 1 ) % mFeatureCount;
599 ok[seed] && seed != iter;
600 seed = ( seed + 1 ) % mFeatureCount )
609 iter = ( iter + 1 ) % mFeatureCount;
610 retainedChain = chain( seed );
612 if ( retainedChain && retainedChain->
delta < -
EPSILON )
615 for ( i = 0; i < retainedChain->
degree; i++ )
617 fid = retainedChain->
feat[i];
618 lid = retainedChain->
label[i];
620 if ( mSol.activeLabelIds[fid] >= 0 )
622 LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
625 mAllCandidatesIndex.intersects(
QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old,
this](
const LabelPosition * lp ) ->
bool
627 if ( candidatesAreConflicting( old, lp ) )
636 mSol.activeLabelIds[fid] = lid;
638 if ( mSol.activeLabelIds[fid] >= 0 )
640 mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex );
661 QList<LabelPosition *> finalLabelPlacements;
662 finalLabelPlacements.reserve( mFeatureCount );
665 for ( std::size_t i = 0; i < mFeatureCount; i++ )
667 const int labelId = mSol.activeLabelIds[i];
668 const bool foundNonOverlappingPlacement = labelId != -1;
669 const int startIndexForLabelPlacements = mFeatStartId[i];
670 const bool foundCandidatesForFeature = startIndexForLabelPlacements < static_cast< int >( mLabelPositions.size() );
672 if ( foundNonOverlappingPlacement )
674 finalLabelPlacements.push_back( mLabelPositions[ labelId ].get() );
676 else if ( foundCandidatesForFeature &&
679 || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->alwaysShow() ) )
681 finalLabelPlacements.push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
683 else if ( unlabeled )
686 if ( foundCandidatesForFeature && ( i == mFeatureCount - 1 || startIndexForLabelPlacements != mFeatStartId[i + 1] ) )
687 unlabeled->push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
694 unlabeled->reserve( mPositionsWithNoCandidates.size() );
695 for (
const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
696 unlabeled->append( position.get() );
699 return finalLabelPlacements;
A rtree spatial index for use in the pal labeling engine.
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.
@ AllowOverlapIfRequired
Avoids overlapping labels when possible, but permit overlaps if labels for features cannot otherwise ...
A rectangle specified with double values.
Contains information about the context of a rendering operation.
Thrown when something is added in a Full set.
LabelPosition is a candidate feature label position.
void incrementNumOverlaps()
Increases the number of overlaps recorded against this position by 1.
void removeFromIndex(PalRtree< LabelPosition > &index)
Removes the label position from the specified index.
void decrementNumOverlaps()
Decreases the number of overlaps recorded against this position by 1.
int getId() const
Returns the id.
double cost() const
Returns the candidate label position's geographical cost.
int getNumOverlaps() const
int getProblemFeatureId() const
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
void insertIntoIndex(PalRtree< LabelPosition > &index)
Inserts the label position into the specified index.
Custom priority queue for use in pal labeling engine.
void decreaseKey(int key)
void insert(int key, double p)
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 chainSearch(QgsRenderContext &context)
Test with very-large scale neighborhood.
void delete_chain(Chain *chain)