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 );
531 mLabelPositions.at( et->
new_label )->insertIntoIndex( mActiveCandidatesIndex );
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 );
553 mLabelPositions.at( et->
old_label )->insertIntoIndex( mActiveCandidatesIndex );
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 );
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.
QgsRectangle outerBoundingBox() const
Returns bounding box.
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.
QgsRectangle boundingBoxForCandidateConflicts(Pal *pal) const
Returns the bounding box to use for candidate conflicts.
double cost() const
Returns the candidate label position's geographical cost.
int getNumOverlaps() const
int getProblemFeatureId() const
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 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)