52 delete[] chain->
label;
58 : mAllCandidatesIndex( extent )
59 , mActiveCandidatesIndex( extent )
66 mLabelPositions.emplace_back( std::move( position ) );
79 std::vector<bool> ok( mTotalCandidates,
false );
85 if (
pal->isCanceled() )
89 for ( std::size_t feature = 0; feature < mFeatureCount; feature++ )
91 if (
pal->isCanceled() )
95 const int totalCandidatesForFeature = mCandidateCountForFeature[feature];
96 for (
int candidateIndex = 0; candidateIndex < totalCandidatesForFeature; candidateIndex++ )
98 if ( !ok[mFirstCandidateIndexForFeature[feature] + candidateIndex] )
100 if ( mLabelPositions.at( mFirstCandidateIndexForFeature[feature] + candidateIndex )->getNumOverlaps() == 0 )
103 ok[mFirstCandidateIndexForFeature[feature] + candidateIndex] =
true;
106 counter += totalCandidatesForFeature - candidateIndex - 1;
108 for ( k = candidateIndex + 1; k < totalCandidatesForFeature; k++ )
111 lpid = mFirstCandidateIndexForFeature[feature] + k;
113 lp2 = mLabelPositions[lpid ].get();
118 mAllCandidatesIndex.intersects( searchBounds, [&lp2,
this](
const LabelPosition * lp ) ->
bool
120 if ( candidatesAreConflicting( lp2, lp ) )
131 mCandidateCountForFeature[feature] = candidateIndex + 1;
142 this->mTotalCandidates -= counter;
154 if ( lp2->
getId() != lp->
getId() && list.
isIn( lp2->
getId() ) && candidatesAreConflicting( lp2, lp ) )
170 mSol.init( mFeatureCount );
176 for (
int feature = 0; feature < static_cast< int >( mFeatureCount ); feature++ )
178 const int totalCandidatesForFeature = mCandidateCountForFeature[feature];
179 for (
int candidateIndex = 0; candidateIndex < totalCandidatesForFeature; candidateIndex++ )
181 label = mFirstCandidateIndexForFeature[feature] + candidateIndex;
184 list.
insert( label, mLabelPositions.at( label )->getNumOverlaps() );
195 if (
pal->isCanceled() )
202 lp = mLabelPositions[ label ].get();
204 if ( lp->
getId() != label )
210 mSol.activeLabelIds[probFeatId] = label;
212 for (
int candidateIndex = mFirstCandidateIndexForFeature[probFeatId]; candidateIndex < mFirstCandidateIndexForFeature[probFeatId] + mCandidateCountForFeature[probFeatId]; candidateIndex++ )
214 ignoreLabel( mLabelPositions[ candidateIndex ].get(), list, mAllCandidatesIndex );
219 std::vector< const LabelPosition * > conflictingPositions;
220 mAllCandidatesIndex.intersects( searchBounds, [lp, &conflictingPositions,
this](
const LabelPosition * lp2 ) ->
bool
222 if ( candidatesAreConflicting( lp, lp2 ) )
224 conflictingPositions.emplace_back( lp2 );
231 ignoreLabel( conflict, list, mAllCandidatesIndex );
241 for ( std::size_t i = 0; i < mFeatureCount; i++ )
243 if ( mSol.activeLabelIds[i] == -1 )
245 int nbOverlap = std::numeric_limits<int>::max();
246 const int firstCandidateIdForFeature = mFirstCandidateIndexForFeature[i];
247 const int totalCandidatesForFeature = mCandidateCountForFeature[i];
248 for (
int candidateIndexForFeature = 0; candidateIndexForFeature < totalCandidatesForFeature; candidateIndexForFeature++ )
250 lp = mLabelPositions[ firstCandidateIdForFeature + candidateIndexForFeature ].get();
254 mActiveCandidatesIndex.intersects( searchBounds, [&lp,
this](
const LabelPosition * lp2 )->
bool
256 if ( candidatesAreConflicting( lp, lp2 ) )
269 mSol.activeLabelIds[i] = retainedLabel->
getId();
280 return pal->candidatesAreConflicting( lp1, lp2 );
283inline Chain *Problem::chain(
int seed )
289 double delta_best = std::numeric_limits<double>::max();
294 Chain *retainedChain =
nullptr;
296 const int max_degree =
pal->mEjChainDeg;
298 QLinkedList<ElemTrans *> currentChain;
299 QLinkedList<int> conflicts;
301 std::vector< int > tmpsol( mSol.activeLabelIds );
310 const int totalCandidatesForThisFeature = mCandidateCountForFeature[seed];
311 delta_min = std::numeric_limits<double>::max();
317 if ( tmpsol[seed] == -1 )
318 delta -= mUnlabeledCostForFeature[seed];
320 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
322 for (
int i = -1; i < totalCandidatesForThisFeature ; i++ )
327 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFirstCandidateIndexForFeature[seed] != tmpsol[seed] )
331 lid = mFirstCandidateIndexForFeature[seed] + i;
334 lp = mLabelPositions[ lid ].get();
338 mActiveCandidatesIndex.intersects( searchBounds, [lp, &delta_tmp, &conflicts, ¤tChain,
this](
const LabelPosition * lp2 ) ->
bool
340 if ( candidatesAreConflicting( lp2, lp ) )
345 QLinkedList< ElemTrans * >::iterator cur;
346 for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
348 if ( ( *cur )->feat == feat )
354 if ( !conflicts.contains( feat ) )
356 conflicts.append( feat );
357 delta_tmp += lp2->
cost() + mUnlabeledCostForFeature[feat];
364 if ( conflicts.isEmpty() )
366 if ( !retainedChain || delta + lp->
cost() < delta_best )
370 delete[] retainedChain->
label;
371 delete[] retainedChain->
feat;
375 retainedChain =
new Chain();
378 delta_best = delta + lp->
cost();
380 retainedChain->
degree = currentChain.size() + 1;
381 retainedChain->
feat =
new int[retainedChain->
degree];
382 retainedChain->
label =
new int[retainedChain->
degree];
383 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
386 while ( current != currentChain.end() )
389 retainedChain->
feat[j] = move->
feat;
394 retainedChain->
feat[j] = seed;
395 retainedChain->
label[j] = lid;
396 retainedChain->
delta = delta + lp->
cost();
401 else if ( conflicts.size() == 1 )
403 if ( delta_tmp < delta_min )
405 delta_min = delta_tmp;
407 next_seed = conflicts.takeFirst();
411 conflicts.takeFirst();
419 newChain->
degree = currentChain.size() + 1 + conflicts.size();
422 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
426 while ( current != currentChain.end() )
436 newChain->
feat[j] = seed;
437 newChain->
label[j] = lid;
438 newChain->
delta = delta + mLabelPositions.at( newChain->
label[j] )->cost();
442 while ( !conflicts.isEmpty() )
444 const int ftid = conflicts.takeFirst();
445 newChain->
feat[j] = ftid;
446 newChain->
label[j] = -1;
447 newChain->
delta += mUnlabeledCostForFeature[ftid];
451 if ( newChain->
delta < delta_best )
456 delta_best = newChain->
delta;
457 retainedChain = newChain;
468 if ( !retainedChain || delta + mUnlabeledCostForFeature[seed] < delta_best )
472 delete[] retainedChain->
label;
473 delete[] retainedChain->
feat;
476 retainedChain =
new Chain();
478 delta_best = delta + mUnlabeledCostForFeature[seed];
480 retainedChain->
degree = currentChain.size() + 1;
481 retainedChain->
feat =
new int[retainedChain->
degree];
482 retainedChain->
label =
new int[retainedChain->
degree];
483 QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
486 while ( current != currentChain.end() )
489 retainedChain->
feat[j] = move->
feat;
494 retainedChain->
feat[j] = seed;
495 retainedChain->
label[j] = -1;
496 retainedChain->
delta = delta + mUnlabeledCostForFeature[seed];
507 if ( next_seed == -1 )
511 else if ( currentChain.size() > max_degree )
522 currentChain.append( et );
526 mLabelPositions.at( et->
old_label )->removeFromIndex( mActiveCandidatesIndex,
pal );
531 mLabelPositions.at( et->
new_label )->insertIntoIndex( mActiveCandidatesIndex,
pal );
535 tmpsol[seed] = retainedLabel;
537 delta += mLabelPositions.at( retainedLabel )->cost();
542 while ( !currentChain.isEmpty() )
544 std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
548 mLabelPositions.at( et->
new_label )->removeFromIndex( mActiveCandidatesIndex,
pal );
553 mLabelPositions.at( et->
old_label )->insertIntoIndex( mActiveCandidatesIndex,
pal );
557 return retainedChain;
563 if ( mFeatureCount == 0 )
567 bool *ok =
new bool[mFeatureCount];
571 Chain *retainedChain =
nullptr;
573 std::fill( ok, ok + mFeatureCount,
false );
583 for ( seed = ( iter + 1 ) % mFeatureCount;
584 ok[seed] && seed != iter;
585 seed = ( seed + 1 ) % mFeatureCount )
594 iter = ( iter + 1 ) % mFeatureCount;
595 retainedChain = chain( seed );
597 if ( retainedChain && retainedChain->
delta < -
EPSILON )
600 for ( i = 0; i < retainedChain->
degree; i++ )
602 fid = retainedChain->
feat[i];
603 lid = retainedChain->
label[i];
605 if ( mSol.activeLabelIds[fid] >= 0 )
607 LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
611 mAllCandidatesIndex.intersects( searchBounds, [&ok, old,
this](
const LabelPosition * lp ) ->
bool
613 if ( candidatesAreConflicting( old, lp ) )
622 mSol.activeLabelIds[fid] = lid;
624 if ( mSol.activeLabelIds[fid] >= 0 )
626 mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex,
pal );
646 QList<LabelPosition *> finalLabelPlacements;
647 finalLabelPlacements.reserve( mFeatureCount );
650 for ( std::size_t i = 0; i < mFeatureCount; i++ )
652 const int labelId = mSol.activeLabelIds[i];
653 const bool foundNonOverlappingPlacement = labelId != -1;
654 const int startIndexForLabelPlacements = mFirstCandidateIndexForFeature[i];
655 const bool foundCandidatesForFeature = startIndexForLabelPlacements < static_cast< int >( mLabelPositions.size() );
657 if ( foundNonOverlappingPlacement )
659 finalLabelPlacements.push_back( mLabelPositions[ labelId ].get() );
661 else if ( foundCandidatesForFeature &&
664 || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->alwaysShow() ) )
666 finalLabelPlacements.push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
668 else if ( unlabeled )
671 if ( foundCandidatesForFeature && ( i == mFeatureCount - 1 || startIndexForLabelPlacements != mFirstCandidateIndexForFeature[i + 1] ) )
672 unlabeled->push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
679 unlabeled->reserve( mPositionsWithNoCandidates.size() );
680 for (
const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
681 unlabeled->append( position.get() );
684 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 decrementNumOverlaps()
Decreases the number of overlaps recorded against this position by 1.
int getId() const
Returns the id.
QgsRectangle boundingBoxForCandidateConflicts(Pal *pal) const
Returns the bounding box to use for candidate conflicts.
void removeFromIndex(PalRtree< LabelPosition > &index, Pal *pal)
Removes the label position from the specified index.
double cost() const
Returns the candidate label position's geographical cost.
int getNumOverlaps() const
int getProblemFeatureId() const
void insertIntoIndex(PalRtree< LabelPosition > &index, Pal *pal)
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 addCandidatePosition(std::unique_ptr< LabelPosition > position)
Adds a candidate label position to the problem.
Problem(const QgsRectangle &extent)
Constructor for Problem.
void chainSearch(QgsRenderContext &context)
Test with very-large scale neighborhood.
void reduce()
Gets called AFTER extractProblem.
void delete_chain(Chain *chain)