Branch data Line data Source code
1 : : /*
2 : : * libpal - Automated Placement of Labels Library
3 : : *
4 : : * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5 : : * University of Applied Sciences, Western Switzerland
6 : : * http://www.hes-so.ch
7 : : *
8 : : * Contact:
9 : : * maxence.laurent <at> heig-vd <dot> ch
10 : : * or
11 : : * eric.taillard <at> heig-vd <dot> ch
12 : : *
13 : : * This file is part of libpal.
14 : : *
15 : : * libpal is free software: you can redistribute it and/or modify
16 : : * it under the terms of the GNU General Public License as published by
17 : : * the Free Software Foundation, either version 3 of the License, or
18 : : * (at your option) any later version.
19 : : *
20 : : * libpal is distributed in the hope that it will be useful,
21 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 : : * GNU General Public License for more details.
24 : : *
25 : : * You should have received a copy of the GNU General Public License
26 : : * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27 : : *
28 : : */
29 : :
30 : : #include "pal.h"
31 : : #include "palstat.h"
32 : : #include "layer.h"
33 : : #include "feature.h"
34 : : #include "geomfunction.h"
35 : : #include "labelposition.h"
36 : : #include "problem.h"
37 : : #include "util.h"
38 : : #include "priorityqueue.h"
39 : : #include "internalexception.h"
40 : : #include <cfloat>
41 : : #include <limits> //for std::numeric_limits<int>::max()
42 : :
43 : : #include "qgslabelingengine.h"
44 : :
45 : : using namespace pal;
46 : :
47 : 0 : inline void delete_chain( Chain *chain )
48 : : {
49 : 0 : if ( chain )
50 : : {
51 : 0 : delete[] chain->feat;
52 : 0 : delete[] chain->label;
53 : 0 : delete chain;
54 : 0 : }
55 : 0 : }
56 : :
57 : 0 : Problem::Problem( const QgsRectangle &extent )
58 : 0 : : mAllCandidatesIndex( extent )
59 : 0 : , mActiveCandidatesIndex( extent )
60 : : {
61 : :
62 : 0 : }
63 : :
64 : 0 : Problem::~Problem() = default;
65 : :
66 : 0 : void Problem::reduce()
67 : : {
68 : : int i;
69 : : int j;
70 : : int k;
71 : :
72 : 0 : int counter = 0;
73 : :
74 : : int lpid;
75 : :
76 : 0 : bool *ok = new bool[mTotalCandidates];
77 : 0 : bool run = true;
78 : :
79 : 0 : for ( i = 0; i < mTotalCandidates; i++ )
80 : 0 : ok[i] = false;
81 : :
82 : :
83 : : double amin[2];
84 : : double amax[2];
85 : 0 : LabelPosition *lp2 = nullptr;
86 : :
87 : 0 : while ( run )
88 : : {
89 : 0 : run = false;
90 : 0 : for ( i = 0; i < static_cast< int >( mFeatureCount ); i++ )
91 : : {
92 : : // ok[i] = true;
93 : 0 : for ( j = 0; j < mFeatNbLp[i]; j++ ) // for each candidate
94 : : {
95 : 0 : if ( !ok[mFeatStartId[i] + j] )
96 : : {
97 : 0 : if ( mLabelPositions.at( mFeatStartId[i] + j )->getNumOverlaps() == 0 ) // if candidate has no overlap
98 : : {
99 : 0 : run = true;
100 : 0 : ok[mFeatStartId[i] + j] = true;
101 : : // 1) remove worse candidates from candidates
102 : : // 2) update nb_overlaps
103 : 0 : counter += mFeatNbLp[i] - j - 1;
104 : :
105 : 0 : for ( k = j + 1; k < mFeatNbLp[i]; k++ )
106 : : {
107 : :
108 : 0 : lpid = mFeatStartId[i] + k;
109 : 0 : ok[lpid] = true;
110 : 0 : lp2 = mLabelPositions[lpid ].get();
111 : :
112 : 0 : lp2->getBoundingBox( amin, amax );
113 : :
114 : 0 : mNbOverlap -= lp2->getNumOverlaps();
115 : 0 : mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp2, this]( const LabelPosition * lp ) -> bool
116 : : {
117 : 0 : if ( candidatesAreConflicting( lp2, lp ) )
118 : : {
119 : 0 : const_cast< LabelPosition * >( lp )->decrementNumOverlaps();
120 : 0 : lp2->decrementNumOverlaps();
121 : 0 : }
122 : :
123 : 0 : return true;
124 : : } );
125 : 0 : lp2->removeFromIndex( mAllCandidatesIndex );
126 : 0 : }
127 : :
128 : 0 : mFeatNbLp[i] = j + 1;
129 : 0 : break;
130 : : }
131 : 0 : }
132 : 0 : }
133 : 0 : }
134 : : }
135 : :
136 : 0 : this->mTotalCandidates -= counter;
137 : 0 : delete[] ok;
138 : 0 : }
139 : :
140 : 0 : void Problem::ignoreLabel( const LabelPosition *lp, PriorityQueue &list, PalRtree< LabelPosition > &candidatesIndex )
141 : : {
142 : 0 : if ( list.isIn( lp->getId() ) )
143 : : {
144 : 0 : list.remove( lp->getId() );
145 : :
146 : : double amin[2];
147 : : double amax[2];
148 : 0 : lp->getBoundingBox( amin, amax );
149 : 0 : candidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &list, this]( const LabelPosition * lp2 )->bool
150 : : {
151 : 0 : if ( lp2->getId() != lp->getId() && list.isIn( lp2->getId() ) && candidatesAreConflicting( lp2, lp ) )
152 : : {
153 : 0 : list.decreaseKey( lp2->getId() );
154 : 0 : }
155 : 0 : return true;
156 : : } );
157 : 0 : }
158 : 0 : }
159 : :
160 : : /* Better initial solution
161 : : * Step one FALP (Yamamoto, Camara, Lorena 2005)
162 : : */
163 : 0 : void Problem::init_sol_falp()
164 : : {
165 : : int label;
166 : :
167 : 0 : mSol.init( mFeatureCount );
168 : :
169 : 0 : PriorityQueue list( mTotalCandidates, mAllNblp, true );
170 : :
171 : : double amin[2];
172 : : double amax[2];
173 : :
174 : 0 : LabelPosition *lp = nullptr;
175 : :
176 : 0 : for ( int i = 0; i < static_cast< int >( mFeatureCount ); i++ )
177 : 0 : for ( int j = 0; j < mFeatNbLp[i]; j++ )
178 : : {
179 : 0 : label = mFeatStartId[i] + j;
180 : : try
181 : : {
182 : 0 : list.insert( label, mLabelPositions.at( label )->getNumOverlaps() );
183 : 0 : }
184 : : catch ( pal::InternalException::Full & )
185 : : {
186 : : continue;
187 : 0 : }
188 : 0 : }
189 : :
190 : 0 : while ( list.getSize() > 0 ) // O (log size)
191 : : {
192 : 0 : if ( pal->isCanceled() )
193 : : {
194 : 0 : return;
195 : : }
196 : :
197 : 0 : label = list.getBest(); // O (log size)
198 : :
199 : 0 : lp = mLabelPositions[ label ].get();
200 : :
201 : 0 : if ( lp->getId() != label )
202 : : {
203 : : //error
204 : 0 : }
205 : :
206 : 0 : int probFeatId = lp->getProblemFeatureId();
207 : 0 : mSol.activeLabelIds[probFeatId] = label;
208 : :
209 : 0 : for ( int i = mFeatStartId[probFeatId]; i < mFeatStartId[probFeatId] + mFeatNbLp[probFeatId]; i++ )
210 : : {
211 : 0 : ignoreLabel( mLabelPositions[ i ].get(), list, mAllCandidatesIndex );
212 : 0 : }
213 : :
214 : :
215 : 0 : lp->getBoundingBox( amin, amax );
216 : :
217 : 0 : std::vector< const LabelPosition * > conflictingPositions;
218 : 0 : mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &conflictingPositions, this]( const LabelPosition * lp2 ) ->bool
219 : : {
220 : 0 : if ( candidatesAreConflicting( lp, lp2 ) )
221 : : {
222 : 0 : conflictingPositions.emplace_back( lp2 );
223 : 0 : }
224 : 0 : return true;
225 : : } );
226 : :
227 : 0 : for ( const LabelPosition *conflict : conflictingPositions )
228 : : {
229 : 0 : ignoreLabel( conflict, list, mAllCandidatesIndex );
230 : : }
231 : 0 :
232 : 0 : mActiveCandidatesIndex.insert( lp, QgsRectangle( amin[0], amin[1], amax[0], amax[1] ) );
233 : 0 : }
234 : :
235 : 0 : if ( mDisplayAll )
236 : : {
237 : : int nbOverlap;
238 : : int start_p;
239 : 0 : LabelPosition *retainedLabel = nullptr;
240 : : int p;
241 : :
242 : 0 : for ( std::size_t i = 0; i < mFeatureCount; i++ ) // forearch hidden feature
243 : : {
244 : 0 : if ( mSol.activeLabelIds[i] == -1 )
245 : : {
246 : 0 : nbOverlap = std::numeric_limits<int>::max();
247 : 0 : start_p = mFeatStartId[i];
248 : 0 : for ( p = 0; p < mFeatNbLp[i]; p++ )
249 : : {
250 : 0 : lp = mLabelPositions[ start_p + p ].get();
251 : 0 : lp->resetNumOverlaps();
252 : :
253 : 0 : lp->getBoundingBox( amin, amax );
254 : :
255 : :
256 : 0 : mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
257 : : {
258 : 0 : if ( candidatesAreConflicting( lp, lp2 ) )
259 : : {
260 : 0 : lp->incrementNumOverlaps();
261 : 0 : }
262 : 0 : return true;
263 : : } );
264 : :
265 : 0 : if ( lp->getNumOverlaps() < nbOverlap )
266 : : {
267 : 0 : retainedLabel = lp;
268 : 0 : nbOverlap = lp->getNumOverlaps();
269 : 0 : }
270 : 0 : }
271 : 0 : mSol.activeLabelIds[i] = retainedLabel->getId();
272 : :
273 : 0 : retainedLabel->insertIntoIndex( mActiveCandidatesIndex );
274 : :
275 : 0 : }
276 : 0 : }
277 : 0 : }
278 : 0 : }
279 : :
280 : 0 : bool Problem::candidatesAreConflicting( const LabelPosition *lp1, const LabelPosition *lp2 ) const
281 : : {
282 : 0 : return pal->candidatesAreConflicting( lp1, lp2 );
283 : : }
284 : :
285 : 0 : inline Chain *Problem::chain( int seed )
286 : : {
287 : : int lid;
288 : :
289 : : double delta;
290 : : double delta_min;
291 : 0 : double delta_best = std::numeric_limits<double>::max();
292 : : double delta_tmp;
293 : :
294 : : int next_seed;
295 : : int retainedLabel;
296 : 0 : Chain *retainedChain = nullptr;
297 : :
298 : 0 : int max_degree = pal->mEjChainDeg;
299 : :
300 : : int seedNbLp;
301 : :
302 : 0 : QLinkedList<ElemTrans *> currentChain;
303 : 0 : QLinkedList<int> conflicts;
304 : :
305 : 0 : std::vector< int > tmpsol( mSol.activeLabelIds );
306 : :
307 : 0 : LabelPosition *lp = nullptr;
308 : :
309 : : double amin[2];
310 : : double amax[2];
311 : :
312 : 0 : delta = 0;
313 : 0 : while ( seed != -1 )
314 : : {
315 : 0 : seedNbLp = mFeatNbLp[seed];
316 : 0 : delta_min = std::numeric_limits<double>::max();
317 : :
318 : 0 : next_seed = -1;
319 : 0 : retainedLabel = -2;
320 : :
321 : : // sol[seed] is ejected
322 : 0 : if ( tmpsol[seed] == -1 )
323 : 0 : delta -= mInactiveCost[seed];
324 : : else
325 : 0 : delta -= mLabelPositions.at( tmpsol[seed] )->cost();
326 : :
327 : 0 : for ( int i = -1; i < seedNbLp; i++ )
328 : : {
329 : : try
330 : : {
331 : : // Skip active label !
332 : 0 : if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFeatStartId[seed] != tmpsol[seed] )
333 : : {
334 : 0 : if ( i != -1 ) // new_label
335 : : {
336 : 0 : lid = mFeatStartId[seed] + i;
337 : 0 : delta_tmp = delta;
338 : :
339 : 0 : lp = mLabelPositions[ lid ].get();
340 : :
341 : : // evaluate conflicts graph in solution after moving seed's label
342 : :
343 : 0 : lp->getBoundingBox( amin, amax );
344 : 0 : mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, ¤tChain, this]( const LabelPosition * lp2 ) -> bool
345 : : {
346 : 0 : if ( candidatesAreConflicting( lp2, lp ) )
347 : : {
348 : 0 : const int feat = lp2->getProblemFeatureId();
349 : :
350 : : // is there any cycles ?
351 : 0 : QLinkedList< ElemTrans * >::iterator cur;
352 : 0 : for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
353 : : {
354 : 0 : if ( ( *cur )->feat == feat )
355 : : {
356 : 0 : throw - 1;
357 : : }
358 : 0 : }
359 : :
360 : 0 : if ( !conflicts.contains( feat ) )
361 : : {
362 : 0 : conflicts.append( feat );
363 : 0 : delta_tmp += lp2->cost() + mInactiveCost[feat];
364 : 0 : }
365 : 0 : }
366 : 0 : return true;
367 : : } );
368 : :
369 : : // no conflict -> end of chain
370 : 0 : if ( conflicts.isEmpty() )
371 : : {
372 : 0 : if ( !retainedChain || delta + lp->cost() < delta_best )
373 : : {
374 : 0 : if ( retainedChain )
375 : : {
376 : 0 : delete[] retainedChain->label;
377 : 0 : delete[] retainedChain->feat;
378 : 0 : }
379 : : else
380 : : {
381 : 0 : retainedChain = new Chain();
382 : : }
383 : :
384 : 0 : delta_best = delta + lp->cost();
385 : :
386 : 0 : retainedChain->degree = currentChain.size() + 1;
387 : 0 : retainedChain->feat = new int[retainedChain->degree];
388 : 0 : retainedChain->label = new int[retainedChain->degree];
389 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
390 : 0 : ElemTrans *move = nullptr;
391 : 0 : int j = 0;
392 : 0 : while ( current != currentChain.end() )
393 : : {
394 : 0 : move = *current;
395 : 0 : retainedChain->feat[j] = move->feat;
396 : 0 : retainedChain->label[j] = move->new_label;
397 : 0 : ++current;
398 : 0 : ++j;
399 : : }
400 : 0 : retainedChain->feat[j] = seed;
401 : 0 : retainedChain->label[j] = lid;
402 : 0 : retainedChain->delta = delta + lp->cost();
403 : 0 : }
404 : 0 : }
405 : :
406 : : // another feature can be ejected
407 : 0 : else if ( conflicts.size() == 1 )
408 : : {
409 : 0 : if ( delta_tmp < delta_min )
410 : : {
411 : 0 : delta_min = delta_tmp;
412 : 0 : retainedLabel = lid;
413 : 0 : next_seed = conflicts.takeFirst();
414 : 0 : }
415 : : else
416 : : {
417 : 0 : conflicts.takeFirst();
418 : : }
419 : 0 : }
420 : : else
421 : : {
422 : :
423 : : // A lot of conflict : make them inactive and store chain
424 : 0 : Chain *newChain = new Chain();
425 : 0 : newChain->degree = currentChain.size() + 1 + conflicts.size();
426 : 0 : newChain->feat = new int[newChain->degree];
427 : 0 : newChain->label = new int[newChain->degree];
428 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
429 : 0 : ElemTrans *move = nullptr;
430 : 0 : int j = 0;
431 : :
432 : 0 : while ( current != currentChain.end() )
433 : : {
434 : 0 : move = *current;
435 : 0 : newChain->feat[j] = move->feat;
436 : 0 : newChain->label[j] = move->new_label;
437 : 0 : ++current;
438 : 0 : ++j;
439 : : }
440 : :
441 : : // add the current candidates into the chain
442 : 0 : newChain->feat[j] = seed;
443 : 0 : newChain->label[j] = lid;
444 : 0 : newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
445 : 0 : j++;
446 : :
447 : : // hide all conflictual candidates
448 : 0 : while ( !conflicts.isEmpty() )
449 : : {
450 : 0 : int ftid = conflicts.takeFirst();
451 : 0 : newChain->feat[j] = ftid;
452 : 0 : newChain->label[j] = -1;
453 : 0 : newChain->delta += mInactiveCost[ftid];
454 : 0 : j++;
455 : : }
456 : :
457 : 0 : if ( newChain->delta < delta_best )
458 : : {
459 : 0 : if ( retainedChain )
460 : 0 : delete_chain( retainedChain );
461 : :
462 : 0 : delta_best = newChain->delta;
463 : 0 : retainedChain = newChain;
464 : 0 : }
465 : : else
466 : : {
467 : 0 : delete_chain( newChain );
468 : : }
469 : : }
470 : :
471 : 0 : }
472 : : else // Current label == -1 end of chain ...
473 : : {
474 : 0 : if ( !retainedChain || delta + mInactiveCost[seed] < delta_best )
475 : : {
476 : 0 : if ( retainedChain )
477 : : {
478 : 0 : delete[] retainedChain->label;
479 : 0 : delete[] retainedChain->feat;
480 : 0 : }
481 : : else
482 : 0 : retainedChain = new Chain();
483 : :
484 : 0 : delta_best = delta + mInactiveCost[seed];
485 : :
486 : 0 : retainedChain->degree = currentChain.size() + 1;
487 : 0 : retainedChain->feat = new int[retainedChain->degree];
488 : 0 : retainedChain->label = new int[retainedChain->degree];
489 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
490 : 0 : ElemTrans *move = nullptr;
491 : 0 : int j = 0;
492 : 0 : while ( current != currentChain.end() )
493 : : {
494 : 0 : move = *current;
495 : 0 : retainedChain->feat[j] = move->feat;
496 : 0 : retainedChain->label[j] = move->new_label;
497 : 0 : ++current;
498 : 0 : ++j;
499 : : }
500 : 0 : retainedChain->feat[j] = seed;
501 : 0 : retainedChain->label[j] = -1;
502 : 0 : retainedChain->delta = delta + mInactiveCost[seed];
503 : 0 : }
504 : : }
505 : 0 : }
506 : 0 : }
507 : : catch ( int )
508 : : {
509 : 0 : conflicts.clear();
510 : 0 : }
511 : 0 : } // end for each labelposition
512 : :
513 : 0 : if ( next_seed == -1 )
514 : : {
515 : 0 : seed = -1;
516 : 0 : }
517 : 0 : else if ( currentChain.size() > max_degree )
518 : : {
519 : : // Max degree reached
520 : 0 : seed = -1;
521 : 0 : }
522 : : else
523 : : {
524 : 0 : ElemTrans *et = new ElemTrans();
525 : 0 : et->feat = seed;
526 : 0 : et->old_label = tmpsol[seed];
527 : 0 : et->new_label = retainedLabel;
528 : 0 : currentChain.append( et );
529 : :
530 : 0 : if ( et->old_label != -1 )
531 : : {
532 : 0 : mLabelPositions.at( et->old_label )->removeFromIndex( mActiveCandidatesIndex );
533 : 0 : }
534 : :
535 : 0 : if ( et->new_label != -1 )
536 : : {
537 : 0 : mLabelPositions.at( et->new_label )->insertIntoIndex( mActiveCandidatesIndex );
538 : 0 : }
539 : :
540 : :
541 : 0 : tmpsol[seed] = retainedLabel;
542 : : // cppcheck-suppress invalidFunctionArg
543 : 0 : delta += mLabelPositions.at( retainedLabel )->cost();
544 : 0 : seed = next_seed;
545 : : }
546 : : }
547 : :
548 : 0 : while ( !currentChain.isEmpty() )
549 : : {
550 : 0 : std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
551 : :
552 : 0 : if ( et->new_label != -1 )
553 : : {
554 : 0 : mLabelPositions.at( et->new_label )->removeFromIndex( mActiveCandidatesIndex );
555 : 0 : }
556 : :
557 : 0 : if ( et->old_label != -1 )
558 : : {
559 : 0 : mLabelPositions.at( et->old_label )->insertIntoIndex( mActiveCandidatesIndex );
560 : 0 : }
561 : 0 : }
562 : :
563 : 0 : return retainedChain;
564 : 0 : }
565 : :
566 : :
567 : 0 : void Problem::chain_search()
568 : : {
569 : 0 : if ( mFeatureCount == 0 )
570 : 0 : return;
571 : :
572 : : int i;
573 : : int seed;
574 : 0 : bool *ok = new bool[mFeatureCount];
575 : : int fid;
576 : : int lid;
577 : 0 : int popit = 0;
578 : :
579 : 0 : Chain *retainedChain = nullptr;
580 : :
581 : 0 : std::fill( ok, ok + mFeatureCount, false );
582 : :
583 : : //initialization();
584 : 0 : init_sol_falp();
585 : :
586 : : //check_solution();
587 : 0 : solution_cost();
588 : :
589 : 0 : int iter = 0;
590 : :
591 : : double amin[2];
592 : : double amax[2];
593 : :
594 : 0 : while ( true )
595 : : {
596 : :
597 : : //check_solution();
598 : :
599 : 0 : for ( seed = ( iter + 1 ) % mFeatureCount;
600 : 0 : ok[seed] && seed != iter;
601 : 0 : seed = ( seed + 1 ) % mFeatureCount )
602 : : ;
603 : :
604 : : // All seeds are OK
605 : 0 : if ( seed == iter )
606 : : {
607 : 0 : break;
608 : : }
609 : :
610 : 0 : iter = ( iter + 1 ) % mFeatureCount;
611 : 0 : retainedChain = chain( seed );
612 : :
613 : 0 : if ( retainedChain && retainedChain->delta < - EPSILON )
614 : : {
615 : : // apply modification
616 : 0 : for ( i = 0; i < retainedChain->degree; i++ )
617 : : {
618 : 0 : fid = retainedChain->feat[i];
619 : 0 : lid = retainedChain->label[i];
620 : :
621 : 0 : if ( mSol.activeLabelIds[fid] >= 0 )
622 : : {
623 : 0 : LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
624 : 0 : old->removeFromIndex( mActiveCandidatesIndex );
625 : 0 : old->getBoundingBox( amin, amax );
626 : 0 : mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old, this]( const LabelPosition * lp ) ->bool
627 : : {
628 : 0 : if ( candidatesAreConflicting( old, lp ) )
629 : : {
630 : 0 : ok[lp->getProblemFeatureId()] = false;
631 : 0 : }
632 : :
633 : 0 : return true;
634 : : } );
635 : 0 : }
636 : :
637 : 0 : mSol.activeLabelIds[fid] = lid;
638 : :
639 : 0 : if ( mSol.activeLabelIds[fid] >= 0 )
640 : : {
641 : 0 : mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex );
642 : 0 : }
643 : :
644 : 0 : ok[fid] = false;
645 : 0 : }
646 : 0 : mSol.totalCost += retainedChain->delta;
647 : 0 : }
648 : : else
649 : : {
650 : : // no chain or the one is not god enough
651 : 0 : ok[seed] = true;
652 : : }
653 : :
654 : 0 : delete_chain( retainedChain );
655 : 0 : popit++;
656 : : }
657 : :
658 : 0 : solution_cost();
659 : 0 : delete[] ok;
660 : 0 : }
661 : :
662 : 0 : QList<LabelPosition *> Problem::getSolution( bool returnInactive, QList<LabelPosition *> *unlabeled )
663 : : {
664 : 0 : QList<LabelPosition *> finalLabelPlacements;
665 : :
666 : : // loop through all features to be labeled
667 : 0 : for ( std::size_t i = 0; i < mFeatureCount; i++ )
668 : : {
669 : 0 : const int labelId = mSol.activeLabelIds[i];
670 : 0 : const bool foundNonOverlappingPlacement = labelId != -1;
671 : 0 : const int startIndexForLabelPlacements = mFeatStartId[i];
672 : 0 : const bool foundCandidatesForFeature = startIndexForLabelPlacements < static_cast< int >( mLabelPositions.size() );
673 : :
674 : 0 : if ( foundNonOverlappingPlacement )
675 : : {
676 : 0 : finalLabelPlacements.push_back( mLabelPositions[ labelId ].get() ); // active labels
677 : 0 : }
678 : 0 : else if ( foundCandidatesForFeature &&
679 : 0 : ( returnInactive // allowing any overlapping labels regardless of where they are from
680 : 0 : || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->layer()->displayAll() // allowing overlapping labels for the layer
681 : 0 : || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->alwaysShow() ) ) // allowing overlapping labels for the feature
682 : : {
683 : 0 : finalLabelPlacements.push_back( mLabelPositions[ startIndexForLabelPlacements ].get() ); // unplaced label
684 : 0 : }
685 : 0 : else if ( unlabeled )
686 : : {
687 : : // need to be careful here -- if the next feature's start id is the same as this one, then this feature had no candidates!
688 : 0 : if ( foundCandidatesForFeature && ( i == mFeatureCount - 1 || startIndexForLabelPlacements != mFeatStartId[i + 1] ) )
689 : 0 : unlabeled->push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
690 : 0 : }
691 : 0 : }
692 : :
693 : : // unlabeled features also include those with no candidates
694 : 0 : if ( unlabeled )
695 : : {
696 : 0 : for ( const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
697 : 0 : unlabeled->append( position.get() );
698 : 0 : }
699 : :
700 : 0 : return finalLabelPlacements;
701 : 0 : }
702 : :
703 : 0 : void Problem::solution_cost()
704 : : {
705 : 0 : mSol.totalCost = 0.0;
706 : :
707 : 0 : LabelPosition *lp = nullptr;
708 : :
709 : : double amin[2];
710 : : double amax[2];
711 : :
712 : 0 : for ( std::size_t i = 0; i < mFeatureCount; i++ )
713 : : {
714 : 0 : if ( mSol.activeLabelIds[i] == -1 )
715 : : {
716 : 0 : mSol.totalCost += mInactiveCost[i];
717 : 0 : }
718 : : else
719 : : {
720 : 0 : lp = mLabelPositions[ mSol.activeLabelIds[i] ].get();
721 : :
722 : 0 : lp->getBoundingBox( amin, amax );
723 : 0 : mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
724 : : {
725 : 0 : if ( candidatesAreConflicting( lp, lp2 ) )
726 : : {
727 : 0 : mSol.totalCost += mInactiveCost[lp2->getProblemFeatureId()] + lp2->cost();
728 : 0 : }
729 : :
730 : 0 : return true;
731 : : } );
732 : :
733 : 0 : mSol.totalCost += lp->cost();
734 : : }
735 : 0 : }
736 : 0 : }
|
