QGIS API Documentation 3.30.0-'s-Hertogenbosch (f186b8efe0)
feature.cpp
Go to the documentation of this file.
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 "layer.h"
32#include "feature.h"
33#include "geomfunction.h"
34#include "labelposition.h"
35#include "pointset.h"
36
37#include "qgis.h"
38#include "qgsgeometry.h"
39#include "qgsgeos.h"
40#include "qgstextlabelfeature.h"
41#include "qgsmessagelog.h"
42#include "qgsgeometryutils.h"
43#include "qgslabeling.h"
44#include "qgspolygon.h"
46
47#include <QLinkedList>
48#include <cmath>
49#include <cfloat>
50
51using namespace pal;
52
53FeaturePart::FeaturePart( QgsLabelFeature *feat, const GEOSGeometry *geom )
54 : mLF( feat )
55{
56 // we'll remove const, but we won't modify that geometry
57 mGeos = const_cast<GEOSGeometry *>( geom );
58 mOwnsGeom = false; // geometry is owned by Feature class
59
60 extractCoords( geom );
61
62 holeOf = nullptr;
63 for ( int i = 0; i < mHoles.count(); i++ )
64 {
65 mHoles.at( i )->holeOf = this;
66 }
67
68}
69
71 : PointSet( other )
72 , mLF( other.mLF )
73{
74 for ( const FeaturePart *hole : std::as_const( other.mHoles ) )
75 {
76 mHoles << new FeaturePart( *hole );
77 mHoles.last()->holeOf = this;
78 }
79}
80
82{
83 // X and Y are deleted in PointSet
84
85 qDeleteAll( mHoles );
86 mHoles.clear();
87}
88
89void FeaturePart::extractCoords( const GEOSGeometry *geom )
90{
91 const GEOSCoordSequence *coordSeq = nullptr;
92 GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
93
94 type = GEOSGeomTypeId_r( geosctxt, geom );
95
96 if ( type == GEOS_POLYGON )
97 {
98 if ( GEOSGetNumInteriorRings_r( geosctxt, geom ) > 0 )
99 {
100 int numHoles = GEOSGetNumInteriorRings_r( geosctxt, geom );
101
102 for ( int i = 0; i < numHoles; ++i )
103 {
104 const GEOSGeometry *interior = GEOSGetInteriorRingN_r( geosctxt, geom, i );
105 FeaturePart *hole = new FeaturePart( mLF, interior );
106 hole->holeOf = nullptr;
107 // possibly not needed. it's not done for the exterior ring, so I'm not sure
108 // why it's just done here...
109 GeomFunction::reorderPolygon( hole->x, hole->y );
110
111 mHoles << hole;
112 }
113 }
114
115 // use exterior ring for the extraction of coordinates that follows
116 geom = GEOSGetExteriorRing_r( geosctxt, geom );
117 }
118 else
119 {
120 qDeleteAll( mHoles );
121 mHoles.clear();
122 }
123
124 // find out number of points
125 nbPoints = GEOSGetNumCoordinates_r( geosctxt, geom );
126 coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, geom );
127
128 // initialize bounding box
129 xmin = ymin = std::numeric_limits<double>::max();
130 xmax = ymax = std::numeric_limits<double>::lowest();
131
132 // initialize coordinate arrays
133 deleteCoords();
134 x.resize( nbPoints );
135 y.resize( nbPoints );
136
137#if GEOS_VERSION_MAJOR>3 || ( GEOS_VERSION_MAJOR == 3 && GEOS_VERSION_MINOR>=10 )
138 GEOSCoordSeq_copyToArrays_r( geosctxt, coordSeq, x.data(), y.data(), nullptr, nullptr );
139 auto xminmax = std::minmax_element( x.begin(), x.end() );
140 xmin = *xminmax.first;
141 xmax = *xminmax.second;
142 auto yminmax = std::minmax_element( y.begin(), y.end() );
143 ymin = *yminmax.first;
144 ymax = *yminmax.second;
145#else
146 for ( int i = 0; i < nbPoints; ++i )
147 {
148 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, i, &x[i], &y[i] );
149
150 xmax = x[i] > xmax ? x[i] : xmax;
151 xmin = x[i] < xmin ? x[i] : xmin;
152
153 ymax = y[i] > ymax ? y[i] : ymax;
154 ymin = y[i] < ymin ? y[i] : ymin;
155 }
156#endif
157}
158
160{
161 return mLF->layer();
162}
163
165{
166 return mLF->id();
167}
168
170{
172}
173
175{
176 if ( mCachedMaxLineCandidates > 0 )
177 return mCachedMaxLineCandidates;
178
179 const double l = length();
180 if ( l > 0 )
181 {
182 const std::size_t candidatesForLineLength = static_cast< std::size_t >( std::ceil( mLF->layer()->mPal->maximumLineCandidatesPerMapUnit() * l ) );
183 const std::size_t maxForLayer = mLF->layer()->maximumLineLabelCandidates();
184 if ( maxForLayer == 0 )
185 mCachedMaxLineCandidates = candidatesForLineLength;
186 else
187 mCachedMaxLineCandidates = std::min( candidatesForLineLength, maxForLayer );
188 }
189 else
190 {
191 mCachedMaxLineCandidates = 1;
192 }
193 return mCachedMaxLineCandidates;
194}
195
197{
198 if ( mCachedMaxPolygonCandidates > 0 )
199 return mCachedMaxPolygonCandidates;
200
201 const double a = area();
202 if ( a > 0 )
203 {
204 const std::size_t candidatesForArea = static_cast< std::size_t >( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * a ) );
205 const std::size_t maxForLayer = mLF->layer()->maximumPolygonLabelCandidates();
206 if ( maxForLayer == 0 )
207 mCachedMaxPolygonCandidates = candidatesForArea;
208 else
209 mCachedMaxPolygonCandidates = std::min( candidatesForArea, maxForLayer );
210 }
211 else
212 {
213 mCachedMaxPolygonCandidates = 1;
214 }
215 return mCachedMaxPolygonCandidates;
216}
217
219{
220 if ( !part )
221 return false;
222
223 if ( mLF->layer()->name() != part->layer()->name() )
224 return false;
225
226 if ( mLF->id() == part->featureId() )
227 return true;
228
229 // any part of joined features are also treated as having the same label feature
230 int connectedFeatureId = mLF->layer()->connectedFeatureId( mLF->id() );
231 return connectedFeatureId >= 0 && connectedFeatureId == mLF->layer()->connectedFeatureId( part->featureId() );
232}
233
234LabelPosition::Quadrant FeaturePart::quadrantFromOffset() const
235{
236 QPointF quadOffset = mLF->quadOffset();
237 qreal quadOffsetX = quadOffset.x(), quadOffsetY = quadOffset.y();
238
239 if ( quadOffsetX < 0 )
240 {
241 if ( quadOffsetY < 0 )
242 {
244 }
245 else if ( quadOffsetY > 0 )
246 {
248 }
249 else
250 {
252 }
253 }
254 else if ( quadOffsetX > 0 )
255 {
256 if ( quadOffsetY < 0 )
257 {
259 }
260 else if ( quadOffsetY > 0 )
261 {
263 }
264 else
265 {
267 }
268 }
269 else
270 {
271 if ( quadOffsetY < 0 )
272 {
274 }
275 else if ( quadOffsetY > 0 )
276 {
278 }
279 else
280 {
282 }
283 }
284}
285
287{
288 return mTotalRepeats;
289}
290
291void FeaturePart::setTotalRepeats( int totalRepeats )
292{
293 mTotalRepeats = totalRepeats;
294}
295
296std::size_t FeaturePart::createCandidateCenteredOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
297{
298 // get from feature
299 double labelW = getLabelWidth( angle );
300 double labelH = getLabelHeight( angle );
301
302 double cost = 0.00005;
303 int id = lPos.size();
304
305 double xdiff = -labelW / 2.0;
306 double ydiff = -labelH / 2.0;
307
309
310 double lx = x + xdiff;
311 double ly = y + ydiff;
312
314 {
315 if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), lx, ly, labelW, labelH, angle ) )
316 {
317 return 0;
318 }
319 }
320
321 lPos.emplace_back( std::make_unique< LabelPosition >( id, lx, ly, labelW, labelH, angle, cost, this, false, LabelPosition::QuadrantOver ) );
322 return 1;
323}
324
325std::size_t FeaturePart::createCandidatesOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
326{
327 // get from feature
328 double labelW = getLabelWidth( angle );
329 double labelH = getLabelHeight( angle );
330
331 double cost = 0.0001;
332 int id = lPos.size();
333
334 double xdiff = -labelW / 2.0;
335 double ydiff = -labelH / 2.0;
336
338
339 if ( !qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
340 {
341 xdiff += labelW / 2.0 * mLF->quadOffset().x();
342 }
343 if ( !qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
344 {
345 ydiff += labelH / 2.0 * mLF->quadOffset().y();
346 }
347
348 if ( ! mLF->hasFixedPosition() )
349 {
350 if ( !qgsDoubleNear( angle, 0.0 ) )
351 {
352 double xd = xdiff * std::cos( angle ) - ydiff * std::sin( angle );
353 double yd = xdiff * std::sin( angle ) + ydiff * std::cos( angle );
354 xdiff = xd;
355 ydiff = yd;
356 }
357 }
358
360 {
361 //if in "around point" placement mode, then we use the label distance to determine
362 //the label's offset
363 if ( qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
364 {
365 ydiff += mLF->quadOffset().y() * mLF->distLabel();
366 }
367 else if ( qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
368 {
369 xdiff += mLF->quadOffset().x() * mLF->distLabel();
370 }
371 else
372 {
373 xdiff += mLF->quadOffset().x() * M_SQRT1_2 * mLF->distLabel();
374 ydiff += mLF->quadOffset().y() * M_SQRT1_2 * mLF->distLabel();
375 }
376 }
377 else
378 {
379 if ( !qgsDoubleNear( mLF->positionOffset().x(), 0.0 ) )
380 {
381 xdiff += mLF->positionOffset().x();
382 }
383 if ( !qgsDoubleNear( mLF->positionOffset().y(), 0.0 ) )
384 {
385 ydiff += mLF->positionOffset().y();
386 }
387 }
388
389 double lx = x + xdiff;
390 double ly = y + ydiff;
391
393 {
394 if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), lx, ly, labelW, labelH, angle ) )
395 {
396 return 0;
397 }
398 }
399
400 lPos.emplace_back( std::make_unique< LabelPosition >( id, lx, ly, labelW, labelH, angle, cost, this, false, quadrantFromOffset() ) );
401 return 1;
402}
403
404std::unique_ptr<LabelPosition> FeaturePart::createCandidatePointOnSurface( PointSet *mapShape )
405{
406 double px, py;
407 try
408 {
409 GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
410 geos::unique_ptr pointGeom( GEOSPointOnSurface_r( geosctxt, mapShape->geos() ) );
411 if ( pointGeom )
412 {
413 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
414 unsigned int nPoints = 0;
415 GEOSCoordSeq_getSize_r( geosctxt, coordSeq, &nPoints );
416 if ( nPoints == 0 )
417 return nullptr;
418 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
419 }
420 }
421 catch ( GEOSException &e )
422 {
423 qWarning( "GEOS exception: %s", e.what() );
424 QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
425 return nullptr;
426 }
427
428 return std::make_unique< LabelPosition >( 0, px, py, getLabelWidth(), getLabelHeight(), 0.0, 0.0, this, false, LabelPosition::QuadrantOver );
429}
430
431void createCandidateAtOrderedPositionOverPoint( double &labelX, double &labelY, LabelPosition::Quadrant &quadrant, double x, double y, double labelWidth, double labelHeight, Qgis::LabelPredefinedPointPosition position, double distanceToLabel, const QgsMargins &visualMargin, double symbolWidthOffset, double symbolHeightOffset, double angle )
432{
433 double alpha = 0.0;
434 double deltaX = 0;
435 double deltaY = 0;
436
437 switch ( position )
438 {
441 alpha = 3 * M_PI_4;
442 deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
443 deltaY = -visualMargin.bottom() + symbolHeightOffset;
444 break;
445
447 quadrant = LabelPosition::QuadrantAboveRight; //right quadrant, so labels are left-aligned
448 alpha = M_PI_2;
449 deltaX = -labelWidth / 4.0 - visualMargin.left();
450 deltaY = -visualMargin.bottom() + symbolHeightOffset;
451 break;
452
455 alpha = M_PI_2;
456 deltaX = -labelWidth / 2.0;
457 deltaY = -visualMargin.bottom() + symbolHeightOffset;
458 break;
459
461 quadrant = LabelPosition::QuadrantAboveLeft; //left quadrant, so labels are right-aligned
462 alpha = M_PI_2;
463 deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
464 deltaY = -visualMargin.bottom() + symbolHeightOffset;
465 break;
466
469 alpha = M_PI_4;
470 deltaX = - visualMargin.left() + symbolWidthOffset;
471 deltaY = -visualMargin.bottom() + symbolHeightOffset;
472 break;
473
476 alpha = M_PI;
477 deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
478 deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
479 break;
480
483 alpha = 0.0;
484 deltaX = -visualMargin.left() + symbolWidthOffset;
485 deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
486 break;
487
490 alpha = 5 * M_PI_4;
491 deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
492 deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
493 break;
494
496 quadrant = LabelPosition::QuadrantBelowRight; //right quadrant, so labels are left-aligned
497 alpha = 3 * M_PI_2;
498 deltaX = -labelWidth / 4.0 - visualMargin.left();
499 deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
500 break;
501
504 alpha = 3 * M_PI_2;
505 deltaX = -labelWidth / 2.0;
506 deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
507 break;
508
510 quadrant = LabelPosition::QuadrantBelowLeft; //left quadrant, so labels are right-aligned
511 alpha = 3 * M_PI_2;
512 deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
513 deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
514 break;
515
518 alpha = 7 * M_PI_4;
519 deltaX = -visualMargin.left() + symbolWidthOffset;
520 deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
521 break;
522 }
523
524 // Take care of the label angle when creating candidates. See pr comments #44944 for details
525 // https://github.com/qgis/QGIS/pull/44944#issuecomment-914670088
526 QTransform transformRotation;
527 transformRotation.rotate( angle * 180 / M_PI );
528 transformRotation.map( deltaX, deltaY, &deltaX, &deltaY );
529
530 //have bearing, distance - calculate reference point
531 double referenceX = std::cos( alpha ) * distanceToLabel + x;
532 double referenceY = std::sin( alpha ) * distanceToLabel + y;
533
534 labelX = referenceX + deltaX;
535 labelY = referenceY + deltaY;
536}
537
538std::size_t FeaturePart::createCandidatesAtOrderedPositionsOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
539{
540 const QVector< Qgis::LabelPredefinedPointPosition > positions = mLF->predefinedPositionOrder();
541 double labelWidth = getLabelWidth( angle );
542 double labelHeight = getLabelHeight( angle );
543 double distanceToLabel = getLabelDistance();
544 const QgsMargins &visualMargin = mLF->visualMargin();
545
546 double symbolWidthOffset = ( mLF->offsetType() == Qgis::LabelOffsetType::FromSymbolBounds ? mLF->symbolSize().width() / 2.0 : 0.0 );
547 double symbolHeightOffset = ( mLF->offsetType() == Qgis::LabelOffsetType::FromSymbolBounds ? mLF->symbolSize().height() / 2.0 : 0.0 );
548
549 double cost = 0.0001;
550 std::size_t i = lPos.size();
551
552 const std::size_t maxNumberCandidates = mLF->layer()->maximumPointLabelCandidates();
553 std::size_t created = 0;
554 for ( Qgis::LabelPredefinedPointPosition position : positions )
555 {
557
558 double labelX = 0;
559 double labelY = 0;
560 createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel, visualMargin, symbolWidthOffset, symbolHeightOffset, angle );
561
562 if ( ! mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
563 {
564 lPos.emplace_back( std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant ) );
565 created++;
566 //TODO - tweak
567 cost += 0.001;
568 if ( maxNumberCandidates > 0 && created >= maxNumberCandidates )
569 break;
570 }
571 ++i;
572 }
573
574 return created;
575}
576
577std::size_t FeaturePart::createCandidatesAroundPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
578{
579 double labelWidth = getLabelWidth( angle );
580 double labelHeight = getLabelHeight( angle );
581 double distanceToLabel = getLabelDistance();
582
583 std::size_t maxNumberCandidates = mLF->layer()->maximumPointLabelCandidates();
584 if ( maxNumberCandidates == 0 )
585 maxNumberCandidates = 16;
586
587 int icost = 0;
588 int inc = 2;
589 int id = lPos.size();
590
591 double candidateAngleIncrement = 2 * M_PI / maxNumberCandidates; /* angle bw 2 pos */
592
593 /* various angles */
594 double a90 = M_PI_2;
595 double a180 = M_PI;
596 double a270 = a180 + a90;
597 double a360 = 2 * M_PI;
598
599 double gamma1, gamma2;
600
601 if ( distanceToLabel > 0 )
602 {
603 gamma1 = std::atan2( labelHeight / 2, distanceToLabel + labelWidth / 2 );
604 gamma2 = std::atan2( labelWidth / 2, distanceToLabel + labelHeight / 2 );
605 }
606 else
607 {
608 gamma1 = gamma2 = a90 / 3.0;
609 }
610
611 if ( gamma1 > a90 / 3.0 )
612 gamma1 = a90 / 3.0;
613
614 if ( gamma2 > a90 / 3.0 )
615 gamma2 = a90 / 3.0;
616
617 std::size_t numberCandidatesGenerated = 0;
618
619 std::size_t i;
620 double angleToCandidate;
621 for ( i = 0, angleToCandidate = M_PI_4; i < maxNumberCandidates; i++, angleToCandidate += candidateAngleIncrement )
622 {
623 double deltaX = 0.0;
624 double deltaY = 0.0;
625
626 if ( angleToCandidate > a360 )
627 angleToCandidate -= a360;
628
630
631 if ( angleToCandidate < gamma1 || angleToCandidate > a360 - gamma1 ) // on the right
632 {
633 deltaX = distanceToLabel;
634 double iota = ( angleToCandidate + gamma1 );
635 if ( iota > a360 - gamma1 )
636 iota -= a360;
637
638 //ly += -yrm/2.0 + tan(alpha)*(distlabel + xrm/2);
639 deltaY = -labelHeight + labelHeight * iota / ( 2 * gamma1 );
640
642 }
643 else if ( angleToCandidate < a90 - gamma2 ) // top-right
644 {
645 deltaX = distanceToLabel * std::cos( angleToCandidate );
646 deltaY = distanceToLabel * std::sin( angleToCandidate );
648 }
649 else if ( angleToCandidate < a90 + gamma2 ) // top
650 {
651 //lx += -xrm/2.0 - tan(alpha+a90)*(distlabel + yrm/2);
652 deltaX = -labelWidth * ( angleToCandidate - a90 + gamma2 ) / ( 2 * gamma2 );
653 deltaY = distanceToLabel;
655 }
656 else if ( angleToCandidate < a180 - gamma1 ) // top left
657 {
658 deltaX = distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
659 deltaY = distanceToLabel * std::sin( angleToCandidate );
661 }
662 else if ( angleToCandidate < a180 + gamma1 ) // left
663 {
664 deltaX = -distanceToLabel - labelWidth;
665 //ly += -yrm/2.0 - tan(alpha)*(distlabel + xrm/2);
666 deltaY = - ( angleToCandidate - a180 + gamma1 ) * labelHeight / ( 2 * gamma1 );
668 }
669 else if ( angleToCandidate < a270 - gamma2 ) // down - left
670 {
671 deltaX = distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
672 deltaY = distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
674 }
675 else if ( angleToCandidate < a270 + gamma2 ) // down
676 {
677 deltaY = -distanceToLabel - labelHeight;
678 //lx += -xrm/2.0 + tan(alpha+a90)*(distlabel + yrm/2);
679 deltaX = -labelWidth + ( angleToCandidate - a270 + gamma2 ) * labelWidth / ( 2 * gamma2 );
681 }
682 else if ( angleToCandidate < a360 ) // down - right
683 {
684 deltaX = distanceToLabel * std::cos( angleToCandidate );
685 deltaY = distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
687 }
688
689 // Take care of the label angle when creating candidates. See pr comments #44944 for details
690 // https://github.com/qgis/QGIS/pull/44944#issuecomment-914670088
691 QTransform transformRotation;
692 transformRotation.rotate( angle * 180 / M_PI );
693 transformRotation.map( deltaX, deltaY, &deltaX, &deltaY );
694
695 double labelX = x + deltaX;
696 double labelY = y + deltaY;
697
698 double cost;
699
700 if ( maxNumberCandidates == 1 )
701 cost = 0.0001;
702 else
703 cost = 0.0001 + 0.0020 * double( icost ) / double( maxNumberCandidates - 1 );
704
705
707 {
708 if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
709 {
710 continue;
711 }
712 }
713
714 lPos.emplace_back( std::make_unique< LabelPosition >( id + i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant ) );
715 numberCandidatesGenerated++;
716
717 icost += inc;
718
719 if ( icost == static_cast< int >( maxNumberCandidates ) )
720 {
721 icost = static_cast< int >( maxNumberCandidates ) - 1;
722 inc = -2;
723 }
724 else if ( icost > static_cast< int >( maxNumberCandidates ) )
725 {
726 icost = static_cast< int >( maxNumberCandidates ) - 2;
727 inc = -2;
728 }
729
730 }
731
732 return numberCandidatesGenerated;
733}
734
735std::size_t FeaturePart::createCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
736{
737 if ( allowOverrun )
738 {
739 double shapeLength = mapShape->length();
740 if ( totalRepeats() > 1 && shapeLength < getLabelWidth() )
741 return 0;
742 else if ( shapeLength < getLabelWidth() - 2 * std::min( getLabelWidth(), mLF->overrunDistance() ) )
743 {
744 // label doesn't fit on this line, don't waste time trying to make candidates
745 return 0;
746 }
747 }
748
749 //prefer to label along straightish segments:
750 std::size_t candidates = 0;
751
753 candidates = createCandidatesAlongLineNearStraightSegments( lPos, mapShape, pal );
754
755 const std::size_t candidateTargetCount = maximumLineCandidates();
756 if ( candidates < candidateTargetCount )
757 {
758 // but not enough candidates yet, so fallback to labeling near whole line's midpoint
759 candidates = createCandidatesAlongLineNearMidpoint( lPos, mapShape, candidates > 0 ? 0.01 : 0.0, pal );
760 }
761 return candidates;
762}
763
764std::size_t FeaturePart::createHorizontalCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, Pal *pal )
765{
766 const double labelWidth = getLabelWidth();
767 const double labelHeight = getLabelHeight();
768
769 PointSet *line = mapShape;
770 int nbPoints = line->nbPoints;
771 std::vector< double > &x = line->x;
772 std::vector< double > &y = line->y;
773
774 std::vector< double > segmentLengths( nbPoints - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
775 std::vector< double >distanceToSegment( nbPoints ); // absolute distance bw pt[0] and pt[i] along the line
776
777 double totalLineLength = 0.0; // line length
778 for ( int i = 0; i < line->nbPoints - 1; i++ )
779 {
780 if ( i == 0 )
781 distanceToSegment[i] = 0;
782 else
783 distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
784
785 segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
786 totalLineLength += segmentLengths[i];
787 }
788 distanceToSegment[line->nbPoints - 1] = totalLineLength;
789
790 const std::size_t candidateTargetCount = maximumLineCandidates();
791 double lineStepDistance = 0;
792
793 const double lineAnchorPoint = totalLineLength * mLF->lineAnchorPercent();
794 double currentDistanceAlongLine = lineStepDistance;
795 switch ( mLF->lineAnchorType() )
796 {
798 lineStepDistance = totalLineLength / ( candidateTargetCount + 1 ); // distance to move along line with each candidate
799 break;
800
802 currentDistanceAlongLine = lineAnchorPoint;
803 lineStepDistance = -1;
804 break;
805 }
806
808
809 double candidateCenterX, candidateCenterY;
810 int i = 0;
811 while ( currentDistanceAlongLine <= totalLineLength )
812 {
813 if ( pal->isCanceled() )
814 {
815 return lPos.size();
816 }
817
818 line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateCenterX, &candidateCenterY );
819
820 // penalize positions which are further from the line's anchor point
821 double cost = std::fabs( lineAnchorPoint - currentDistanceAlongLine ) / totalLineLength; // <0, 0.5>
822 cost /= 1000; // < 0, 0.0005 >
823
824 double labelX = 0;
825 switch ( textPoint )
826 {
828 labelX = candidateCenterX;
829 break;
831 labelX = candidateCenterX - labelWidth / 2;
832 break;
834 labelX = candidateCenterX - labelWidth;
835 break;
837 // not possible here
838 break;
839 }
840 lPos.emplace_back( std::make_unique< LabelPosition >( i, labelX, candidateCenterY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) );
841
842 currentDistanceAlongLine += lineStepDistance;
843
844 i++;
845
846 if ( lineStepDistance < 0 )
847 break;
848 }
849
850 return lPos.size();
851}
852
853std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
854{
855 double labelWidth = getLabelWidth();
856 double labelHeight = getLabelHeight();
857 double distanceLineToLabel = getLabelDistance();
858 QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
859 if ( flags == 0 )
860 flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
861
862 // first scan through the whole line and look for segments where the angle at a node is greater than 45 degrees - these form a "hard break" which labels shouldn't cross over
863 QVector< int > extremeAngleNodes;
864 PointSet *line = mapShape;
865 int numberNodes = line->nbPoints;
866 std::vector< double > &x = line->x;
867 std::vector< double > &y = line->y;
868
869 // closed line? if so, we need to handle the final node angle
870 bool closedLine = qgsDoubleNear( x[0], x[ numberNodes - 1] ) && qgsDoubleNear( y[0], y[numberNodes - 1 ] );
871 for ( int i = 1; i <= numberNodes - ( closedLine ? 1 : 2 ); ++i )
872 {
873 double x1 = x[i - 1];
874 double x2 = x[i];
875 double x3 = x[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
876 double y1 = y[i - 1];
877 double y2 = y[i];
878 double y3 = y[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
879 if ( qgsDoubleNear( y2, y3 ) && qgsDoubleNear( x2, x3 ) )
880 continue;
881 if ( qgsDoubleNear( y1, y2 ) && qgsDoubleNear( x1, x2 ) )
882 continue;
883 double vertexAngle = M_PI - ( std::atan2( y3 - y2, x3 - x2 ) - std::atan2( y2 - y1, x2 - x1 ) );
884 vertexAngle = QgsGeometryUtils::normalizedAngle( vertexAngle );
885
886 // extreme angles form more than 45 degree angle at a node - these are the ones we don't want labels to cross
887 if ( vertexAngle < M_PI * 135.0 / 180.0 || vertexAngle > M_PI * 225.0 / 180.0 )
888 extremeAngleNodes << i;
889 }
890 extremeAngleNodes << numberNodes - 1;
891
892 if ( extremeAngleNodes.isEmpty() )
893 {
894 // no extreme angles - createCandidatesAlongLineNearMidpoint will be more appropriate
895 return 0;
896 }
897
898 // calculate lengths of segments, and work out longest straight-ish segment
899 std::vector< double > segmentLengths( numberNodes - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
900 std::vector< double > distanceToSegment( numberNodes ); // absolute distance bw pt[0] and pt[i] along the line
901 double totalLineLength = 0.0;
902 QVector< double > straightSegmentLengths;
903 QVector< double > straightSegmentAngles;
904 straightSegmentLengths.reserve( extremeAngleNodes.size() + 1 );
905 straightSegmentAngles.reserve( extremeAngleNodes.size() + 1 );
906 double currentStraightSegmentLength = 0;
907 double longestSegmentLength = 0;
908 int segmentIndex = 0;
909 double segmentStartX = x[0];
910 double segmentStartY = y[0];
911 for ( int i = 0; i < numberNodes - 1; i++ )
912 {
913 if ( i == 0 )
914 distanceToSegment[i] = 0;
915 else
916 distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
917
918 segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
919 totalLineLength += segmentLengths[i];
920 if ( extremeAngleNodes.contains( i ) )
921 {
922 // at an extreme angle node, so reset counters
923 straightSegmentLengths << currentStraightSegmentLength;
924 straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[i] - segmentStartY, x[i] - segmentStartX ) );
925 longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
926 segmentIndex++;
927 currentStraightSegmentLength = 0;
928 segmentStartX = x[i];
929 segmentStartY = y[i];
930 }
931 currentStraightSegmentLength += segmentLengths[i];
932 }
933 distanceToSegment[line->nbPoints - 1] = totalLineLength;
934 straightSegmentLengths << currentStraightSegmentLength;
935 straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[numberNodes - 1] - segmentStartY, x[numberNodes - 1] - segmentStartX ) );
936 longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
937 const double lineAnchorPoint = totalLineLength * mLF->lineAnchorPercent();
938
939 if ( totalLineLength < labelWidth )
940 {
941 return 0; //createCandidatesAlongLineNearMidpoint will be more appropriate
942 }
943
945
946 const std::size_t candidateTargetCount = maximumLineCandidates();
947 double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
948 lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
949
950 double distanceToEndOfSegment = 0.0;
951 int lastNodeInSegment = 0;
952 // finally, loop through all these straight segments. For each we create candidates along the straight segment.
953 for ( int i = 0; i < straightSegmentLengths.count(); ++i )
954 {
955 currentStraightSegmentLength = straightSegmentLengths.at( i );
956 double currentSegmentAngle = straightSegmentAngles.at( i );
957 lastNodeInSegment = extremeAngleNodes.at( i );
958 double distanceToStartOfSegment = distanceToEndOfSegment;
959 distanceToEndOfSegment = distanceToSegment[ lastNodeInSegment ];
960 double distanceToCenterOfSegment = 0.5 * ( distanceToEndOfSegment + distanceToStartOfSegment );
961
962 if ( currentStraightSegmentLength < labelWidth )
963 // can't fit a label on here
964 continue;
965
966 double currentDistanceAlongLine = distanceToStartOfSegment;
967 double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
968 double candidateLength = 0.0;
969 double cost = 0.0;
970 double angle = 0.0;
971 double beta = 0.0;
972
973 //calculate some cost penalties
974 double segmentCost = 1.0 - ( distanceToEndOfSegment - distanceToStartOfSegment ) / longestSegmentLength; // 0 -> 1 (lower for longer segments)
975 double segmentAngleCost = 1 - std::fabs( std::fmod( currentSegmentAngle, M_PI ) - M_PI_2 ) / M_PI_2; // 0 -> 1, lower for more horizontal segments
976
977 while ( currentDistanceAlongLine + labelWidth < distanceToEndOfSegment )
978 {
979 if ( pal->isCanceled() )
980 {
981 return lPos.size();
982 }
983
984 // calculate positions along linestring corresponding to start and end of current label candidate
985 line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
986 line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
987
988 candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
989
990
991 // LOTS OF DIFFERENT COSTS TO BALANCE HERE - feel free to tweak these, but please add a unit test
992 // which covers the situation you are adjusting for (e.g., "given equal length lines, choose the more horizontal line")
993
994 cost = candidateLength / labelWidth;
995 if ( cost > 0.98 )
996 cost = 0.0001;
997 else
998 {
999 // jaggy line has a greater cost
1000 cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
1001 }
1002
1003 const double labelCenter = currentDistanceAlongLine + labelWidth / 2.0;
1004 double labelTextAnchor = 0;
1005 switch ( textPoint )
1006 {
1008 labelTextAnchor = currentDistanceAlongLine;
1009 break;
1011 labelTextAnchor = currentDistanceAlongLine + labelWidth / 2.0;
1012 break;
1014 labelTextAnchor = currentDistanceAlongLine + labelWidth;
1015 break;
1017 // not possible here
1018 break;
1019 }
1020
1021 const bool placementIsFlexible = mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1022 // penalize positions which are further from the straight segments's midpoint
1023 if ( placementIsFlexible )
1024 {
1025 // only apply this if labels are being placed toward the center of overall lines -- otherwise it messes with the distance from anchor cost
1026 double costCenter = 2 * std::fabs( labelCenter - distanceToCenterOfSegment ) / ( distanceToEndOfSegment - distanceToStartOfSegment ); // 0 -> 1
1027 cost += costCenter * 0.0005; // < 0, 0.0005 >
1028 }
1029
1030 if ( !closedLine )
1031 {
1032 // penalize positions which are further from line anchor point of whole linestring (by default the middle of the line)
1033 // this only applies to non closed linestrings, since the middle of a closed linestring is effectively arbitrary
1034 // and irrelevant to labeling
1035 double costLineCenter = 2 * std::fabs( labelTextAnchor - lineAnchorPoint ) / totalLineLength; // 0 -> 1
1036 cost += costLineCenter * 0.0005; // < 0, 0.0005 >
1037 }
1038
1039 if ( placementIsFlexible )
1040 {
1041 cost += segmentCost * 0.0005; // prefer labels on longer straight segments
1042 cost += segmentAngleCost * 0.0001; // prefer more horizontal segments, but this is less important than length considerations
1043 }
1044
1045 if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
1046 {
1047 angle = 0.0;
1048 }
1049 else
1050 angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1051
1052 labelWidth = getLabelWidth( angle );
1053 labelHeight = getLabelHeight( angle );
1054 beta = angle + M_PI_2;
1055
1057 {
1058 // find out whether the line direction for this candidate is from right to left
1059 bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1060 // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1061 bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1062 bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1063 bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1064
1065 if ( belowLine )
1066 {
1067 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1068 {
1069 const double candidateCost = cost + ( reversed ? 0 : 0.001 );
1070 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1071 }
1072 }
1073 if ( aboveLine )
1074 {
1075 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1076 {
1077 const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1078 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1079 }
1080 }
1081 if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1082 {
1083 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1084 {
1085 const double candidateCost = cost + 0.002;
1086 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1087 }
1088 }
1089 }
1091 {
1092 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1093 }
1094 else
1095 {
1096 // an invalid arrangement?
1097 }
1098
1099 currentDistanceAlongLine += lineStepDistance;
1100 }
1101 }
1102
1103 return lPos.size();
1104}
1105
1106std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost, Pal *pal )
1107{
1108 double distanceLineToLabel = getLabelDistance();
1109
1110 double labelWidth = getLabelWidth();
1111 double labelHeight = getLabelHeight();
1112
1113 double angle;
1114 double cost;
1115
1116 QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1117 if ( flags == 0 )
1118 flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1119
1120 PointSet *line = mapShape;
1121 int nbPoints = line->nbPoints;
1122 std::vector< double > &x = line->x;
1123 std::vector< double > &y = line->y;
1124
1125 std::vector< double > segmentLengths( nbPoints - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
1126 std::vector< double >distanceToSegment( nbPoints ); // absolute distance bw pt[0] and pt[i] along the line
1127
1128 double totalLineLength = 0.0; // line length
1129 for ( int i = 0; i < line->nbPoints - 1; i++ )
1130 {
1131 if ( i == 0 )
1132 distanceToSegment[i] = 0;
1133 else
1134 distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
1135
1136 segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
1137 totalLineLength += segmentLengths[i];
1138 }
1139 distanceToSegment[line->nbPoints - 1] = totalLineLength;
1140
1141 double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
1142 double currentDistanceAlongLine = 0;
1143
1145
1146 const std::size_t candidateTargetCount = maximumLineCandidates();
1147
1148 if ( totalLineLength > labelWidth )
1149 {
1150 lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
1151 }
1152 else if ( !line->isClosed() ) // line length < label width => centering label position
1153 {
1154 currentDistanceAlongLine = - ( labelWidth - totalLineLength ) / 2.0;
1155 lineStepDistance = -1;
1156 totalLineLength = labelWidth;
1157 }
1158 else
1159 {
1160 // closed line, not long enough for label => no candidates!
1161 currentDistanceAlongLine = std::numeric_limits< double >::max();
1162 }
1163
1164 const double lineAnchorPoint = totalLineLength * std::min( 0.99, mLF->lineAnchorPercent() ); // don't actually go **all** the way to end of line, just very close to!
1165
1166 switch ( mLF->lineAnchorType() )
1167 {
1169 break;
1170
1172 switch ( textPoint )
1173 {
1175 currentDistanceAlongLine = std::min( lineAnchorPoint, totalLineLength * 0.99 - labelWidth );
1176 break;
1178 currentDistanceAlongLine = std::min( lineAnchorPoint - labelWidth / 2, totalLineLength * 0.99 - labelWidth );
1179 break;
1181 currentDistanceAlongLine = std::min( lineAnchorPoint - labelWidth, totalLineLength * 0.99 - labelWidth );
1182 break;
1184 // not possible here
1185 break;
1186 }
1187 lineStepDistance = -1;
1188 break;
1189 }
1190
1191 double candidateLength;
1192 double beta;
1193 double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
1194 int i = 0;
1195 while ( currentDistanceAlongLine <= totalLineLength - labelWidth || mLF->lineAnchorType() == QgsLabelLineSettings::AnchorType::Strict )
1196 {
1197 if ( pal->isCanceled() )
1198 {
1199 return lPos.size();
1200 }
1201
1202 // calculate positions along linestring corresponding to start and end of current label candidate
1203 line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
1204 line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
1205
1206 if ( currentDistanceAlongLine < 0 )
1207 {
1208 // label is bigger than line, use whole available line
1209 candidateLength = std::sqrt( ( x[nbPoints - 1] - x[0] ) * ( x[nbPoints - 1] - x[0] )
1210 + ( y[nbPoints - 1] - y[0] ) * ( y[nbPoints - 1] - y[0] ) );
1211 }
1212 else
1213 {
1214 candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
1215 }
1216
1217 cost = candidateLength / labelWidth;
1218 if ( cost > 0.98 )
1219 cost = 0.0001;
1220 else
1221 {
1222 // jaggy line has a greater cost
1223 cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
1224 }
1225
1226 // penalize positions which are further from the line's anchor point
1227 double textAnchorPoint = 0;
1228 switch ( textPoint )
1229 {
1231 textAnchorPoint = currentDistanceAlongLine;
1232 break;
1234 textAnchorPoint = currentDistanceAlongLine + labelWidth / 2;
1235 break;
1237 textAnchorPoint = currentDistanceAlongLine + labelWidth;
1238 break;
1240 // not possible here
1241 break;
1242 }
1243 double costCenter = std::fabs( lineAnchorPoint - textAnchorPoint ) / totalLineLength; // <0, 0.5>
1244 cost += costCenter / 1000; // < 0, 0.0005 >
1245 cost += initialCost;
1246
1247 if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
1248 {
1249 angle = 0.0;
1250 }
1251 else
1252 angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1253
1254 labelWidth = getLabelWidth( angle );
1255 labelHeight = getLabelHeight( angle );
1256 beta = angle + M_PI_2;
1257
1259 {
1260 // find out whether the line direction for this candidate is from right to left
1261 bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1262 // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1263 bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1264 bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1265 bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1266
1267 if ( aboveLine )
1268 {
1269 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1270 {
1271 const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1272 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1273 }
1274 }
1275 if ( belowLine )
1276 {
1277 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1278 {
1279 const double candidateCost = cost + ( !reversed ? 0.001 : 0 );
1280 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1281 }
1282 }
1283 if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1284 {
1285 if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1286 {
1287 const double candidateCost = cost + 0.002;
1288 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1289 }
1290 }
1291 }
1293 {
1294 lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1295 }
1296 else
1297 {
1298 // an invalid arrangement?
1299 }
1300
1301 currentDistanceAlongLine += lineStepDistance;
1302
1303 i++;
1304
1305 if ( lineStepDistance < 0 )
1306 break;
1307 }
1308
1309 return lPos.size();
1310}
1311
1312std::unique_ptr< LabelPosition > FeaturePart::curvedPlacementAtOffset( PointSet *mapShape, const std::vector< double> &pathDistances, QgsTextRendererUtils::LabelLineDirection direction, const double offsetAlongLine, bool &labeledLineSegmentIsRightToLeft, bool applyAngleConstraints, bool uprightOnly )
1313{
1314 const QgsPrecalculatedTextMetrics *metrics = qgis::down_cast< QgsTextLabelFeature * >( mLF )->textMetrics();
1315 Q_ASSERT( metrics );
1316
1317 const double maximumCharacterAngleInside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleInside() ) : -1;
1318 const double maximumCharacterAngleOutside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleOutside() ) : -1;
1319
1320 std::unique_ptr< QgsTextRendererUtils::CurvePlacementProperties > placement(
1321 QgsTextRendererUtils::generateCurvedTextPlacement( *metrics, mapShape->x.data(), mapShape->y.data(), mapShape->nbPoints, pathDistances, offsetAlongLine, direction, maximumCharacterAngleInside, maximumCharacterAngleOutside, uprightOnly )
1322 );
1323
1324 labeledLineSegmentIsRightToLeft = !uprightOnly ? placement->labeledLineSegmentIsRightToLeft : placement->flippedCharacterPlacementToGetUprightLabels;
1325
1326 if ( placement->graphemePlacement.empty() )
1327 return nullptr;
1328
1329 auto it = placement->graphemePlacement.constBegin();
1330 std::unique_ptr< LabelPosition > firstPosition = std::make_unique< LabelPosition >( 0, it->x, it->y, it->width, it->height, it->angle, 0.0001, this, false, LabelPosition::QuadrantOver );
1331 firstPosition->setUpsideDownCharCount( placement->upsideDownCharCount );
1332 firstPosition->setPartId( it->graphemeIndex );
1333 LabelPosition *previousPosition = firstPosition.get();
1334 it++;
1335 while ( it != placement->graphemePlacement.constEnd() )
1336 {
1337 std::unique_ptr< LabelPosition > position = std::make_unique< LabelPosition >( 0, it->x, it->y, it->width, it->height, it->angle, 0.0001, this, false, LabelPosition::QuadrantOver );
1338 position->setPartId( it->graphemeIndex );
1339
1340 LabelPosition *nextPosition = position.get();
1341 previousPosition->setNextPart( std::move( position ) );
1342 previousPosition = nextPosition;
1343 it++;
1344 }
1345
1346 return firstPosition;
1347}
1348
1349std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
1350{
1351 const QgsPrecalculatedTextMetrics *li = qgis::down_cast< QgsTextLabelFeature *>( mLF )->textMetrics();
1352 Q_ASSERT( li );
1353
1354 // label info must be present
1355 if ( !li )
1356 return 0;
1357
1358 const int characterCount = li->count();
1359 if ( characterCount == 0 )
1360 return 0;
1361
1362 // TODO - we may need an explicit penalty for overhanging labels. Currently, they are penalized just because they
1363 // are further from the line center, so non-overhanding placements are picked where possible.
1364
1365 double totalCharacterWidth = 0;
1366 for ( int i = 0; i < characterCount; ++i )
1367 totalCharacterWidth += li->characterWidth( i );
1368
1369 std::unique_ptr< PointSet > expanded;
1370 double shapeLength = mapShape->length();
1371
1372 if ( totalRepeats() > 1 )
1373 allowOverrun = false;
1374
1375 // unless in strict mode, label overrun should NEVER exceed the label length (or labels would sit off in space).
1376 // in fact, let's require that a minimum of 5% of the label text has to sit on the feature,
1377 // as we don't want a label sitting right at the start or end corner of a line
1378 double overrun = 0;
1379 switch ( mLF->lineAnchorType() )
1380 {
1382 overrun = std::min( mLF->overrunDistance(), totalCharacterWidth * 0.95 );
1383 break;
1385 // in strict mode, we force sufficient overrun to ensure label will always "fit", even if it's placed
1386 // so that the label start sits right on the end of the line OR the label end sits right on the start of the line
1387 overrun = std::max( mLF->overrunDistance(), totalCharacterWidth * 1.05 );
1388 break;
1389 }
1390
1391 if ( totalCharacterWidth > shapeLength )
1392 {
1393 if ( !allowOverrun || shapeLength < totalCharacterWidth - 2 * overrun )
1394 {
1395 // label doesn't fit on this line, don't waste time trying to make candidates
1396 return 0;
1397 }
1398 }
1399
1400 // calculate the anchor point for the original line shape as a GEOS point.
1401 // this must be done BEFORE we account for overrun by extending the shape!
1402 const geos::unique_ptr originalPoint = mapShape->interpolatePoint( shapeLength * mLF->lineAnchorPercent() );
1403
1404 if ( allowOverrun && overrun > 0 )
1405 {
1406 // expand out line on either side to fit label
1407 expanded = mapShape->clone();
1408 expanded->extendLineByDistance( overrun, overrun, mLF->overrunSmoothDistance() );
1409 mapShape = expanded.get();
1410 shapeLength += 2 * overrun;
1411 }
1412
1413 QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1414 if ( flags == 0 )
1415 flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1416 const bool hasAboveBelowLinePlacement = flags & QgsLabeling::LinePlacementFlag::AboveLine || flags & QgsLabeling::LinePlacementFlag::BelowLine;
1417 const double offsetDistance = mLF->distLabel() + li->characterHeight( 0 ) / 2;
1418 std::unique_ptr< PointSet > mapShapeOffsetPositive;
1419 bool positiveShapeHasNegativeDistance = false;
1420 std::unique_ptr< PointSet > mapShapeOffsetNegative;
1421 bool negativeShapeHasNegativeDistance = false;
1422 if ( hasAboveBelowLinePlacement && !qgsDoubleNear( offsetDistance, 0 ) )
1423 {
1424 // create offseted map shapes to be used for above and below line placements
1425 if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1426 mapShapeOffsetPositive = mapShape->clone();
1427 if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1428 mapShapeOffsetNegative = mapShape->clone();
1429 if ( offsetDistance >= 0.0 || !( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) )
1430 {
1431 if ( mapShapeOffsetPositive )
1432 mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance );
1433 positiveShapeHasNegativeDistance = offsetDistance < 0;
1434 if ( mapShapeOffsetNegative )
1435 mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance * -1 );
1436 negativeShapeHasNegativeDistance = offsetDistance > 0;
1437 }
1438 else
1439 {
1440 // In case of a negative offset distance, above line placement switch to below line and vice versa
1441 if ( flags & QgsLabeling::LinePlacementFlag::AboveLine
1442 && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1443 {
1444 flags &= ~QgsLabeling::LinePlacementFlag::AboveLine;
1445 flags |= QgsLabeling::LinePlacementFlag::BelowLine;
1446 }
1447 else if ( flags & QgsLabeling::LinePlacementFlag::BelowLine
1448 && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1449 {
1450 flags &= ~QgsLabeling::LinePlacementFlag::BelowLine;
1451 flags |= QgsLabeling::LinePlacementFlag::AboveLine;
1452 }
1453 if ( mapShapeOffsetPositive )
1454 mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance * -1 );
1455 positiveShapeHasNegativeDistance = offsetDistance > 0;
1456 if ( mapShapeOffsetNegative )
1457 mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance );
1458 negativeShapeHasNegativeDistance = offsetDistance < 0;
1459 }
1460 }
1461
1463
1464 std::vector< std::unique_ptr< LabelPosition >> positions;
1465 std::unique_ptr< LabelPosition > backupPlacement;
1466 for ( PathOffset offset : { PositiveOffset, NoOffset, NegativeOffset } )
1467 {
1468 PointSet *currentMapShape = nullptr;
1469 if ( offset == PositiveOffset && hasAboveBelowLinePlacement )
1470 {
1471 currentMapShape = mapShapeOffsetPositive.get();
1472 }
1473 if ( offset == NoOffset && flags & QgsLabeling::LinePlacementFlag::OnLine )
1474 {
1475 currentMapShape = mapShape;
1476 }
1477 if ( offset == NegativeOffset && hasAboveBelowLinePlacement )
1478 {
1479 currentMapShape = mapShapeOffsetNegative.get();
1480 }
1481 if ( !currentMapShape )
1482 continue;
1483
1484 // distance calculation
1485 const auto [ pathDistances, totalDistance ] = currentMapShape->edgeDistances();
1486 if ( qgsDoubleNear( totalDistance, 0.0 ) )
1487 continue;
1488
1489 double lineAnchorPoint = 0;
1490 if ( originalPoint && offset != NoOffset )
1491 {
1492 // the actual anchor point for the offset curves is the closest point on those offset curves
1493 // to the anchor point on the original line. This avoids anchor points which differ greatly
1494 // on the positive/negative offset lines due to line curvature.
1495 lineAnchorPoint = currentMapShape->lineLocatePoint( originalPoint.get() );
1496 }
1497 else
1498 {
1499 lineAnchorPoint = totalDistance * mLF->lineAnchorPercent();
1500 if ( offset == NegativeOffset )
1501 lineAnchorPoint = totalDistance - lineAnchorPoint;
1502 }
1503
1504 if ( pal->isCanceled() )
1505 return 0;
1506
1507 const std::size_t candidateTargetCount = maximumLineCandidates();
1508 double delta = std::max( li->characterHeight( 0 ) / 6, totalDistance / candidateTargetCount );
1509
1510 // generate curved labels
1511 double distanceAlongLineToStartCandidate = 0;
1512 bool singleCandidateOnly = false;
1513 switch ( mLF->lineAnchorType() )
1514 {
1516 break;
1517
1519 switch ( textPoint )
1520 {
1522 distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint, 0.0, totalDistance * 0.999 );
1523 break;
1525 distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint - getLabelWidth() / 2, 0.0, totalDistance * 0.999 - getLabelWidth() / 2 );
1526 break;
1528 distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint - getLabelWidth(), 0.0, totalDistance * 0.999 - getLabelWidth() ) ;
1529 break;
1531 // not possible here
1532 break;
1533 }
1534 singleCandidateOnly = true;
1535 break;
1536 }
1537
1538 bool hasTestedFirstPlacement = false;
1539 for ( ; distanceAlongLineToStartCandidate <= totalDistance; distanceAlongLineToStartCandidate += delta )
1540 {
1541 if ( singleCandidateOnly && hasTestedFirstPlacement )
1542 break;
1543
1544 if ( pal->isCanceled() )
1545 return 0;
1546
1547 hasTestedFirstPlacement = true;
1548 // placements may need to be reversed if using map orientation and the line has right-to-left direction
1549 bool labeledLineSegmentIsRightToLeft = false;
1550 const QgsTextRendererUtils::LabelLineDirection direction = ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? QgsTextRendererUtils::RespectPainterOrientation : QgsTextRendererUtils::FollowLineDirection;
1551 std::unique_ptr< LabelPosition > labelPosition = curvedPlacementAtOffset( currentMapShape, pathDistances, direction, distanceAlongLineToStartCandidate, labeledLineSegmentIsRightToLeft, !singleCandidateOnly,
1552 onlyShowUprightLabels() && ( !singleCandidateOnly || !( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ) );
1553
1554 if ( !labelPosition )
1555 {
1556 continue;
1557 }
1558
1559
1560 bool isBackupPlacementOnly = false;
1561 if ( flags & QgsLabeling::LinePlacementFlag::MapOrientation )
1562 {
1563 if ( ( currentMapShape == mapShapeOffsetPositive.get() && positiveShapeHasNegativeDistance )
1564 || ( currentMapShape == mapShapeOffsetNegative.get() && negativeShapeHasNegativeDistance ) )
1565 {
1566 labeledLineSegmentIsRightToLeft = !labeledLineSegmentIsRightToLeft;
1567 }
1568
1569 if ( ( offset != NoOffset ) && !labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1570 {
1571 if ( singleCandidateOnly && offset == PositiveOffset )
1572 isBackupPlacementOnly = true;
1573 else
1574 continue;
1575 }
1576 if ( ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1577 {
1578 if ( singleCandidateOnly && offset == PositiveOffset )
1579 isBackupPlacementOnly = true;
1580 else
1581 continue;
1582 }
1583 }
1584
1585 backupPlacement.reset();
1586
1587 // evaluate cost
1588 const double angleDiff = labelPosition->angleDifferential();
1589 const double angleDiffAvg = characterCount > 1 ? ( angleDiff / ( characterCount - 1 ) ) : 0; // <0, pi> but pi/8 is much already
1590
1591 // if anchor placement is towards start or end of line, we need to slightly tweak the costs to ensure that the
1592 // anchor weighting is sufficient to push labels towards start/end
1593 const bool anchorIsFlexiblePlacement = !singleCandidateOnly && mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1594 double cost = angleDiffAvg / 100; // <0, 0.031 > but usually <0, 0.003 >
1595 if ( cost < 0.0001 )
1596 cost = 0.0001;
1597
1598 // penalize positions which are further from the line's anchor point
1599 double labelTextAnchor = 0;
1600 switch ( textPoint )
1601 {
1603 labelTextAnchor = distanceAlongLineToStartCandidate;
1604 break;
1606 labelTextAnchor = distanceAlongLineToStartCandidate + getLabelWidth() / 2;
1607 break;
1609 labelTextAnchor = distanceAlongLineToStartCandidate + getLabelWidth();
1610 break;
1612 // not possible here
1613 break;
1614 }
1615 double costCenter = std::fabs( lineAnchorPoint - labelTextAnchor ) / totalDistance; // <0, 0.5>
1616 cost += costCenter / ( anchorIsFlexiblePlacement ? 100 : 10 ); // < 0, 0.005 >, or <0, 0.05> if preferring placement close to start/end of line
1617
1618 const bool isBelow = ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft;
1619 if ( isBelow )
1620 {
1621 // add additional cost for on line placement
1622 cost += 0.001;
1623 }
1624 else if ( offset == NoOffset )
1625 {
1626 // add additional cost for below line placement
1627 cost += 0.002;
1628 }
1629
1630 labelPosition->setCost( cost );
1631
1632 std::unique_ptr< LabelPosition > p = std::make_unique< LabelPosition >( *labelPosition );
1633 if ( p && mLF->permissibleZonePrepared() )
1634 {
1635 bool within = true;
1636 LabelPosition *currentPos = p.get();
1637 while ( within && currentPos )
1638 {
1639 within = GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), currentPos->getX(), currentPos->getY(), currentPos->getWidth(), currentPos->getHeight(), currentPos->getAlpha() );
1640 currentPos = currentPos->nextPart();
1641 }
1642 if ( !within )
1643 {
1644 p.reset();
1645 }
1646 }
1647
1648 if ( p )
1649 {
1650 if ( isBackupPlacementOnly )
1651 backupPlacement = std::move( p );
1652 else
1653 positions.emplace_back( std::move( p ) );
1654 }
1655 }
1656 }
1657
1658 for ( std::unique_ptr< LabelPosition > &pos : positions )
1659 {
1660 lPos.emplace_back( std::move( pos ) );
1661 }
1662
1663 if ( backupPlacement )
1664 lPos.emplace_back( std::move( backupPlacement ) );
1665
1666 return positions.size();
1667}
1668
1669/*
1670 * seg 2
1671 * pt3 ____________pt2
1672 * ¦ ¦
1673 * ¦ ¦
1674 * seg 3 ¦ BBOX ¦ seg 1
1675 * ¦ ¦
1676 * ¦____________¦
1677 * pt0 seg 0 pt1
1678 *
1679 */
1680
1681std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
1682{
1683 double labelWidth = getLabelWidth();
1684 double labelHeight = getLabelHeight();
1685
1686 const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1687 const std::size_t targetPolygonCandidates = maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * area() ) ) )
1688 : 0;
1689
1690 const double totalArea = area();
1691
1692 mapShape->parent = nullptr;
1693
1694 if ( pal->isCanceled() )
1695 return 0;
1696
1697 QLinkedList<PointSet *> shapes_final = splitPolygons( mapShape, labelWidth, labelHeight );
1698#if 0
1699 QgsDebugMsg( QStringLiteral( "PAL split polygons resulted in:" ) );
1700 for ( PointSet *ps : shapes_final )
1701 {
1702 QgsDebugMsg( ps->toWkt() );
1703 }
1704#endif
1705
1706 std::size_t nbp = 0;
1707
1708 if ( !shapes_final.isEmpty() )
1709 {
1710 int id = 0; // ids for candidates
1711 double dlx, dly; // delta from label center and bottom-left corner
1712 double alpha = 0.0; // rotation for the label
1713 double px, py;
1714
1715 double beta;
1716 double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
1717 double rx, ry;
1718 std::vector< OrientedConvexHullBoundingBox > boxes;
1719 boxes.reserve( shapes_final.size() );
1720
1721 // Compute bounding box for each finalShape
1722 while ( !shapes_final.isEmpty() )
1723 {
1724 PointSet *shape = shapes_final.takeFirst();
1725 bool ok = false;
1727 if ( ok )
1728 boxes.emplace_back( box );
1729
1730 if ( shape->parent )
1731 delete shape;
1732 }
1733
1734 if ( pal->isCanceled() )
1735 return 0;
1736
1737 double densityX = 1.0 / std::sqrt( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() );
1738 double densityY = densityX;
1739 int numTry = 0;
1740
1741 //fit in polygon only mode slows down calculation a lot, so if it's enabled
1742 //then use a smaller limit for number of iterations
1743 int maxTry = mLF->permissibleZonePrepared() ? 7 : 10;
1744
1745 std::size_t numberCandidatesGenerated = 0;
1746
1747 do
1748 {
1749 for ( OrientedConvexHullBoundingBox &box : boxes )
1750 {
1751 // there is two possibilities here:
1752 // 1. no maximum candidates for polygon setting is in effect (i.e. maxPolygonCandidates == 0). In that case,
1753 // we base our dx/dy on the current maximumPolygonCandidatesPerMapUnitSquared value. That should give us the desired
1754 // density of candidates straight up. Easy!
1755 // 2. a maximum candidate setting IS in effect. In that case, we want to generate a good initial estimate for dx/dy
1756 // which gives us a good spatial coverage of the polygon while roughly matching the desired maximum number of candidates.
1757 // If dx/dy is too small, then too many candidates will be generated, which is both slow AND results in poor coverage of the
1758 // polygon (after culling candidates to the max number, only those clustered around the polygon's pole of inaccessibility
1759 // will remain).
1760 double dx = densityX;
1761 double dy = densityY;
1762 if ( numTry == 0 && maxPolygonCandidates > 0 )
1763 {
1764 // scale maxPolygonCandidates for just this convex hull
1765 const double boxArea = box.width * box.length;
1766 double maxThisBox = targetPolygonCandidates * boxArea / totalArea;
1767 dx = std::max( dx, std::sqrt( boxArea / maxThisBox ) * 0.8 );
1768 dy = dx;
1769 }
1770
1771 if ( pal->isCanceled() )
1772 return numberCandidatesGenerated;
1773
1774 if ( ( box.length * box.width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
1775 {
1776 // Very Large BBOX (should never occur)
1777 continue;
1778 }
1779
1781 {
1782 //check width/height of bbox is sufficient for label
1783 if ( mLF->permissibleZone().boundingBox().width() < labelWidth ||
1784 mLF->permissibleZone().boundingBox().height() < labelHeight )
1785 {
1786 //no way label can fit in this box, skip it
1787 continue;
1788 }
1789 }
1790
1791 bool enoughPlace = false;
1793 {
1794 enoughPlace = true;
1795 px = ( box.x[0] + box.x[2] ) / 2 - labelWidth;
1796 py = ( box.y[0] + box.y[2] ) / 2 - labelHeight;
1797 int i, j;
1798
1799 // Virtual label: center on bbox center, label size = 2x original size
1800 // alpha = 0.
1801 // If all corner are in bbox then place candidates horizontaly
1802 for ( rx = px, i = 0; i < 2; rx = rx + 2 * labelWidth, i++ )
1803 {
1804 for ( ry = py, j = 0; j < 2; ry = ry + 2 * labelHeight, j++ )
1805 {
1806 if ( !mapShape->containsPoint( rx, ry ) )
1807 {
1808 enoughPlace = false;
1809 break;
1810 }
1811 }
1812 if ( !enoughPlace )
1813 {
1814 break;
1815 }
1816 }
1817
1818 } // arrangement== FREE ?
1819
1820 if ( mLF->layer()->arrangement() == Qgis::LabelPlacement::Horizontal || enoughPlace )
1821 {
1822 alpha = 0.0; // HORIZ
1823 }
1824 else if ( box.length > 1.5 * labelWidth && box.width > 1.5 * labelWidth )
1825 {
1826 if ( box.alpha <= M_PI_4 )
1827 {
1828 alpha = box.alpha;
1829 }
1830 else
1831 {
1832 alpha = box.alpha - M_PI_2;
1833 }
1834 }
1835 else if ( box.length > box.width )
1836 {
1837 alpha = box.alpha - M_PI_2;
1838 }
1839 else
1840 {
1841 alpha = box.alpha;
1842 }
1843
1844 beta = std::atan2( labelHeight, labelWidth ) + alpha;
1845
1846
1847 //alpha = box->alpha;
1848
1849 // delta from label center and down-left corner
1850 dlx = std::cos( beta ) * diago;
1851 dly = std::sin( beta ) * diago;
1852
1853 double px0 = box.width / 2.0;
1854 double py0 = box.length / 2.0;
1855
1856 px0 -= std::ceil( px0 / dx ) * dx;
1857 py0 -= std::ceil( py0 / dy ) * dy;
1858
1859 for ( px = px0; px <= box.width; px += dx )
1860 {
1861 if ( pal->isCanceled() )
1862 break;
1863
1864 for ( py = py0; py <= box.length; py += dy )
1865 {
1866
1867 rx = std::cos( box.alpha ) * px + std::cos( box.alpha - M_PI_2 ) * py;
1868 ry = std::sin( box.alpha ) * px + std::sin( box.alpha - M_PI_2 ) * py;
1869
1870 rx += box.x[0];
1871 ry += box.y[0];
1872
1874 {
1875 if ( GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), rx - dlx, ry - dly, labelWidth, labelHeight, alpha ) )
1876 {
1877 // cost is set to minimal value, evaluated later
1878 lPos.emplace_back( std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver ) );
1879 numberCandidatesGenerated++;
1880 }
1881 }
1882 else
1883 {
1884 // TODO - this should be an intersection test, not just a contains test of the candidate centroid
1885 // because in some cases we would want to allow candidates which mostly overlap the polygon even though
1886 // their centroid doesn't overlap (e.g. a "U" shaped polygon)
1887 // but the bugs noted in CostCalculator currently prevent this
1888 if ( mapShape->containsPoint( rx, ry ) )
1889 {
1890 std::unique_ptr< LabelPosition > potentialCandidate = std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver );
1891 // cost is set to minimal value, evaluated later
1892 lPos.emplace_back( std::move( potentialCandidate ) );
1893 numberCandidatesGenerated++;
1894 }
1895 }
1896 }
1897 }
1898 } // forall box
1899
1900 nbp = numberCandidatesGenerated;
1901 if ( maxPolygonCandidates > 0 && nbp < targetPolygonCandidates )
1902 {
1903 densityX /= 2;
1904 densityY /= 2;
1905 numTry++;
1906 }
1907 else
1908 {
1909 break;
1910 }
1911 }
1912 while ( numTry < maxTry );
1913
1914 nbp = numberCandidatesGenerated;
1915 }
1916 else
1917 {
1918 nbp = 0;
1919 }
1920
1921 return nbp;
1922}
1923
1924std::size_t FeaturePart::createCandidatesOutsidePolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, Pal *pal )
1925{
1926 // calculate distance between horizontal lines
1927 const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1928 std::size_t candidatesCreated = 0;
1929
1930 double labelWidth = getLabelWidth();
1931 double labelHeight = getLabelHeight();
1932 double distanceToLabel = getLabelDistance();
1933 const QgsMargins &visualMargin = mLF->visualMargin();
1934
1935 /*
1936 * From Rylov & Reimer (2016) "A practical algorithm for the external annotation of area features":
1937 *
1938 * The list of rules adapted to the
1939 * needs of externally labelling areal features is as follows:
1940 * R1. Labels should be placed horizontally.
1941 * R2. Label should be placed entirely outside at some
1942 * distance from the area feature.
1943 * R3. Name should not cross the boundary of its area
1944 * feature.
1945 * R4. The name should be placed in way that takes into
1946 * account the shape of the feature by achieving a
1947 * balance between the feature and its name, emphasizing their relationship.
1948 * R5. The lettering to the right and slightly above the
1949 * symbol is prioritized.
1950 *
1951 * In the following subsections we utilize four of the five rules
1952 * for two subtasks of label placement, namely, for candidate
1953 * positions generation (R1, R2, and R3) and for measuring their
1954 * ‘goodness’ (R4). The rule R5 is applicable only in the case when
1955 * the area of a polygonal feature is small and the feature can be
1956 * treated and labelled as a point-feature
1957 */
1958
1959 /*
1960 * QGIS approach (cite Dawson (2020) if you want ;) )
1961 *
1962 * We differ from the horizontal sweep line approach described by Rylov & Reimer and instead
1963 * rely on just generating a set of points at regular intervals along the boundary of the polygon (exterior ring).
1964 *
1965 * In practice, this generates similar results as Rylov & Reimer, but has the additional benefits that:
1966 * 1. It avoids the need to calculate intersections between the sweep line and the polygon
1967 * 2. For horizontal or near horizontal segments, Rylov & Reimer propose generating evenly spaced points along
1968 * these segments-- i.e. the same approach as we do for the whole polygon
1969 * 3. It's easier to determine in advance exactly how many candidate positions we'll be generating, and accordingly
1970 * we can easily pick the distance between points along the exterior ring so that the number of positions generated
1971 * matches our target number (targetPolygonCandidates)
1972 */
1973
1974 // TO consider -- for very small polygons (wrt label size), treat them just like a point feature?
1975
1976 double cx, cy;
1977 getCentroid( cx, cy, false );
1978
1979 GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1980
1981 // be a bit sneaky and only buffer out 50% here, and then do the remaining 50% when we make the label candidate itself.
1982 // this avoids candidates being created immediately over the buffered ring and always intersecting with it...
1983 geos::unique_ptr buffer( GEOSBuffer_r( ctxt, geos(), distanceToLabel * 0.5, 1 ) );
1984 std::unique_ptr< QgsAbstractGeometry> gg( QgsGeos::fromGeos( buffer.get() ) );
1985
1986 geos::prepared_unique_ptr preparedBuffer( GEOSPrepare_r( ctxt, buffer.get() ) );
1987
1988 const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( gg.get() );
1989 if ( !poly )
1990 return candidatesCreated;
1991
1992 const QgsLineString *ring = qgsgeometry_cast< const QgsLineString *>( poly->exteriorRing() );
1993 if ( !ring )
1994 return candidatesCreated;
1995
1996 // we cheat here -- we don't use the polygon area when calculating the number of candidates, and rather use the perimeter (because that's more relevant,
1997 // i.e a loooooong skinny polygon with small area should still generate a large number of candidates)
1998 const double ringLength = ring->length();
1999 const double circleArea = std::pow( ringLength, 2 ) / ( 4 * M_PI );
2000 const std::size_t candidatesForArea = static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * circleArea ) );
2001 const std::size_t targetPolygonCandidates = std::max( static_cast< std::size_t >( 16 ), maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, candidatesForArea ) : candidatesForArea );
2002
2003 // assume each position generates one candidate
2004 const double delta = ringLength / targetPolygonCandidates;
2005 geos::unique_ptr geosPoint;
2006
2007 const double maxDistCentroidToLabelX = std::max( xmax - cx, cx - xmin ) + distanceToLabel;
2008 const double maxDistCentroidToLabelY = std::max( ymax - cy, cy - ymin ) + distanceToLabel;
2009 const double estimateOfMaxPossibleDistanceCentroidToLabel = std::sqrt( maxDistCentroidToLabelX * maxDistCentroidToLabelX + maxDistCentroidToLabelY * maxDistCentroidToLabelY );
2010
2011 // Satisfy R1: Labels should be placed horizontally.
2012 const double labelAngle = 0;
2013
2014 std::size_t i = lPos.size();
2015 auto addCandidate = [&]( double x, double y, Qgis::LabelPredefinedPointPosition position )
2016 {
2017 double labelX = 0;
2018 double labelY = 0;
2020
2021 // Satisfy R2: Label should be placed entirely outside at some distance from the area feature.
2022 createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel * 0.5, visualMargin, 0, 0, labelAngle );
2023
2024 std::unique_ptr< LabelPosition > candidate = std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, labelAngle, 0, this, false, quadrant );
2025 if ( candidate->intersects( preparedBuffer.get() ) )
2026 {
2027 // satisfy R3. Name should not cross the boundary of its area feature.
2028
2029 // actually, we use the buffered geometry here, because a label shouldn't be closer to the polygon then the minimum distance value
2030 return;
2031 }
2032
2033 // cost candidates by their distance to the feature's centroid (following Rylov & Reimer)
2034
2035 // Satisfy R4. The name should be placed in way that takes into
2036 // account the shape of the feature by achieving a
2037 // balance between the feature and its name, emphasizing their relationship.
2038
2039
2040 // here we deviate a little from R&R, and instead of just calculating the centroid distance
2041 // to centroid of label, we calculate the distance from the centroid to the nearest point on the label
2042
2043 const double centroidDistance = candidate->getDistanceToPoint( cx, cy, false );
2044 const double centroidCost = centroidDistance / estimateOfMaxPossibleDistanceCentroidToLabel;
2045 candidate->setCost( centroidCost );
2046
2047 lPos.emplace_back( std::move( candidate ) );
2048 candidatesCreated++;
2049 ++i;
2050 };
2051
2052 ring->visitPointsByRegularDistance( delta, [&]( double x, double y, double, double,
2053 double startSegmentX, double startSegmentY, double, double,
2054 double endSegmentX, double endSegmentY, double, double )
2055 {
2056 // get normal angle for segment
2057 float angle = atan2( static_cast< float >( endSegmentY - startSegmentY ), static_cast< float >( endSegmentX - startSegmentX ) ) * 180 / M_PI;
2058 if ( angle < 0 )
2059 angle += 360;
2060
2061 // adapted fom Rylov & Reimer figure 9
2062 if ( angle >= 0 && angle <= 5 )
2063 {
2066 }
2067 else if ( angle <= 85 )
2068 {
2070 }
2071 else if ( angle <= 90 )
2072 {
2075 }
2076
2077 else if ( angle <= 95 )
2078 {
2081 }
2082 else if ( angle <= 175 )
2083 {
2085 }
2086 else if ( angle <= 180 )
2087 {
2090 }
2091
2092 else if ( angle <= 185 )
2093 {
2096 }
2097 else if ( angle <= 265 )
2098 {
2100 }
2101 else if ( angle <= 270 )
2102 {
2105 }
2106 else if ( angle <= 275 )
2107 {
2110 }
2111 else if ( angle <= 355 )
2112 {
2114 }
2115 else
2116 {
2119 }
2120
2121 return !pal->isCanceled();
2122 } );
2123
2124 return candidatesCreated;
2125}
2126
2127std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates( Pal *pal )
2128{
2129 std::vector< std::unique_ptr< LabelPosition > > lPos;
2130 double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
2131
2132 if ( mLF->hasFixedPosition() )
2133 {
2134 lPos.emplace_back( std::make_unique< LabelPosition> ( 0, mLF->fixedPosition().x(), mLF->fixedPosition().y(), getLabelWidth( angle ), getLabelHeight( angle ), angle, 0.0, this, false, LabelPosition::Quadrant::QuadrantOver ) );
2135 }
2136 else
2137 {
2138 switch ( type )
2139 {
2140 case GEOS_POINT:
2144 createCandidatesOverPoint( x[0], y[0], lPos, angle );
2145 else
2146 createCandidatesAroundPoint( x[0], y[0], lPos, angle );
2147 break;
2148
2149 case GEOS_LINESTRING:
2152 else if ( mLF->layer()->isCurved() )
2153 createCurvedCandidatesAlongLine( lPos, this, true, pal );
2154 else
2155 createCandidatesAlongLine( lPos, this, true, pal );
2156 break;
2157
2158 case GEOS_POLYGON:
2159 {
2160 const double labelWidth = getLabelWidth();
2161 const double labelHeight = getLabelHeight();
2162
2163 const bool allowOutside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementOutsideOfPolygon;
2164 const bool allowInside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementInsideOfPolygon;
2165 //check width/height of bbox is sufficient for label
2166
2167 if ( ( allowOutside && !allowInside ) || ( mLF->layer()->arrangement() == Qgis::LabelPlacement::OutsidePolygons ) )
2168 {
2169 // only allowed to place outside of polygon
2171 }
2172 else if ( allowOutside && ( std::fabs( xmax - xmin ) < labelWidth ||
2173 std::fabs( ymax - ymin ) < labelHeight ) )
2174 {
2175 //no way label can fit in this polygon -- shortcut and only place label outside
2177 }
2178 else
2179 {
2180 std::size_t created = 0;
2181 if ( allowInside )
2182 {
2183 switch ( mLF->layer()->arrangement() )
2184 {
2186 {
2187 double cx, cy;
2188 getCentroid( cx, cy, mLF->layer()->centroidInside() );
2189 if ( qgsDoubleNear( mLF->distLabel(), 0.0 ) )
2190 created += createCandidateCenteredOverPoint( cx, cy, lPos, angle );
2191 created += createCandidatesAroundPoint( cx, cy, lPos, angle );
2192 break;
2193 }
2195 {
2196 double cx, cy;
2197 getCentroid( cx, cy, mLF->layer()->centroidInside() );
2198 created += createCandidatesOverPoint( cx, cy, lPos, angle );
2199 break;
2200 }
2202 created += createCandidatesAlongLine( lPos, this, false, pal );
2203 break;
2205 created += createCurvedCandidatesAlongLine( lPos, this, false, pal );
2206 break;
2207 default:
2208 created += createCandidatesForPolygon( lPos, this, pal );
2209 break;
2210 }
2211 }
2212
2213 if ( allowOutside )
2214 {
2215 // add fallback for labels outside the polygon
2217
2218 if ( created > 0 )
2219 {
2220 // TODO (maybe) increase cost for outside placements (i.e. positions at indices >= created)?
2221 // From my initial testing this doesn't seem necessary
2222 }
2223 }
2224 }
2225 }
2226 }
2227 }
2228
2229 return lPos;
2230}
2231
2232void FeaturePart::addSizePenalty( std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4] ) const
2233{
2234 if ( !mGeos )
2236
2237 GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2238 int geomType = GEOSGeomTypeId_r( ctxt, mGeos );
2239
2240 double sizeCost = 0;
2241 if ( geomType == GEOS_LINESTRING )
2242 {
2243 const double l = length();
2244 if ( l <= 0 )
2245 return; // failed to calculate length
2246 double bbox_length = std::max( bbx[2] - bbx[0], bby[2] - bby[0] );
2247 if ( l >= bbox_length / 4 )
2248 return; // the line is longer than quarter of height or width - don't penalize it
2249
2250 sizeCost = 1 - ( l / ( bbox_length / 4 ) ); // < 0,1 >
2251 }
2252 else if ( geomType == GEOS_POLYGON )
2253 {
2254 const double a = area();
2255 if ( a <= 0 )
2256 return;
2257 double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
2258 if ( a >= bbox_area / 16 )
2259 return; // covers more than 1/16 of our view - don't penalize it
2260
2261 sizeCost = 1 - ( a / ( bbox_area / 16 ) ); // < 0, 1 >
2262 }
2263 else
2264 return; // no size penalty for points
2265
2266// apply the penalty
2267 for ( std::unique_ptr< LabelPosition > &pos : lPos )
2268 {
2269 pos->setCost( pos->cost() + sizeCost / 100 );
2270 }
2271}
2272
2274{
2275 if ( !nbPoints || !p2->nbPoints )
2276 return false;
2277
2278 // here we only care if the lines start or end at the other line -- we don't want to test
2279 // touches as that is true for "T" type joins!
2280 const double x1first = x.front();
2281 const double x1last = x.back();
2282 const double x2first = p2->x.front();
2283 const double x2last = p2->x.back();
2284 const double y1first = y.front();
2285 const double y1last = y.back();
2286 const double y2first = p2->y.front();
2287 const double y2last = p2->y.back();
2288
2289 const bool p2startTouches = ( qgsDoubleNear( x1first, x2first ) && qgsDoubleNear( y1first, y2first ) )
2290 || ( qgsDoubleNear( x1last, x2first ) && qgsDoubleNear( y1last, y2first ) );
2291
2292 const bool p2endTouches = ( qgsDoubleNear( x1first, x2last ) && qgsDoubleNear( y1first, y2last ) )
2293 || ( qgsDoubleNear( x1last, x2last ) && qgsDoubleNear( y1last, y2last ) );
2294 // only one endpoint can touch, not both
2295 if ( ( !p2startTouches && !p2endTouches ) || ( p2startTouches && p2endTouches ) )
2296 return false;
2297
2298 // now we know that we have one line endpoint touching only, but there's still a chance
2299 // that the other side of p2 may touch the original line NOT at the other endpoint
2300 // so we need to check that this point doesn't intersect
2301 const double p2otherX = p2startTouches ? x2last : x2first;
2302 const double p2otherY = p2startTouches ? y2last : y2first;
2303
2304 GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
2305
2306 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
2307 GEOSCoordSeq_setXY_r( geosctxt, coord, 0, p2otherX, p2otherY );
2308
2309 geos::unique_ptr p2OtherEnd( GEOSGeom_createPoint_r( geosctxt, coord ) );
2310 try
2311 {
2312 return ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), p2OtherEnd.get() ) != 1 );
2313 }
2314 catch ( GEOSException &e )
2315 {
2316 qWarning( "GEOS exception: %s", e.what() );
2317 QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2318 return false;
2319 }
2320}
2321
2323{
2324 if ( !mGeos )
2326 if ( !other->mGeos )
2327 other->createGeosGeom();
2328
2329 GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2330 try
2331 {
2332 GEOSGeometry *g1 = GEOSGeom_clone_r( ctxt, mGeos );
2333 GEOSGeometry *g2 = GEOSGeom_clone_r( ctxt, other->mGeos );
2334 GEOSGeometry *geoms[2] = { g1, g2 };
2335 geos::unique_ptr g( GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 ) );
2336 geos::unique_ptr gTmp( GEOSLineMerge_r( ctxt, g.get() ) );
2337
2338 if ( GEOSGeomTypeId_r( ctxt, gTmp.get() ) != GEOS_LINESTRING )
2339 {
2340 // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
2341 return false;
2342 }
2344
2345 // set up new geometry
2346 mGeos = gTmp.release();
2347 mOwnsGeom = true;
2348
2349 deleteCoords();
2350 qDeleteAll( mHoles );
2351 mHoles.clear();
2353 return true;
2354 }
2355 catch ( GEOSException &e )
2356 {
2357 qWarning( "GEOS exception: %s", e.what() );
2358 QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2359 return false;
2360 }
2361}
2362
2364{
2365 if ( mLF->alwaysShow() )
2366 {
2367 //if feature is set to always show, bump the priority up by orders of magnitude
2368 //so that other feature's labels are unlikely to be placed over the label for this feature
2369 //(negative numbers due to how pal::extract calculates inactive cost)
2370 return -0.2;
2371 }
2372
2373 return mLF->priority() >= 0 ? mLF->priority() : mLF->layer()->priority();
2374}
2375
2377{
2378 bool result = false;
2379
2380 switch ( mLF->layer()->upsidedownLabels() )
2381 {
2382 case Qgis::UpsideDownLabelHandling::FlipUpsideDownLabels:
2383 result = true;
2384 break;
2385 case Qgis::UpsideDownLabelHandling::AllowUpsideDownWhenRotationIsDefined:
2386 // upright only dynamic labels
2387 if ( !hasFixedRotation() || ( !hasFixedPosition() && fixedAngle() == 0.0 ) )
2388 {
2389 result = true;
2390 }
2391 break;
2392 case Qgis::UpsideDownLabelHandling::AlwaysAllowUpsideDown:
2393 break;
2394 }
2395 return result;
2396}
@ FromSymbolBounds
Offset distance applies from rendered symbol bounds.
@ OverPoint
Arranges candidates over a point (or centroid of a polygon), or at a preset offset from the point....
@ AroundPoint
Arranges candidates in a circle around a point (or centroid of a polygon). Applies to point or polygo...
@ Line
Arranges candidates parallel to a generalised line representing the feature or parallel to a polygon'...
@ Free
Arranges candidates scattered throughout a polygon feature. Candidates are rotated to respect the pol...
@ OrderedPositionsAroundPoint
Candidates are placed in predefined positions around a point. Preference is given to positions with g...
@ Horizontal
Arranges horizontal candidates scattered throughout a polygon feature. Applies to polygon layers only...
@ PerimeterCurved
Arranges candidates following the curvature of a polygon's boundary. Applies to polygon layers only.
@ OutsidePolygons
Candidates are placed outside of polygon boundaries. Applies to polygon layers only....
LabelPredefinedPointPosition
Positions for labels when using the Qgis::LabelPlacement::OrderedPositionsAroundPoint placement mode.
Definition: qgis.h:753
@ MiddleLeft
Label on left of point.
@ TopRight
Label on top-right of point.
@ MiddleRight
Label on right of point.
@ TopSlightlyRight
Label on top of point, slightly right of center.
@ TopMiddle
Label directly above point.
@ BottomSlightlyLeft
Label below point, slightly left of center.
@ BottomRight
Label on bottom right of point.
@ BottomLeft
Label on bottom-left of point.
@ BottomSlightlyRight
Label below point, slightly right of center.
@ TopLeft
Label on top-left of point.
@ BottomMiddle
Label directly below point.
@ TopSlightlyLeft
Label on top of point, slightly left of center.
const QgsCurve * exteriorRing() const SIP_HOLDGIL
Returns the curve polygon's exterior ring.
static double normalizedAngle(double angle) SIP_HOLDGIL
Ensures that an angle is in the range 0 <= angle < 2 pi.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
static std::unique_ptr< QgsAbstractGeometry > fromGeos(const GEOSGeometry *geos)
Create a geometry from a GEOSGeometry.
Definition: qgsgeos.cpp:1391
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:3450
The QgsLabelFeature class describes a feature that should be used within the labeling engine.
double overrunSmoothDistance() const
Returns the distance (in map units) with which the ends of linear features are averaged over when cal...
double fixedAngle() const
Angle in degrees of the fixed angle (relevant only if hasFixedAngle() returns true)
const QSizeF & symbolSize() const
Returns the size of the rendered symbol associated with this feature, if applicable.
QVector< Qgis::LabelPredefinedPointPosition > predefinedPositionOrder() const
Returns the priority ordered list of predefined positions for label candidates.
QgsLabeling::PolygonPlacementFlags polygonPlacementFlags() const
Returns the polygon placement flags, which dictate how polygon labels can be placed.
QgsPointXY positionOffset() const
Applies only to "offset from point" placement strategy.
bool hasFixedQuadrant() const
Returns whether the quadrant for the label is fixed.
bool hasFixedAngle() const
Whether the label should use a fixed angle instead of using angle from automatic placement.
pal::Layer * layer() const
Gets PAL layer of the label feature. Should be only used internally in PAL.
QgsLabeling::LinePlacementFlags arrangementFlags() const
Returns the feature's arrangement flags.
bool alwaysShow() const
Whether label should be always shown (sets very high label priority)
double lineAnchorPercent() const
Returns the percent along the line at which labels should be placed, for line labels only.
const GEOSPreparedGeometry * permissibleZonePrepared() const
Returns a GEOS prepared geometry representing the label's permissibleZone().
QgsLabelLineSettings::AnchorType lineAnchorType() const
Returns the line anchor type, which dictates how the lineAnchorPercent() setting is handled.
double distLabel() const
Applies to "around point" placement strategy or linestring features.
QPointF quadOffset() const
Applies to "offset from point" placement strategy and "around point" (in case hasFixedQuadrant() retu...
void setAnchorPosition(const QgsPointXY &anchorPosition)
In case of quadrand or aligned positioning, this is set to the anchor point.
QgsFeatureId id() const
Identifier of the label (unique within the parent label provider)
double overrunDistance() const
Returns the permissible distance (in map units) which labels are allowed to overrun the start or end ...
double priority() const
Returns the feature's labeling priority.
QgsGeometry permissibleZone() const
Returns the label's permissible zone geometry.
bool hasFixedPosition() const
Whether the label should use a fixed position instead of being automatically placed.
QgsLabelLineSettings::AnchorTextPoint lineAnchorTextPoint() const
Returns the line anchor text point, which dictates which part of the label text should be placed at t...
const QgsMargins & visualMargin() const
Returns the visual margin for the label feature.
Qgis::LabelOffsetType offsetType() const
Returns the offset type, which determines how offsets and distance to label behaves.
QgsPointXY fixedPosition() const
Coordinates of the fixed position (relevant only if hasFixedPosition() returns true)
@ Strict
Line anchor is a strict placement, and other placements are not permitted.
@ HintOnly
Line anchor is a hint for preferred placement only, but other placements close to the hint are permit...
AnchorTextPoint
Anchor point of label text.
@ EndOfText
Anchor using end of text.
@ StartOfText
Anchor using start of text.
@ CenterOfText
Anchor using center of text.
@ FollowPlacement
Automatically set the anchor point based on the lineAnchorPercent() value. Values <25% will use the s...
Contains constants and enums relating to labeling.
Definition: qgslabeling.h:32
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:45
double length() const override SIP_HOLDGIL
Returns the planar, 2-dimensional length of the geometry.
void visitPointsByRegularDistance(double distance, const std::function< bool(double x, double y, double z, double m, double startSegmentX, double startSegmentY, double startSegmentZ, double startSegmentM, double endSegmentX, double endSegmentY, double endSegmentZ, double endSegmentM) > &visitPoint) const
Visits regular points along the linestring, spaced by distance.
The QgsMargins class defines the four margins of a rectangle.
Definition: qgsmargins.h:38
double top() const
Returns the top margin.
Definition: qgsmargins.h:78
double right() const
Returns the right margin.
Definition: qgsmargins.h:84
double bottom() const
Returns the bottom margin.
Definition: qgsmargins.h:90
double left() const
Returns the left margin.
Definition: qgsmargins.h:72
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::MessageLevel::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
A class to represent a 2D point.
Definition: qgspointxy.h:59
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
Polygon geometry type.
Definition: qgspolygon.h:34
Contains precalculated properties regarding text metrics for text to be renderered at a later stage.
int count() const
Returns the total number of characters.
double characterWidth(int position) const
Returns the width of the character at the specified position.
double characterHeight(int position) const
Returns the character height of the character at the specified position (actually font metrics height...
double height() const SIP_HOLDGIL
Returns the height of the rectangle.
Definition: qgsrectangle.h:230
double width() const SIP_HOLDGIL
Returns the width of the rectangle.
Definition: qgsrectangle.h:223
LabelLineDirection
Controls behavior of curved text with respect to line directions.
@ FollowLineDirection
Curved text placement will respect the line direction and ignore painter orientation.
@ RespectPainterOrientation
Curved text will be placed respecting the painter orientation, and the actual line direction will be ...
static CurvePlacementProperties * generateCurvedTextPlacement(const QgsPrecalculatedTextMetrics &metrics, const double *x, const double *y, int numPoints, const std::vector< double > &pathDistances, double offsetAlongLine, LabelLineDirection direction=RespectPainterOrientation, double maxConcaveAngle=-1, double maxConvexAngle=-1, bool uprightOnly=true)
Calculates curved text placement properties.
Main class to handle feature.
Definition: feature.h:65
std::size_t createCandidatesAroundPoint(double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle)
Generate candidates for point feature, located around a specified point.
Definition: feature.cpp:577
std::size_t createCandidatesOutsidePolygon(std::vector< std::unique_ptr< LabelPosition > > &lPos, Pal *pal)
Generate candidates outside of polygon features.
Definition: feature.cpp:1924
bool hasFixedRotation() const
Returns true if the feature's label has a fixed rotation.
Definition: feature.h:283
double getLabelHeight(double angle=0.0) const
Returns the height of the label, optionally taking an angle into account.
Definition: feature.h:274
QList< FeaturePart * > mHoles
Definition: feature.h:350
double getLabelDistance() const
Returns the distance from the anchor point to the label.
Definition: feature.h:280
~FeaturePart() override
Deletes the feature.
Definition: feature.cpp:81
bool hasFixedPosition() const
Returns true if the feature's label has a fixed position.
Definition: feature.h:289
std::size_t createCandidatesForPolygon(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal)
Generate candidates for polygon features.
Definition: feature.cpp:1681
void setTotalRepeats(int repeats)
Returns the total number of repeating labels associated with this label.
Definition: feature.cpp:291
std::size_t maximumPolygonCandidates() const
Returns the maximum number of polygon candidates to generate for this feature.
Definition: feature.cpp:196
QgsFeatureId featureId() const
Returns the unique ID of the feature.
Definition: feature.cpp:164
std::size_t createCandidatesAlongLineNearStraightSegments(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal)
Generate candidates for line feature, by trying to place candidates towards the middle of the longest...
Definition: feature.cpp:853
bool hasSameLabelFeatureAs(FeaturePart *part) const
Tests whether this feature part belongs to the same QgsLabelFeature as another feature part.
Definition: feature.cpp:218
double fixedAngle() const
Returns the fixed angle for the feature's label.
Definition: feature.h:286
std::size_t maximumLineCandidates() const
Returns the maximum number of line candidates to generate for this feature.
Definition: feature.cpp:174
std::size_t createHorizontalCandidatesAlongLine(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal)
Generate horizontal candidates for line feature.
Definition: feature.cpp:764
std::size_t createCandidatesAlongLine(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal)
Generate candidates for line feature.
Definition: feature.cpp:735
bool mergeWithFeaturePart(FeaturePart *other)
Merge other (connected) part with this one and save the result in this part (other is unchanged).
Definition: feature.cpp:2322
std::size_t createCurvedCandidatesAlongLine(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal)
Generate curved candidates for line features.
Definition: feature.cpp:1349
bool onlyShowUprightLabels() const
Returns true if feature's label must be displayed upright.
Definition: feature.cpp:2376
std::size_t createCandidatesOverPoint(double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle)
Generate one candidate over or offset the specified point.
Definition: feature.cpp:325
std::unique_ptr< LabelPosition > createCandidatePointOnSurface(PointSet *mapShape)
Creates a single candidate using the "point on sruface" algorithm.
Definition: feature.cpp:404
QgsLabelFeature * mLF
Definition: feature.h:349
double getLabelWidth(double angle=0.0) const
Returns the width of the label, optionally taking an angle into account.
Definition: feature.h:268
QgsLabelFeature * feature()
Returns the parent feature.
Definition: feature.h:94
std::unique_ptr< LabelPosition > curvedPlacementAtOffset(PointSet *mapShape, const std::vector< double > &pathDistances, QgsTextRendererUtils::LabelLineDirection direction, double distance, bool &labeledLineSegmentIsRightToLeft, bool applyAngleConstraints, bool uprightOnly)
Returns the label position for a curved label at a specific offset along a path.
Definition: feature.cpp:1312
std::vector< std::unique_ptr< LabelPosition > > createCandidates(Pal *pal)
Generates a list of candidate positions for labels for this feature.
Definition: feature.cpp:2127
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:2273
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:159
PathOffset
Path offset variances used in curved placement.
Definition: feature.h:71
int totalRepeats() const
Returns the total number of repeating labels associated with this label.
Definition: feature.cpp:286
std::size_t createCandidatesAlongLineNearMidpoint(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost=0.0, Pal *pal=nullptr)
Generate candidates for line feature, by trying to place candidates as close as possible to the line'...
Definition: feature.cpp:1106
void addSizePenalty(std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4]) const
Increases the cost of the label candidates for this feature, based on the size of the feature.
Definition: feature.cpp:2232
void extractCoords(const GEOSGeometry *geom)
read coordinates from a GEOS geom
Definition: feature.cpp:89
double calculatePriority() const
Calculates the priority for the feature.
Definition: feature.cpp:2363
std::size_t createCandidatesAtOrderedPositionsOverPoint(double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle)
Generates candidates following a prioritized list of predefined positions around a point.
Definition: feature.cpp:538
std::size_t createCandidateCenteredOverPoint(double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle)
Generate one candidate centered over the specified point.
Definition: feature.cpp:296
std::size_t maximumPointCandidates() const
Returns the maximum number of point candidates to generate for this feature.
Definition: feature.cpp:169
static bool reorderPolygon(std::vector< double > &x, std::vector< double > &y)
Reorder points to have cross prod ((x,y)[i], (x,y)[i+1), point) > 0 when point is outside.
static double dist_euc2d(double x1, double y1, double x2, double y2)
Definition: geomfunction.h:67
static bool containsCandidate(const GEOSPreparedGeometry *geom, double x, double y, double width, double height, double alpha)
Returns true if a GEOS prepared geometry totally contains a label candidate.
LabelPosition is a candidate feature label position.
Definition: labelposition.h:56
double getAlpha() const
Returns the angle to rotate text (in rad).
Quadrant
Position of label candidate relative to feature.
Definition: labelposition.h:66
double getHeight() const
void setNextPart(std::unique_ptr< LabelPosition > next)
Sets the next part of this label position (i.e.
double getWidth() const
double getX(int i=0) const
Returns the down-left x coordinate.
double getY(int i=0) const
Returns the down-left y coordinate.
LabelPosition * nextPart() const
Returns the next part of this label position (i.e.
A set of features which influence the labeling process.
Definition: layer.h:63
QString name() const
Returns the layer's name.
Definition: layer.h:162
std::size_t maximumPolygonLabelCandidates() const
Returns the maximum number of polygon label candidates to generate for features in this layer.
Definition: layer.h:139
Pal * mPal
Definition: layer.h:323
int connectedFeatureId(QgsFeatureId featureId) const
Returns the connected feature ID for a label feature ID, which is unique for all features which have ...
Definition: layer.cpp:360
Qgis::LabelPlacement arrangement() const
Returns the layer's arrangement policy.
Definition: layer.h:168
std::size_t maximumPointLabelCandidates() const
Returns the maximum number of point label candidates to generate for features in this layer.
Definition: layer.h:97
Qgis::UpsideDownLabelHandling upsidedownLabels() const
Returns how upside down labels are handled within the layer.
Definition: layer.h:269
bool centroidInside() const
Returns whether labels placed at the centroid of features within the layer are forced to be placed in...
Definition: layer.h:285
bool isCurved() const
Returns true if the layer has curved labels.
Definition: layer.h:173
double priority() const
Returns the layer's priority, between 0 and 1.
Definition: layer.h:243
std::size_t maximumLineLabelCandidates() const
Returns the maximum number of line label candidates to generate for features in this layer.
Definition: layer.h:118
Main Pal labeling class.
Definition: pal.h:83
double maximumLineCandidatesPerMapUnit() const
Returns the maximum number of line label candidate positions per map unit.
Definition: pal.h:178
double maximumPolygonCandidatesPerMapUnitSquared() const
Returns the maximum number of polygon label candidate positions per map unit squared.
Definition: pal.h:192
The underlying raw pal geometry class.
Definition: pointset.h:77
geos::unique_ptr interpolatePoint(double distance) const
Returns a GEOS geometry representing the point interpolated on the shape by distance.
Definition: pointset.cpp:1014
std::unique_ptr< PointSet > clone() const
Returns a copy of the point set.
Definition: pointset.cpp:265
double lineLocatePoint(const GEOSGeometry *point) const
Returns the distance along the geometry closest to the specified GEOS point.
Definition: pointset.cpp:1032
OrientedConvexHullBoundingBox computeConvexHullOrientedBoundingBox(bool &ok)
Computes an oriented bounding box for the shape's convex hull.
Definition: pointset.cpp:718
double length() const
Returns length of line geometry.
Definition: pointset.cpp:1060
void deleteCoords()
Definition: pointset.cpp:232
double ymax
Definition: pointset.h:261
double ymin
Definition: pointset.h:260
double area() const
Returns area of polygon geometry.
Definition: pointset.cpp:1086
bool isClosed() const
Returns true if pointset is closed.
Definition: pointset.cpp:1113
PointSet * holeOf
Definition: pointset.h:241
void createGeosGeom() const
Definition: pointset.cpp:99
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py) const
Gets a point a set distance along a line geometry.
Definition: pointset.cpp:975
std::vector< double > y
Definition: pointset.h:231
void getCentroid(double &px, double &py, bool forceInside=false) const
Definition: pointset.cpp:917
std::vector< double > x
Definition: pointset.h:230
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:154
GEOSGeometry * mGeos
Definition: pointset.h:234
double xmin
Definition: pointset.h:258
const GEOSGeometry * geos() const
Returns the point set's GEOS geometry.
Definition: pointset.cpp:1052
void invalidateGeos() const
Definition: pointset.cpp:166
friend class FeaturePart
Definition: pointset.h:78
double xmax
Definition: pointset.h:259
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
Definition: pointset.cpp:270
std::tuple< std::vector< double >, double > edgeDistances() const
Returns a vector of edge distances as well as its total length.
Definition: pointset.cpp:1147
PointSet * parent
Definition: pointset.h:242
bool mOwnsGeom
Definition: pointset.h:235
static QLinkedList< PointSet * > splitPolygons(PointSet *inputShape, double labelWidth, double labelHeight)
Split a polygon using some random logic into some other polygons.
Definition: pointset.cpp:294
void createCandidateAtOrderedPositionOverPoint(double &labelX, double &labelY, LabelPosition::Quadrant &quadrant, double x, double y, double labelWidth, double labelHeight, Qgis::LabelPredefinedPointPosition position, double distanceToLabel, const QgsMargins &visualMargin, double symbolWidthOffset, double symbolHeightOffset, double angle)
Definition: feature.cpp:431
double ANALYSIS_EXPORT angle(QgsPoint *p1, QgsPoint *p2, QgsPoint *p3, QgsPoint *p4)
Calculates the angle between two segments (in 2 dimension, z-values are ignored)
Definition: MathUtils.cpp:786
std::unique_ptr< const GEOSPreparedGeometry, GeosDeleter > prepared_unique_ptr
Scoped GEOS prepared geometry pointer.
Definition: qgsgeos.h:79
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:74
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:3509
qint64 QgsFeatureId
64 bit feature ids negative numbers are used for uncommitted/newly added features
Definition: qgsfeatureid.h:28
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
Represents the minimum area, oriented bounding box surrounding a convex hull.
Definition: pointset.h:60