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