QGIS API Documentation  3.22.4-Białowieża (ce8e65e95e)
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  if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1341  mapShapeOffsetPositive = mapShape->clone();
1342  if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1343  mapShapeOffsetNegative = mapShape->clone();
1344  if ( offsetDistance >= 0.0 || !( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) )
1345  {
1346  if ( mapShapeOffsetPositive )
1347  mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance );
1348  if ( mapShapeOffsetNegative )
1349  mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance * -1 );
1350  }
1351  else
1352  {
1353  // In case of a negative offset distance, above line placement switch to below line and vice versa
1354  if ( flags & QgsLabeling::LinePlacementFlag::AboveLine
1355  && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1356  {
1357  flags &= ~QgsLabeling::LinePlacementFlag::AboveLine;
1358  flags |= QgsLabeling::LinePlacementFlag::BelowLine;
1359  }
1360  else if ( flags & QgsLabeling::LinePlacementFlag::BelowLine
1361  && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1362  {
1363  flags &= ~QgsLabeling::LinePlacementFlag::BelowLine;
1364  flags |= QgsLabeling::LinePlacementFlag::AboveLine;
1365  }
1366  if ( mapShapeOffsetPositive )
1367  mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance * -1 );
1368  if ( mapShapeOffsetNegative )
1369  mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance );
1370  }
1371  }
1372 
1373  std::vector< std::unique_ptr< LabelPosition >> positions;
1374  for ( PathOffset offset : { PositiveOffset, NoOffset, NegativeOffset } )
1375  {
1376  PointSet *currentMapShape = nullptr;
1377  if ( offset == PositiveOffset && hasAboveBelowLinePlacement )
1378  {
1379  currentMapShape = mapShapeOffsetPositive.get();
1380  }
1381  if ( offset == NoOffset && flags & QgsLabeling::LinePlacementFlag::OnLine )
1382  {
1383  currentMapShape = mapShape;
1384  }
1385  if ( offset == NegativeOffset && hasAboveBelowLinePlacement )
1386  {
1387  currentMapShape = mapShapeOffsetNegative.get();
1388  }
1389  if ( !currentMapShape )
1390  continue;
1391 
1392  // distance calculation
1393  const auto [ pathDistances, totalDistance ] = currentMapShape->edgeDistances();
1394  if ( qgsDoubleNear( totalDistance, 0.0 ) )
1395  continue;
1396 
1397  const double lineAnchorPoint = totalDistance * mLF->lineAnchorPercent();
1398 
1399  if ( pal->isCanceled() )
1400  return 0;
1401 
1402  const std::size_t candidateTargetCount = maximumLineCandidates();
1403  double delta = std::max( li->characterHeight() / 6, totalDistance / candidateTargetCount );
1404 
1405  // generate curved labels
1406  double distanceAlongLineToStartCandidate = 0;
1407  bool singleCandidateOnly = false;
1408  switch ( mLF->lineAnchorType() )
1409  {
1411  break;
1412 
1414  distanceAlongLineToStartCandidate = std::min( lineAnchorPoint, totalDistance * 0.99 - getLabelWidth() );
1415  singleCandidateOnly = true;
1416  break;
1417  }
1418 
1419  for ( ; distanceAlongLineToStartCandidate <= totalDistance; distanceAlongLineToStartCandidate += delta )
1420  {
1421  if ( pal->isCanceled() )
1422  return 0;
1423 
1424  // placements may need to be reversed if using map orientation and the line has right-to-left direction
1425  bool labeledLineSegmentIsRightToLeft = false;
1426  const QgsTextRendererUtils::LabelLineDirection direction = ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? QgsTextRendererUtils::RespectPainterOrientation : QgsTextRendererUtils::FollowLineDirection;
1427  std::unique_ptr< LabelPosition > labelPosition = curvedPlacementAtOffset( currentMapShape, pathDistances, direction, distanceAlongLineToStartCandidate, labeledLineSegmentIsRightToLeft, !singleCandidateOnly );
1428 
1429  if ( !labelPosition )
1430  continue;
1431  if ( flags & QgsLabeling::LinePlacementFlag::MapOrientation )
1432  {
1433  if ( ( offset != NoOffset ) && !labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1434  continue;
1435  if ( ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1436  continue;
1437  }
1438 
1439  // evaluate cost
1440  const double angleDiff = labelPosition->angleDifferential();
1441  const double angleDiffAvg = characterCount > 1 ? ( angleDiff / ( characterCount - 1 ) ) : 0; // <0, pi> but pi/8 is much already
1442 
1443  // if anchor placement is towards start or end of line, we need to slightly tweak the costs to ensure that the
1444  // anchor weighting is sufficient to push labels towards start/end
1445  const bool anchorIsFlexiblePlacement = !singleCandidateOnly && mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1446  double cost = angleDiffAvg / 100; // <0, 0.031 > but usually <0, 0.003 >
1447  if ( cost < 0.0001 )
1448  cost = 0.0001;
1449 
1450  // penalize positions which are further from the line's anchor point
1451  double labelCenter = distanceAlongLineToStartCandidate + getLabelWidth() / 2;
1452  double costCenter = std::fabs( lineAnchorPoint - labelCenter ) / totalDistance; // <0, 0.5>
1453  cost += costCenter / ( anchorIsFlexiblePlacement ? 100 : 10 ); // < 0, 0.005 >, or <0, 0.05> if preferring placement close to start/end of line
1454 
1455  const bool isBelow = ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft;
1456  if ( isBelow )
1457  {
1458  // add additional cost for on line placement
1459  cost += 0.001;
1460  }
1461  else if ( offset == NoOffset )
1462  {
1463  // add additional cost for below line placement
1464  cost += 0.002;
1465  }
1466 
1467  labelPosition->setCost( cost );
1468 
1469  std::unique_ptr< LabelPosition > p = std::make_unique< LabelPosition >( *labelPosition );
1470  if ( p && mLF->permissibleZonePrepared() )
1471  {
1472  bool within = true;
1473  LabelPosition *currentPos = p.get();
1474  while ( within && currentPos )
1475  {
1476  within = GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), currentPos->getX(), currentPos->getY(), currentPos->getWidth(), currentPos->getHeight(), currentPos->getAlpha() );
1477  currentPos = currentPos->nextPart();
1478  }
1479  if ( !within )
1480  {
1481  p.reset();
1482  }
1483  }
1484 
1485  if ( p )
1486  positions.emplace_back( std::move( p ) );
1487 
1488  if ( singleCandidateOnly )
1489  break;
1490  }
1491  }
1492 
1493  for ( std::unique_ptr< LabelPosition > &pos : positions )
1494  {
1495  lPos.emplace_back( std::move( pos ) );
1496  }
1497 
1498  return positions.size();
1499 }
1500 
1501 /*
1502  * seg 2
1503  * pt3 ____________pt2
1504  * ¦ ¦
1505  * ¦ ¦
1506  * seg 3 ¦ BBOX ¦ seg 1
1507  * ¦ ¦
1508  * ¦____________¦
1509  * pt0 seg 0 pt1
1510  *
1511  */
1512 
1513 std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
1514 {
1515  double labelWidth = getLabelWidth();
1516  double labelHeight = getLabelHeight();
1517 
1518  const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1519  const std::size_t targetPolygonCandidates = maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * area() ) ) )
1520  : 0;
1521 
1522  const double totalArea = area();
1523 
1524  mapShape->parent = nullptr;
1525 
1526  if ( pal->isCanceled() )
1527  return 0;
1528 
1529  QLinkedList<PointSet *> shapes_final = splitPolygons( mapShape, labelWidth, labelHeight );
1530 #if 0
1531  QgsDebugMsg( QStringLiteral( "PAL split polygons resulted in:" ) );
1532  for ( PointSet *ps : shapes_final )
1533  {
1534  QgsDebugMsg( ps->toWkt() );
1535  }
1536 #endif
1537 
1538  std::size_t nbp = 0;
1539 
1540  if ( !shapes_final.isEmpty() )
1541  {
1542  int id = 0; // ids for candidates
1543  double dlx, dly; // delta from label center and bottom-left corner
1544  double alpha = 0.0; // rotation for the label
1545  double px, py;
1546 
1547  double beta;
1548  double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
1549  double rx, ry;
1550  std::vector< OrientedConvexHullBoundingBox > boxes;
1551  boxes.reserve( shapes_final.size() );
1552 
1553  // Compute bounding box for each finalShape
1554  while ( !shapes_final.isEmpty() )
1555  {
1556  PointSet *shape = shapes_final.takeFirst();
1557  bool ok = false;
1559  if ( ok )
1560  boxes.emplace_back( box );
1561 
1562  if ( shape->parent )
1563  delete shape;
1564  }
1565 
1566  if ( pal->isCanceled() )
1567  return 0;
1568 
1569  double densityX = 1.0 / std::sqrt( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() );
1570  double densityY = densityX;
1571  int numTry = 0;
1572 
1573  //fit in polygon only mode slows down calculation a lot, so if it's enabled
1574  //then use a smaller limit for number of iterations
1575  int maxTry = mLF->permissibleZonePrepared() ? 7 : 10;
1576 
1577  std::size_t numberCandidatesGenerated = 0;
1578 
1579  do
1580  {
1581  for ( OrientedConvexHullBoundingBox &box : boxes )
1582  {
1583  // there is two possibilities here:
1584  // 1. no maximum candidates for polygon setting is in effect (i.e. maxPolygonCandidates == 0). In that case,
1585  // we base our dx/dy on the current maximumPolygonCandidatesPerMapUnitSquared value. That should give us the desired
1586  // density of candidates straight up. Easy!
1587  // 2. a maximum candidate setting IS in effect. In that case, we want to generate a good initial estimate for dx/dy
1588  // which gives us a good spatial coverage of the polygon while roughly matching the desired maximum number of candidates.
1589  // If dx/dy is too small, then too many candidates will be generated, which is both slow AND results in poor coverage of the
1590  // polygon (after culling candidates to the max number, only those clustered around the polygon's pole of inaccessibility
1591  // will remain).
1592  double dx = densityX;
1593  double dy = densityY;
1594  if ( numTry == 0 && maxPolygonCandidates > 0 )
1595  {
1596  // scale maxPolygonCandidates for just this convex hull
1597  const double boxArea = box.width * box.length;
1598  double maxThisBox = targetPolygonCandidates * boxArea / totalArea;
1599  dx = std::max( dx, std::sqrt( boxArea / maxThisBox ) * 0.8 );
1600  dy = dx;
1601  }
1602 
1603  if ( pal->isCanceled() )
1604  return numberCandidatesGenerated;
1605 
1606  if ( ( box.length * box.width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
1607  {
1608  // Very Large BBOX (should never occur)
1609  continue;
1610  }
1611 
1613  {
1614  //check width/height of bbox is sufficient for label
1615  if ( mLF->permissibleZone().boundingBox().width() < labelWidth ||
1616  mLF->permissibleZone().boundingBox().height() < labelHeight )
1617  {
1618  //no way label can fit in this box, skip it
1619  continue;
1620  }
1621  }
1622 
1623  bool enoughPlace = false;
1625  {
1626  enoughPlace = true;
1627  px = ( box.x[0] + box.x[2] ) / 2 - labelWidth;
1628  py = ( box.y[0] + box.y[2] ) / 2 - labelHeight;
1629  int i, j;
1630 
1631  // Virtual label: center on bbox center, label size = 2x original size
1632  // alpha = 0.
1633  // If all corner are in bbox then place candidates horizontaly
1634  for ( rx = px, i = 0; i < 2; rx = rx + 2 * labelWidth, i++ )
1635  {
1636  for ( ry = py, j = 0; j < 2; ry = ry + 2 * labelHeight, j++ )
1637  {
1638  if ( !mapShape->containsPoint( rx, ry ) )
1639  {
1640  enoughPlace = false;
1641  break;
1642  }
1643  }
1644  if ( !enoughPlace )
1645  {
1646  break;
1647  }
1648  }
1649 
1650  } // arrangement== FREE ?
1651 
1652  if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal || enoughPlace )
1653  {
1654  alpha = 0.0; // HORIZ
1655  }
1656  else if ( box.length > 1.5 * labelWidth && box.width > 1.5 * labelWidth )
1657  {
1658  if ( box.alpha <= M_PI_4 )
1659  {
1660  alpha = box.alpha;
1661  }
1662  else
1663  {
1664  alpha = box.alpha - M_PI_2;
1665  }
1666  }
1667  else if ( box.length > box.width )
1668  {
1669  alpha = box.alpha - M_PI_2;
1670  }
1671  else
1672  {
1673  alpha = box.alpha;
1674  }
1675 
1676  beta = std::atan2( labelHeight, labelWidth ) + alpha;
1677 
1678 
1679  //alpha = box->alpha;
1680 
1681  // delta from label center and down-left corner
1682  dlx = std::cos( beta ) * diago;
1683  dly = std::sin( beta ) * diago;
1684 
1685  double px0 = box.width / 2.0;
1686  double py0 = box.length / 2.0;
1687 
1688  px0 -= std::ceil( px0 / dx ) * dx;
1689  py0 -= std::ceil( py0 / dy ) * dy;
1690 
1691  for ( px = px0; px <= box.width; px += dx )
1692  {
1693  if ( pal->isCanceled() )
1694  break;
1695 
1696  for ( py = py0; py <= box.length; py += dy )
1697  {
1698 
1699  rx = std::cos( box.alpha ) * px + std::cos( box.alpha - M_PI_2 ) * py;
1700  ry = std::sin( box.alpha ) * px + std::sin( box.alpha - M_PI_2 ) * py;
1701 
1702  rx += box.x[0];
1703  ry += box.y[0];
1704 
1705  if ( mLF->permissibleZonePrepared() )
1706  {
1707  if ( GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), rx - dlx, ry - dly, labelWidth, labelHeight, alpha ) )
1708  {
1709  // cost is set to minimal value, evaluated later
1710  lPos.emplace_back( std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver ) );
1711  numberCandidatesGenerated++;
1712  }
1713  }
1714  else
1715  {
1716  // TODO - this should be an intersection test, not just a contains test of the candidate centroid
1717  // because in some cases we would want to allow candidates which mostly overlap the polygon even though
1718  // their centroid doesn't overlap (e.g. a "U" shaped polygon)
1719  // but the bugs noted in CostCalculator currently prevent this
1720  if ( mapShape->containsPoint( rx, ry ) )
1721  {
1722  std::unique_ptr< LabelPosition > potentialCandidate = std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver );
1723  // cost is set to minimal value, evaluated later
1724  lPos.emplace_back( std::move( potentialCandidate ) );
1725  numberCandidatesGenerated++;
1726  }
1727  }
1728  }
1729  }
1730  } // forall box
1731 
1732  nbp = numberCandidatesGenerated;
1733  if ( maxPolygonCandidates > 0 && nbp < targetPolygonCandidates )
1734  {
1735  densityX /= 2;
1736  densityY /= 2;
1737  numTry++;
1738  }
1739  else
1740  {
1741  break;
1742  }
1743  }
1744  while ( numTry < maxTry );
1745 
1746  nbp = numberCandidatesGenerated;
1747  }
1748  else
1749  {
1750  nbp = 0;
1751  }
1752 
1753  return nbp;
1754 }
1755 
1756 std::size_t FeaturePart::createCandidatesOutsidePolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, Pal *pal )
1757 {
1758  // calculate distance between horizontal lines
1759  const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1760  std::size_t candidatesCreated = 0;
1761 
1762  double labelWidth = getLabelWidth();
1763  double labelHeight = getLabelHeight();
1764  double distanceToLabel = getLabelDistance();
1765  const QgsMargins &visualMargin = mLF->visualMargin();
1766 
1767  /*
1768  * From Rylov & Reimer (2016) "A practical algorithm for the external annotation of area features":
1769  *
1770  * The list of rules adapted to the
1771  * needs of externally labelling areal features is as follows:
1772  * R1. Labels should be placed horizontally.
1773  * R2. Label should be placed entirely outside at some
1774  * distance from the area feature.
1775  * R3. Name should not cross the boundary of its area
1776  * feature.
1777  * R4. The name should be placed in way that takes into
1778  * account the shape of the feature by achieving a
1779  * balance between the feature and its name, emphasizing their relationship.
1780  * R5. The lettering to the right and slightly above the
1781  * symbol is prioritized.
1782  *
1783  * In the following subsections we utilize four of the five rules
1784  * for two subtasks of label placement, namely, for candidate
1785  * positions generation (R1, R2, and R3) and for measuring their
1786  * ‘goodness’ (R4). The rule R5 is applicable only in the case when
1787  * the area of a polygonal feature is small and the feature can be
1788  * treated and labelled as a point-feature
1789  */
1790 
1791  /*
1792  * QGIS approach (cite Dawson (2020) if you want ;) )
1793  *
1794  * We differ from the horizontal sweep line approach described by Rylov & Reimer and instead
1795  * rely on just generating a set of points at regular intervals along the boundary of the polygon (exterior ring).
1796  *
1797  * In practice, this generates similar results as Rylov & Reimer, but has the additional benefits that:
1798  * 1. It avoids the need to calculate intersections between the sweep line and the polygon
1799  * 2. For horizontal or near horizontal segments, Rylov & Reimer propose generating evenly spaced points along
1800  * these segments-- i.e. the same approach as we do for the whole polygon
1801  * 3. It's easier to determine in advance exactly how many candidate positions we'll be generating, and accordingly
1802  * we can easily pick the distance between points along the exterior ring so that the number of positions generated
1803  * matches our target number (targetPolygonCandidates)
1804  */
1805 
1806  // TO consider -- for very small polygons (wrt label size), treat them just like a point feature?
1807 
1808  double cx, cy;
1809  getCentroid( cx, cy, false );
1810 
1811  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1812 
1813  // be a bit sneaky and only buffer out 50% here, and then do the remaining 50% when we make the label candidate itself.
1814  // this avoids candidates being created immediately over the buffered ring and always intersecting with it...
1815  geos::unique_ptr buffer( GEOSBuffer_r( ctxt, geos(), distanceToLabel * 0.5, 1 ) );
1816  std::unique_ptr< QgsAbstractGeometry> gg( QgsGeos::fromGeos( buffer.get() ) );
1817 
1818  geos::prepared_unique_ptr preparedBuffer( GEOSPrepare_r( ctxt, buffer.get() ) );
1819 
1820  const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( gg.get() );
1821  if ( !poly )
1822  return candidatesCreated;
1823 
1824  const QgsLineString *ring = qgsgeometry_cast< const QgsLineString *>( poly->exteriorRing() );
1825  if ( !ring )
1826  return candidatesCreated;
1827 
1828  // 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,
1829  // i.e a loooooong skinny polygon with small area should still generate a large number of candidates)
1830  const double ringLength = ring->length();
1831  const double circleArea = std::pow( ringLength, 2 ) / ( 4 * M_PI );
1832  const std::size_t candidatesForArea = static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * circleArea ) );
1833  const std::size_t targetPolygonCandidates = std::max( static_cast< std::size_t >( 16 ), maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, candidatesForArea ) : candidatesForArea );
1834 
1835  // assume each position generates one candidate
1836  const double delta = ringLength / targetPolygonCandidates;
1837  geos::unique_ptr geosPoint;
1838 
1839  const double maxDistCentroidToLabelX = std::max( xmax - cx, cx - xmin ) + distanceToLabel;
1840  const double maxDistCentroidToLabelY = std::max( ymax - cy, cy - ymin ) + distanceToLabel;
1841  const double estimateOfMaxPossibleDistanceCentroidToLabel = std::sqrt( maxDistCentroidToLabelX * maxDistCentroidToLabelX + maxDistCentroidToLabelY * maxDistCentroidToLabelY );
1842 
1843  // Satisfy R1: Labels should be placed horizontally.
1844  const double labelAngle = 0;
1845 
1846  std::size_t i = lPos.size();
1847  auto addCandidate = [&]( double x, double y, QgsPalLayerSettings::PredefinedPointPosition position )
1848  {
1849  double labelX = 0;
1850  double labelY = 0;
1852 
1853  // Satisfy R2: Label should be placed entirely outside at some distance from the area feature.
1854  createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel * 0.5, visualMargin, 0, 0, labelAngle );
1855 
1856  std::unique_ptr< LabelPosition > candidate = std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, labelAngle, 0, this, false, quadrant );
1857  if ( candidate->intersects( preparedBuffer.get() ) )
1858  {
1859  // satisfy R3. Name should not cross the boundary of its area feature.
1860 
1861  // actually, we use the buffered geometry here, because a label shouldn't be closer to the polygon then the minimum distance value
1862  return;
1863  }
1864 
1865  // cost candidates by their distance to the feature's centroid (following Rylov & Reimer)
1866 
1867  // Satisfy R4. The name should be placed in way that takes into
1868  // account the shape of the feature by achieving a
1869  // balance between the feature and its name, emphasizing their relationship.
1870 
1871 
1872  // here we deviate a little from R&R, and instead of just calculating the centroid distance
1873  // to centroid of label, we calculate the distance from the centroid to the nearest point on the label
1874 
1875  const double centroidDistance = candidate->getDistanceToPoint( cx, cy );
1876  const double centroidCost = centroidDistance / estimateOfMaxPossibleDistanceCentroidToLabel;
1877  candidate->setCost( centroidCost );
1878 
1879  lPos.emplace_back( std::move( candidate ) );
1880  candidatesCreated++;
1881  ++i;
1882  };
1883 
1884  ring->visitPointsByRegularDistance( delta, [&]( double x, double y, double, double,
1885  double startSegmentX, double startSegmentY, double, double,
1886  double endSegmentX, double endSegmentY, double, double )
1887  {
1888  // get normal angle for segment
1889  float angle = atan2( static_cast< float >( endSegmentY - startSegmentY ), static_cast< float >( endSegmentX - startSegmentX ) ) * 180 / M_PI;
1890  if ( angle < 0 )
1891  angle += 360;
1892 
1893  // adapted fom Rylov & Reimer figure 9
1894  if ( angle >= 0 && angle <= 5 )
1895  {
1896  addCandidate( x, y, QgsPalLayerSettings::TopMiddle );
1897  addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1898  }
1899  else if ( angle <= 85 )
1900  {
1901  addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1902  }
1903  else if ( angle <= 90 )
1904  {
1905  addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1906  addCandidate( x, y, QgsPalLayerSettings::MiddleLeft );
1907  }
1908 
1909  else if ( angle <= 95 )
1910  {
1911  addCandidate( x, y, QgsPalLayerSettings::MiddleLeft );
1912  addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1913  }
1914  else if ( angle <= 175 )
1915  {
1916  addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1917  }
1918  else if ( angle <= 180 )
1919  {
1920  addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1921  addCandidate( x, y, QgsPalLayerSettings::BottomMiddle );
1922  }
1923 
1924  else if ( angle <= 185 )
1925  {
1926  addCandidate( x, y, QgsPalLayerSettings::BottomMiddle );
1927  addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1928  }
1929  else if ( angle <= 265 )
1930  {
1931  addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1932  }
1933  else if ( angle <= 270 )
1934  {
1935  addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1936  addCandidate( x, y, QgsPalLayerSettings::MiddleRight );
1937  }
1938  else if ( angle <= 275 )
1939  {
1940  addCandidate( x, y, QgsPalLayerSettings::MiddleRight );
1941  addCandidate( x, y, QgsPalLayerSettings::TopRight );
1942  }
1943  else if ( angle <= 355 )
1944  {
1945  addCandidate( x, y, QgsPalLayerSettings::TopRight );
1946  }
1947  else
1948  {
1949  addCandidate( x, y, QgsPalLayerSettings::TopRight );
1950  addCandidate( x, y, QgsPalLayerSettings::TopMiddle );
1951  }
1952 
1953  return !pal->isCanceled();
1954  } );
1955 
1956  return candidatesCreated;
1957 }
1958 
1959 std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates( Pal *pal )
1960 {
1961  std::vector< std::unique_ptr< LabelPosition > > lPos;
1962  double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
1963 
1964  if ( mLF->hasFixedPosition() )
1965  {
1966  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 ) );
1967  }
1968  else
1969  {
1970  switch ( type )
1971  {
1972  case GEOS_POINT:
1976  createCandidatesOverPoint( x[0], y[0], lPos, angle );
1977  else
1978  createCandidatesAroundPoint( x[0], y[0], lPos, angle );
1979  break;
1980 
1981  case GEOS_LINESTRING:
1984  else if ( mLF->layer()->isCurved() )
1985  createCurvedCandidatesAlongLine( lPos, this, true, pal );
1986  else
1987  createCandidatesAlongLine( lPos, this, true, pal );
1988  break;
1989 
1990  case GEOS_POLYGON:
1991  {
1992  const double labelWidth = getLabelWidth();
1993  const double labelHeight = getLabelHeight();
1994 
1995  const bool allowOutside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementOutsideOfPolygon;
1996  const bool allowInside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementInsideOfPolygon;
1997  //check width/height of bbox is sufficient for label
1998 
1999  if ( ( allowOutside && !allowInside ) || ( mLF->layer()->arrangement() == QgsPalLayerSettings::OutsidePolygons ) )
2000  {
2001  // only allowed to place outside of polygon
2003  }
2004  else if ( allowOutside && ( std::fabs( xmax - xmin ) < labelWidth ||
2005  std::fabs( ymax - ymin ) < labelHeight ) )
2006  {
2007  //no way label can fit in this polygon -- shortcut and only place label outside
2009  }
2010  else
2011  {
2012  std::size_t created = 0;
2013  if ( allowInside )
2014  {
2015  switch ( mLF->layer()->arrangement() )
2016  {
2018  {
2019  double cx, cy;
2020  getCentroid( cx, cy, mLF->layer()->centroidInside() );
2021  if ( qgsDoubleNear( mLF->distLabel(), 0.0 ) )
2022  created += createCandidateCenteredOverPoint( cx, cy, lPos, angle );
2023  created += createCandidatesAroundPoint( cx, cy, lPos, angle );
2024  break;
2025  }
2027  {
2028  double cx, cy;
2029  getCentroid( cx, cy, mLF->layer()->centroidInside() );
2030  created += createCandidatesOverPoint( cx, cy, lPos, angle );
2031  break;
2032  }
2034  created += createCandidatesAlongLine( lPos, this, false, pal );
2035  break;
2037  created += createCurvedCandidatesAlongLine( lPos, this, false, pal );
2038  break;
2039  default:
2040  created += createCandidatesForPolygon( lPos, this, pal );
2041  break;
2042  }
2043  }
2044 
2045  if ( allowOutside )
2046  {
2047  // add fallback for labels outside the polygon
2049 
2050  if ( created > 0 )
2051  {
2052  // TODO (maybe) increase cost for outside placements (i.e. positions at indices >= created)?
2053  // From my initial testing this doesn't seem necessary
2054  }
2055  }
2056  }
2057  }
2058  }
2059  }
2060 
2061  return lPos;
2062 }
2063 
2064 void FeaturePart::addSizePenalty( std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4] )
2065 {
2066  if ( !mGeos )
2067  createGeosGeom();
2068 
2069  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2070  int geomType = GEOSGeomTypeId_r( ctxt, mGeos );
2071 
2072  double sizeCost = 0;
2073  if ( geomType == GEOS_LINESTRING )
2074  {
2075  const double l = length();
2076  if ( l <= 0 )
2077  return; // failed to calculate length
2078  double bbox_length = std::max( bbx[2] - bbx[0], bby[2] - bby[0] );
2079  if ( l >= bbox_length / 4 )
2080  return; // the line is longer than quarter of height or width - don't penalize it
2081 
2082  sizeCost = 1 - ( l / ( bbox_length / 4 ) ); // < 0,1 >
2083  }
2084  else if ( geomType == GEOS_POLYGON )
2085  {
2086  const double a = area();
2087  if ( a <= 0 )
2088  return;
2089  double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
2090  if ( a >= bbox_area / 16 )
2091  return; // covers more than 1/16 of our view - don't penalize it
2092 
2093  sizeCost = 1 - ( a / ( bbox_area / 16 ) ); // < 0, 1 >
2094  }
2095  else
2096  return; // no size penalty for points
2097 
2098 // apply the penalty
2099  for ( std::unique_ptr< LabelPosition > &pos : lPos )
2100  {
2101  pos->setCost( pos->cost() + sizeCost / 100 );
2102  }
2103 }
2104 
2106 {
2107  if ( !nbPoints || !p2->nbPoints )
2108  return false;
2109 
2110  // here we only care if the lines start or end at the other line -- we don't want to test
2111  // touches as that is true for "T" type joins!
2112  const double x1first = x.front();
2113  const double x1last = x.back();
2114  const double x2first = p2->x.front();
2115  const double x2last = p2->x.back();
2116  const double y1first = y.front();
2117  const double y1last = y.back();
2118  const double y2first = p2->y.front();
2119  const double y2last = p2->y.back();
2120 
2121  const bool p2startTouches = ( qgsDoubleNear( x1first, x2first ) && qgsDoubleNear( y1first, y2first ) )
2122  || ( qgsDoubleNear( x1last, x2first ) && qgsDoubleNear( y1last, y2first ) );
2123 
2124  const bool p2endTouches = ( qgsDoubleNear( x1first, x2last ) && qgsDoubleNear( y1first, y2last ) )
2125  || ( qgsDoubleNear( x1last, x2last ) && qgsDoubleNear( y1last, y2last ) );
2126  // only one endpoint can touch, not both
2127  if ( ( !p2startTouches && !p2endTouches ) || ( p2startTouches && p2endTouches ) )
2128  return false;
2129 
2130  // now we know that we have one line endpoint touching only, but there's still a chance
2131  // that the other side of p2 may touch the original line NOT at the other endpoint
2132  // so we need to check that this point doesn't intersect
2133  const double p2otherX = p2startTouches ? x2last : x2first;
2134  const double p2otherY = p2startTouches ? y2last : y2first;
2135 
2136  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
2137 
2138  GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
2139 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
2140  GEOSCoordSeq_setXY_r( geosctxt, coord, 0, p2otherX, p2otherY );
2141 #else
2142  GEOSCoordSeq_setX_r( geosctxt, coord, 0, p2otherX );
2143  GEOSCoordSeq_setY_r( geosctxt, coord, 0, p2otherY );
2144 #endif
2145 
2146  geos::unique_ptr p2OtherEnd( GEOSGeom_createPoint_r( geosctxt, coord ) );
2147  try
2148  {
2149  return ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), p2OtherEnd.get() ) != 1 );
2150  }
2151  catch ( GEOSException &e )
2152  {
2153  qWarning( "GEOS exception: %s", e.what() );
2154  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2155  return false;
2156  }
2157 }
2158 
2160 {
2161  if ( !mGeos )
2162  createGeosGeom();
2163  if ( !other->mGeos )
2164  other->createGeosGeom();
2165 
2166  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2167  try
2168  {
2169  GEOSGeometry *g1 = GEOSGeom_clone_r( ctxt, mGeos );
2170  GEOSGeometry *g2 = GEOSGeom_clone_r( ctxt, other->mGeos );
2171  GEOSGeometry *geoms[2] = { g1, g2 };
2172  geos::unique_ptr g( GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 ) );
2173  geos::unique_ptr gTmp( GEOSLineMerge_r( ctxt, g.get() ) );
2174 
2175  if ( GEOSGeomTypeId_r( ctxt, gTmp.get() ) != GEOS_LINESTRING )
2176  {
2177  // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
2178  return false;
2179  }
2180  invalidateGeos();
2181 
2182  // set up new geometry
2183  mGeos = gTmp.release();
2184  mOwnsGeom = true;
2185 
2186  deleteCoords();
2187  qDeleteAll( mHoles );
2188  mHoles.clear();
2189  extractCoords( mGeos );
2190  return true;
2191  }
2192  catch ( GEOSException &e )
2193  {
2194  qWarning( "GEOS exception: %s", e.what() );
2195  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2196  return false;
2197  }
2198 }
2199 
2201 {
2202  if ( mLF->alwaysShow() )
2203  {
2204  //if feature is set to always show, bump the priority up by orders of magnitude
2205  //so that other feature's labels are unlikely to be placed over the label for this feature
2206  //(negative numbers due to how pal::extract calculates inactive cost)
2207  return -0.2;
2208  }
2209 
2210  return mLF->priority() >= 0 ? mLF->priority() : mLF->layer()->priority();
2211 }
2212 
2214 {
2215  bool uprightLabel = false;
2216 
2217  switch ( mLF->layer()->upsidedownLabels() )
2218  {
2219  case Layer::Upright:
2220  uprightLabel = true;
2221  break;
2222  case Layer::ShowDefined:
2223  // upright only dynamic labels
2224  if ( !hasFixedRotation() || ( !hasFixedPosition() && fixedAngle() == 0.0 ) )
2225  {
2226  uprightLabel = true;
2227  }
2228  break;
2229  case Layer::ShowAll:
2230  break;
2231  default:
2232  uprightLabel = true;
2233  }
2234  return uprightLabel;
2235 }
2236 
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:1756
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:1513
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:2064
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:2159
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:2213
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:1959
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:2105
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:2200
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:1246
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