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