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