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]( const LabelPosition * lp ) -> bool
116 : : {
117 : 0 : if ( lp2->isInConflict( 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 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]( const LabelPosition * lp2 )->bool
150 : : {
151 : 0 : if ( lp2->getId() != lp->getId() && list.isIn( lp2->getId() ) && lp2->isInConflict( 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 : 0 : * 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 : 0 : 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 : 0 : {
182 : 0 : list.insert( label, mLabelPositions.at( label )->getNumOverlaps() );
183 : 0 : }
184 : : catch ( pal::InternalException::Full & )
185 : : {
186 : 0 : continue;
187 : 0 : }
188 : 0 : }
189 : :
190 : 0 : while ( list.getSize() > 0 ) // O (log size)
191 : 0 : {
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]( const LabelPosition * lp2 ) ->bool
219 : : {
220 : 0 : if ( lp->isInConflict( lp2 ) )
221 : 0 : {
222 : 0 : conflictingPositions.emplace_back( lp2 );
223 : 0 : }
224 : 0 : return true;
225 : 0 : } );
226 : :
227 : 0 : for ( const LabelPosition *conflict : conflictingPositions )
228 : : {
229 : 0 : ignoreLabel( conflict, list, mAllCandidatesIndex );
230 : : }
231 : :
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]( const LabelPosition * lp2 )->bool
257 : : {
258 : 0 : if ( lp->isInConflict( 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 : inline Chain *Problem::chain( int seed )
281 : : {
282 : : int lid;
283 : :
284 : : double delta;
285 : : double delta_min;
286 : 0 : double delta_best = std::numeric_limits<double>::max();
287 : : double delta_tmp;
288 : :
289 : : int next_seed;
290 : : int retainedLabel;
291 : 0 : Chain *retainedChain = nullptr;
292 : :
293 : 0 : int max_degree = pal->mEjChainDeg;
294 : :
295 : : int seedNbLp;
296 : :
297 : 0 : QLinkedList<ElemTrans *> currentChain;
298 : 0 : QLinkedList<int> conflicts;
299 : :
300 : 0 : std::vector< int > tmpsol( mSol.activeLabelIds );
301 : :
302 : 0 : LabelPosition *lp = nullptr;
303 : :
304 : : double amin[2];
305 : : double amax[2];
306 : :
307 : 0 : delta = 0;
308 : 0 : while ( seed != -1 )
309 : : {
310 : 0 : seedNbLp = mFeatNbLp[seed];
311 : 0 : delta_min = std::numeric_limits<double>::max();
312 : :
313 : 0 : next_seed = -1;
314 : 0 : retainedLabel = -2;
315 : :
316 : : // sol[seed] is ejected
317 : 0 : if ( tmpsol[seed] == -1 )
318 : 0 : delta -= mInactiveCost[seed];
319 : : else
320 : 0 : delta -= mLabelPositions.at( tmpsol[seed] )->cost();
321 : :
322 : 0 : for ( int i = -1; i < seedNbLp; i++ )
323 : : {
324 : : try
325 : : {
326 : : // Skip active label !
327 : 0 : if ( !( tmpsol[seed] == -1 && i == -1 ) && i + mFeatStartId[seed] != tmpsol[seed] )
328 : : {
329 : 0 : if ( i != -1 ) // new_label
330 : : {
331 : 0 : lid = mFeatStartId[seed] + i;
332 : 0 : delta_tmp = delta;
333 : :
334 : 0 : lp = mLabelPositions[ lid ].get();
335 : :
336 : : // evaluate conflicts graph in solution after moving seed's label
337 : :
338 : 0 : lp->getBoundingBox( amin, amax );
339 : 0 : mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [lp, &delta_tmp, &conflicts, ¤tChain, this]( const LabelPosition * lp2 ) -> bool
340 : : {
341 : 0 : if ( lp2->isInConflict( lp ) )
342 : : {
343 : 0 : const int feat = lp2->getProblemFeatureId();
344 : :
345 : : // is there any cycles ?
346 : 0 : QLinkedList< ElemTrans * >::iterator cur;
347 : 0 : for ( cur = currentChain.begin(); cur != currentChain.end(); ++cur )
348 : : {
349 : 0 : if ( ( *cur )->feat == feat )
350 : : {
351 : 0 : throw - 1;
352 : : }
353 : 0 : }
354 : :
355 : 0 : if ( !conflicts.contains( feat ) )
356 : : {
357 : 0 : conflicts.append( feat );
358 : 0 : delta_tmp += lp2->cost() + mInactiveCost[feat];
359 : 0 : }
360 : 0 : }
361 : 0 : return true;
362 : : } );
363 : :
364 : : // no conflict -> end of chain
365 : 0 : if ( conflicts.isEmpty() )
366 : : {
367 : 0 : if ( !retainedChain || delta + lp->cost() < delta_best )
368 : : {
369 : 0 : if ( retainedChain )
370 : : {
371 : 0 : delete[] retainedChain->label;
372 : 0 : delete[] retainedChain->feat;
373 : 0 : }
374 : : else
375 : : {
376 : 0 : retainedChain = new Chain();
377 : : }
378 : :
379 : 0 : delta_best = delta + lp->cost();
380 : :
381 : 0 : retainedChain->degree = currentChain.size() + 1;
382 : 0 : retainedChain->feat = new int[retainedChain->degree];
383 : 0 : retainedChain->label = new int[retainedChain->degree];
384 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
385 : 0 : ElemTrans *move = nullptr;
386 : 0 : int j = 0;
387 : 0 : while ( current != currentChain.end() )
388 : : {
389 : 0 : move = *current;
390 : 0 : retainedChain->feat[j] = move->feat;
391 : 0 : retainedChain->label[j] = move->new_label;
392 : 0 : ++current;
393 : 0 : ++j;
394 : : }
395 : 0 : retainedChain->feat[j] = seed;
396 : 0 : retainedChain->label[j] = lid;
397 : 0 : retainedChain->delta = delta + lp->cost();
398 : 0 : }
399 : 0 : }
400 : :
401 : : // another feature can be ejected
402 : 0 : else if ( conflicts.size() == 1 )
403 : : {
404 : 0 : if ( delta_tmp < delta_min )
405 : : {
406 : 0 : delta_min = delta_tmp;
407 : 0 : retainedLabel = lid;
408 : 0 : next_seed = conflicts.takeFirst();
409 : 0 : }
410 : : else
411 : : {
412 : 0 : conflicts.takeFirst();
413 : : }
414 : 0 : }
415 : : else
416 : : {
417 : :
418 : : // A lot of conflict : make them inactive and store chain
419 : 0 : Chain *newChain = new Chain();
420 : 0 : newChain->degree = currentChain.size() + 1 + conflicts.size();
421 : 0 : newChain->feat = new int[newChain->degree];
422 : 0 : newChain->label = new int[newChain->degree];
423 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
424 : 0 : ElemTrans *move = nullptr;
425 : 0 : int j = 0;
426 : :
427 : 0 : while ( current != currentChain.end() )
428 : : {
429 : 0 : move = *current;
430 : 0 : newChain->feat[j] = move->feat;
431 : 0 : newChain->label[j] = move->new_label;
432 : 0 : ++current;
433 : 0 : ++j;
434 : : }
435 : :
436 : : // add the current candidates into the chain
437 : 0 : newChain->feat[j] = seed;
438 : 0 : newChain->label[j] = lid;
439 : 0 : newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
440 : 0 : j++;
441 : :
442 : : // hide all conflictual candidates
443 : 0 : while ( !conflicts.isEmpty() )
444 : : {
445 : 0 : int ftid = conflicts.takeFirst();
446 : 0 : newChain->feat[j] = ftid;
447 : 0 : newChain->label[j] = -1;
448 : 0 : newChain->delta += mInactiveCost[ftid];
449 : 0 : j++;
450 : : }
451 : :
452 : 0 : if ( newChain->delta < delta_best )
453 : : {
454 : 0 : if ( retainedChain )
455 : 0 : delete_chain( retainedChain );
456 : :
457 : 0 : delta_best = newChain->delta;
458 : 0 : retainedChain = newChain;
459 : 0 : }
460 : : else
461 : : {
462 : 0 : delete_chain( newChain );
463 : : }
464 : : }
465 : :
466 : 0 : }
467 : : else // Current label == -1 end of chain ...
468 : : {
469 : 0 : if ( !retainedChain || delta + mInactiveCost[seed] < delta_best )
470 : : {
471 : 0 : if ( retainedChain )
472 : : {
473 : 0 : delete[] retainedChain->label;
474 : 0 : delete[] retainedChain->feat;
475 : 0 : }
476 : : else
477 : 0 : retainedChain = new Chain();
478 : :
479 : 0 : delta_best = delta + mInactiveCost[seed];
480 : :
481 : 0 : retainedChain->degree = currentChain.size() + 1;
482 : 0 : retainedChain->feat = new int[retainedChain->degree];
483 : 0 : retainedChain->label = new int[retainedChain->degree];
484 : 0 : QLinkedList<ElemTrans *>::iterator current = currentChain.begin();
485 : 0 : ElemTrans *move = nullptr;
486 : 0 : int j = 0;
487 : 0 : while ( current != currentChain.end() )
488 : : {
489 : 0 : move = *current;
490 : 0 : retainedChain->feat[j] = move->feat;
491 : 0 : retainedChain->label[j] = move->new_label;
492 : 0 : ++current;
493 : 0 : ++j;
494 : : }
495 : 0 : retainedChain->feat[j] = seed;
496 : 0 : retainedChain->label[j] = -1;
497 : 0 : retainedChain->delta = delta + mInactiveCost[seed];
498 : 0 : }
499 : : }
500 : 0 : }
501 : 0 : }
502 : : catch ( int )
503 : : {
504 : 0 : conflicts.clear();
505 : 0 : }
506 : 0 : } // end for each labelposition
507 : :
508 : 0 : if ( next_seed == -1 )
509 : : {
510 : 0 : seed = -1;
511 : 0 : }
512 : 0 : else if ( currentChain.size() > max_degree )
513 : : {
514 : : // Max degree reached
515 : 0 : seed = -1;
516 : 0 : }
517 : : else
518 : : {
519 : 0 : ElemTrans *et = new ElemTrans();
520 : 0 : et->feat = seed;
521 : 0 : et->old_label = tmpsol[seed];
522 : 0 : et->new_label = retainedLabel;
523 : 0 : currentChain.append( et );
524 : :
525 : 0 : if ( et->old_label != -1 )
526 : : {
527 : 0 : mLabelPositions.at( et->old_label )->removeFromIndex( mActiveCandidatesIndex );
528 : 0 : }
529 : :
530 : 0 : if ( et->new_label != -1 )
531 : : {
532 : 0 : mLabelPositions.at( et->new_label )->insertIntoIndex( mActiveCandidatesIndex );
533 : 0 : }
534 : :
535 : :
536 : 0 : tmpsol[seed] = retainedLabel;
537 : : // cppcheck-suppress invalidFunctionArg
538 : 0 : delta += mLabelPositions.at( retainedLabel )->cost();
539 : 0 : seed = next_seed;
540 : : }
541 : : }
542 : :
543 : 0 : while ( !currentChain.isEmpty() )
544 : : {
545 : 0 : std::unique_ptr< ElemTrans > et( currentChain.takeFirst() );
546 : :
547 : 0 : if ( et->new_label != -1 )
548 : : {
549 : 0 : mLabelPositions.at( et->new_label )->removeFromIndex( mActiveCandidatesIndex );
550 : 0 : }
551 : :
552 : 0 : if ( et->old_label != -1 )
553 : : {
554 : 0 : mLabelPositions.at( et->old_label )->insertIntoIndex( mActiveCandidatesIndex );
555 : 0 : }
556 : 0 : }
557 : :
558 : 0 : return retainedChain;
559 : 0 : }
560 : :
561 : :
562 : 0 : void Problem::chain_search()
563 : : {
564 : 0 : if ( mFeatureCount == 0 )
565 : 0 : return;
566 : :
567 : : int i;
568 : : int seed;
569 : 0 : bool *ok = new bool[mFeatureCount];
570 : : int fid;
571 : : int lid;
572 : 0 : int popit = 0;
573 : :
574 : 0 : Chain *retainedChain = nullptr;
575 : :
576 : 0 : std::fill( ok, ok + mFeatureCount, false );
577 : :
578 : : //initialization();
579 : 0 : init_sol_falp();
580 : :
581 : : //check_solution();
582 : 0 : solution_cost();
583 : :
584 : 0 : int iter = 0;
585 : :
586 : : double amin[2];
587 : : double amax[2];
588 : :
589 : 0 : while ( true )
590 : : {
591 : :
592 : : //check_solution();
593 : :
594 : 0 : for ( seed = ( iter + 1 ) % mFeatureCount;
595 : 0 : ok[seed] && seed != iter;
596 : 0 : seed = ( seed + 1 ) % mFeatureCount )
597 : : ;
598 : :
599 : : // All seeds are OK
600 : 0 : if ( seed == iter )
601 : : {
602 : 0 : break;
603 : : }
604 : :
605 : 0 : iter = ( iter + 1 ) % mFeatureCount;
606 : 0 : retainedChain = chain( seed );
607 : :
608 : 0 : if ( retainedChain && retainedChain->delta < - EPSILON )
609 : : {
610 : : // apply modification
611 : 0 : for ( i = 0; i < retainedChain->degree; i++ )
612 : : {
613 : 0 : fid = retainedChain->feat[i];
614 : 0 : lid = retainedChain->label[i];
615 : :
616 : 0 : if ( mSol.activeLabelIds[fid] >= 0 )
617 : : {
618 : 0 : LabelPosition *old = mLabelPositions[ mSol.activeLabelIds[fid] ].get();
619 : 0 : old->removeFromIndex( mActiveCandidatesIndex );
620 : 0 : old->getBoundingBox( amin, amax );
621 : 0 : mAllCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&ok, old]( const LabelPosition * lp ) ->bool
622 : : {
623 : 0 : if ( old->isInConflict( lp ) )
624 : : {
625 : 0 : ok[lp->getProblemFeatureId()] = false;
626 : 0 : }
627 : :
628 : 0 : return true;
629 : : } );
630 : 0 : }
631 : :
632 : 0 : mSol.activeLabelIds[fid] = lid;
633 : :
634 : 0 : if ( mSol.activeLabelIds[fid] >= 0 )
635 : : {
636 : 0 : mLabelPositions.at( lid )->insertIntoIndex( mActiveCandidatesIndex );
637 : 0 : }
638 : :
639 : 0 : ok[fid] = false;
640 : 0 : }
641 : 0 : mSol.totalCost += retainedChain->delta;
642 : 0 : }
643 : : else
644 : : {
645 : : // no chain or the one is not god enough
646 : 0 : ok[seed] = true;
647 : : }
648 : :
649 : 0 : delete_chain( retainedChain );
650 : 0 : popit++;
651 : : }
652 : :
653 : 0 : solution_cost();
654 : 0 : delete[] ok;
655 : 0 : }
656 : :
657 : 0 : QList<LabelPosition *> Problem::getSolution( bool returnInactive, QList<LabelPosition *> *unlabeled )
658 : : {
659 : 0 : QList<LabelPosition *> finalLabelPlacements;
660 : :
661 : : // loop through all features to be labeled
662 : 0 : for ( std::size_t i = 0; i < mFeatureCount; i++ )
663 : : {
664 : 0 : const int labelId = mSol.activeLabelIds[i];
665 : 0 : const bool foundNonOverlappingPlacement = labelId != -1;
666 : 0 : const int startIndexForLabelPlacements = mFeatStartId[i];
667 : 0 : const bool foundCandidatesForFeature = startIndexForLabelPlacements < static_cast< int >( mLabelPositions.size() );
668 : :
669 : 0 : if ( foundNonOverlappingPlacement )
670 : : {
671 : 0 : finalLabelPlacements.push_back( mLabelPositions[ labelId ].get() ); // active labels
672 : 0 : }
673 : 0 : else if ( foundCandidatesForFeature &&
674 : 0 : ( returnInactive // allowing any overlapping labels regardless of where they are from
675 : 0 : || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->layer()->displayAll() // allowing overlapping labels for the layer
676 : 0 : || mLabelPositions.at( startIndexForLabelPlacements )->getFeaturePart()->alwaysShow() ) ) // allowing overlapping labels for the feature
677 : : {
678 : 0 : finalLabelPlacements.push_back( mLabelPositions[ startIndexForLabelPlacements ].get() ); // unplaced label
679 : 0 : }
680 : 0 : else if ( unlabeled )
681 : : {
682 : : // need to be careful here -- if the next feature's start id is the same as this one, then this feature had no candidates!
683 : 0 : if ( foundCandidatesForFeature && ( i == mFeatureCount - 1 || startIndexForLabelPlacements != mFeatStartId[i + 1] ) )
684 : 0 : unlabeled->push_back( mLabelPositions[ startIndexForLabelPlacements ].get() );
685 : 0 : }
686 : 0 : }
687 : :
688 : : // unlabeled features also include those with no candidates
689 : 0 : if ( unlabeled )
690 : : {
691 : 0 : for ( const std::unique_ptr< LabelPosition > &position : mPositionsWithNoCandidates )
692 : 0 : unlabeled->append( position.get() );
693 : 0 : }
694 : :
695 : 0 : return finalLabelPlacements;
696 : 0 : }
697 : :
698 : 0 : void Problem::solution_cost()
699 : : {
700 : 0 : mSol.totalCost = 0.0;
701 : :
702 : 0 : LabelPosition *lp = nullptr;
703 : :
704 : : double amin[2];
705 : : double amax[2];
706 : :
707 : 0 : for ( std::size_t i = 0; i < mFeatureCount; i++ )
708 : : {
709 : 0 : if ( mSol.activeLabelIds[i] == -1 )
710 : : {
711 : 0 : mSol.totalCost += mInactiveCost[i];
712 : 0 : }
713 : : else
714 : : {
715 : 0 : lp = mLabelPositions[ mSol.activeLabelIds[i] ].get();
716 : :
717 : 0 : lp->getBoundingBox( amin, amax );
718 : 0 : mActiveCandidatesIndex.intersects( QgsRectangle( amin[0], amin[1], amax[0], amax[1] ), [&lp, this]( const LabelPosition * lp2 )->bool
719 : : {
720 : 0 : if ( lp->isInConflict( lp2 ) )
721 : : {
722 : 0 : mSol.totalCost += mInactiveCost[lp2->getProblemFeatureId()] + lp2->cost();
723 : 0 : }
724 : :
725 : 0 : return true;
726 : : } );
727 : :
728 : 0 : mSol.totalCost += lp->cost();
729 : : }
730 : 0 : }
731 : 0 : }
|
