QGIS API Documentation  3.27.0-Master (bef583a8ef)
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, Qgis::LabelPredefinedPointPosition position, double distanceToLabel, const QgsMargins &visualMargin, double symbolWidthOffset, double symbolHeightOffset, double angle )
434 {
435  double alpha = 0.0;
436  double deltaX = 0;
437  double deltaY = 0;
438 
439  switch ( position )
440  {
443  alpha = 3 * M_PI_4;
444  deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
445  deltaY = -visualMargin.bottom() + symbolHeightOffset;
446  break;
447 
449  quadrant = 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< Qgis::LabelPredefinedPointPosition > 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() == Qgis::LabelOffsetType::FromSymbolBounds ? mLF->symbolSize().width() / 2.0 : 0.0 );
549  double symbolHeightOffset = ( mLF->offsetType() == Qgis::LabelOffsetType::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 ( Qgis::LabelPredefinedPointPosition 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 
810 
811  double candidateCenterX, candidateCenterY;
812  int i = 0;
813  while ( currentDistanceAlongLine <= totalLineLength )
814  {
815  if ( pal->isCanceled() )
816  {
817  return lPos.size();
818  }
819 
820  line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateCenterX, &candidateCenterY );
821 
822  // penalize positions which are further from the line's anchor point
823  double cost = std::fabs( lineAnchorPoint - currentDistanceAlongLine ) / totalLineLength; // <0, 0.5>
824  cost /= 1000; // < 0, 0.0005 >
825 
826  double labelX = 0;
827  switch ( textPoint )
828  {
830  labelX = candidateCenterX;
831  break;
833  labelX = candidateCenterX - labelWidth / 2;
834  break;
836  labelX = candidateCenterX - labelWidth;
837  break;
839  // not possible here
840  break;
841  }
842  lPos.emplace_back( std::make_unique< LabelPosition >( i, labelX, candidateCenterY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) );
843 
844  currentDistanceAlongLine += lineStepDistance;
845 
846  i++;
847 
848  if ( lineStepDistance < 0 )
849  break;
850  }
851 
852  return lPos.size();
853 }
854 
855 std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
856 {
857  double labelWidth = getLabelWidth();
858  double labelHeight = getLabelHeight();
859  double distanceLineToLabel = getLabelDistance();
860  QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
861  if ( flags == 0 )
862  flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
863 
864  // 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
865  QVector< int > extremeAngleNodes;
866  PointSet *line = mapShape;
867  int numberNodes = line->nbPoints;
868  std::vector< double > &x = line->x;
869  std::vector< double > &y = line->y;
870 
871  // closed line? if so, we need to handle the final node angle
872  bool closedLine = qgsDoubleNear( x[0], x[ numberNodes - 1] ) && qgsDoubleNear( y[0], y[numberNodes - 1 ] );
873  for ( int i = 1; i <= numberNodes - ( closedLine ? 1 : 2 ); ++i )
874  {
875  double x1 = x[i - 1];
876  double x2 = x[i];
877  double x3 = x[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
878  double y1 = y[i - 1];
879  double y2 = y[i];
880  double y3 = y[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
881  if ( qgsDoubleNear( y2, y3 ) && qgsDoubleNear( x2, x3 ) )
882  continue;
883  if ( qgsDoubleNear( y1, y2 ) && qgsDoubleNear( x1, x2 ) )
884  continue;
885  double vertexAngle = M_PI - ( std::atan2( y3 - y2, x3 - x2 ) - std::atan2( y2 - y1, x2 - x1 ) );
886  vertexAngle = QgsGeometryUtils::normalizedAngle( vertexAngle );
887 
888  // extreme angles form more than 45 degree angle at a node - these are the ones we don't want labels to cross
889  if ( vertexAngle < M_PI * 135.0 / 180.0 || vertexAngle > M_PI * 225.0 / 180.0 )
890  extremeAngleNodes << i;
891  }
892  extremeAngleNodes << numberNodes - 1;
893 
894  if ( extremeAngleNodes.isEmpty() )
895  {
896  // no extreme angles - createCandidatesAlongLineNearMidpoint will be more appropriate
897  return 0;
898  }
899 
900  // calculate lengths of segments, and work out longest straight-ish segment
901  std::vector< double > segmentLengths( numberNodes - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
902  std::vector< double > distanceToSegment( numberNodes ); // absolute distance bw pt[0] and pt[i] along the line
903  double totalLineLength = 0.0;
904  QVector< double > straightSegmentLengths;
905  QVector< double > straightSegmentAngles;
906  straightSegmentLengths.reserve( extremeAngleNodes.size() + 1 );
907  straightSegmentAngles.reserve( extremeAngleNodes.size() + 1 );
908  double currentStraightSegmentLength = 0;
909  double longestSegmentLength = 0;
910  int segmentIndex = 0;
911  double segmentStartX = x[0];
912  double segmentStartY = y[0];
913  for ( int i = 0; i < numberNodes - 1; i++ )
914  {
915  if ( i == 0 )
916  distanceToSegment[i] = 0;
917  else
918  distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
919 
920  segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
921  totalLineLength += segmentLengths[i];
922  if ( extremeAngleNodes.contains( i ) )
923  {
924  // at an extreme angle node, so reset counters
925  straightSegmentLengths << currentStraightSegmentLength;
926  straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[i] - segmentStartY, x[i] - segmentStartX ) );
927  longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
928  segmentIndex++;
929  currentStraightSegmentLength = 0;
930  segmentStartX = x[i];
931  segmentStartY = y[i];
932  }
933  currentStraightSegmentLength += segmentLengths[i];
934  }
935  distanceToSegment[line->nbPoints - 1] = totalLineLength;
936  straightSegmentLengths << currentStraightSegmentLength;
937  straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[numberNodes - 1] - segmentStartY, x[numberNodes - 1] - segmentStartX ) );
938  longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
939  const double lineAnchorPoint = totalLineLength * mLF->lineAnchorPercent();
940 
941  if ( totalLineLength < labelWidth )
942  {
943  return 0; //createCandidatesAlongLineNearMidpoint will be more appropriate
944  }
945 
947 
948  const std::size_t candidateTargetCount = maximumLineCandidates();
949  double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
950  lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
951 
952  double distanceToEndOfSegment = 0.0;
953  int lastNodeInSegment = 0;
954  // finally, loop through all these straight segments. For each we create candidates along the straight segment.
955  for ( int i = 0; i < straightSegmentLengths.count(); ++i )
956  {
957  currentStraightSegmentLength = straightSegmentLengths.at( i );
958  double currentSegmentAngle = straightSegmentAngles.at( i );
959  lastNodeInSegment = extremeAngleNodes.at( i );
960  double distanceToStartOfSegment = distanceToEndOfSegment;
961  distanceToEndOfSegment = distanceToSegment[ lastNodeInSegment ];
962  double distanceToCenterOfSegment = 0.5 * ( distanceToEndOfSegment + distanceToStartOfSegment );
963 
964  if ( currentStraightSegmentLength < labelWidth )
965  // can't fit a label on here
966  continue;
967 
968  double currentDistanceAlongLine = distanceToStartOfSegment;
969  double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
970  double candidateLength = 0.0;
971  double cost = 0.0;
972  double angle = 0.0;
973  double beta = 0.0;
974 
975  //calculate some cost penalties
976  double segmentCost = 1.0 - ( distanceToEndOfSegment - distanceToStartOfSegment ) / longestSegmentLength; // 0 -> 1 (lower for longer segments)
977  double segmentAngleCost = 1 - std::fabs( std::fmod( currentSegmentAngle, M_PI ) - M_PI_2 ) / M_PI_2; // 0 -> 1, lower for more horizontal segments
978 
979  while ( currentDistanceAlongLine + labelWidth < distanceToEndOfSegment )
980  {
981  if ( pal->isCanceled() )
982  {
983  return lPos.size();
984  }
985 
986  // calculate positions along linestring corresponding to start and end of current label candidate
987  line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
988  line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
989 
990  candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
991 
992 
993  // LOTS OF DIFFERENT COSTS TO BALANCE HERE - feel free to tweak these, but please add a unit test
994  // which covers the situation you are adjusting for (e.g., "given equal length lines, choose the more horizontal line")
995 
996  cost = candidateLength / labelWidth;
997  if ( cost > 0.98 )
998  cost = 0.0001;
999  else
1000  {
1001  // jaggy line has a greater cost
1002  cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
1003  }
1004 
1005  const double labelCenter = currentDistanceAlongLine + labelWidth / 2.0;
1006  double labelTextAnchor = 0;
1007  switch ( textPoint )
1008  {
1010  labelTextAnchor = currentDistanceAlongLine;
1011  break;
1013  labelTextAnchor = currentDistanceAlongLine + labelWidth / 2.0;
1014  break;
1016  labelTextAnchor = currentDistanceAlongLine + labelWidth;
1017  break;
1019  // not possible here
1020  break;
1021  }
1022 
1023  const bool placementIsFlexible = mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1024  // penalize positions which are further from the straight segments's midpoint
1025  if ( placementIsFlexible )
1026  {
1027  // only apply this if labels are being placed toward the center of overall lines -- otherwise it messes with the distance from anchor cost
1028  double costCenter = 2 * std::fabs( labelCenter - distanceToCenterOfSegment ) / ( distanceToEndOfSegment - distanceToStartOfSegment ); // 0 -> 1
1029  cost += costCenter * 0.0005; // < 0, 0.0005 >
1030  }
1031 
1032  if ( !closedLine )
1033  {
1034  // penalize positions which are further from line anchor point of whole linestring (by default the middle of the line)
1035  // this only applies to non closed linestrings, since the middle of a closed linestring is effectively arbitrary
1036  // and irrelevant to labeling
1037  double costLineCenter = 2 * std::fabs( labelTextAnchor - lineAnchorPoint ) / totalLineLength; // 0 -> 1
1038  cost += costLineCenter * 0.0005; // < 0, 0.0005 >
1039  }
1040 
1041  if ( placementIsFlexible )
1042  {
1043  cost += segmentCost * 0.0005; // prefer labels on longer straight segments
1044  cost += segmentAngleCost * 0.0001; // prefer more horizontal segments, but this is less important than length considerations
1045  }
1046 
1047  if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
1048  {
1049  angle = 0.0;
1050  }
1051  else
1052  angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1053 
1054  labelWidth = getLabelWidth( angle );
1055  labelHeight = getLabelHeight( angle );
1056  beta = angle + M_PI_2;
1057 
1059  {
1060  // find out whether the line direction for this candidate is from right to left
1061  bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1062  // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1063  bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1064  bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1065  bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1066 
1067  if ( belowLine )
1068  {
1069  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1070  {
1071  const double candidateCost = cost + ( reversed ? 0 : 0.001 );
1072  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
1073  }
1074  }
1075  if ( aboveLine )
1076  {
1077  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1078  {
1079  const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1080  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
1081  }
1082  }
1083  if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1084  {
1085  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1086  {
1087  const double candidateCost = cost + 0.002;
1088  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
1089  }
1090  }
1091  }
1093  {
1094  lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1095  }
1096  else
1097  {
1098  // an invalid arrangement?
1099  }
1100 
1101  currentDistanceAlongLine += lineStepDistance;
1102  }
1103  }
1104 
1105  return lPos.size();
1106 }
1107 
1108 std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost, Pal *pal )
1109 {
1110  double distanceLineToLabel = getLabelDistance();
1111 
1112  double labelWidth = getLabelWidth();
1113  double labelHeight = getLabelHeight();
1114 
1115  double angle;
1116  double cost;
1117 
1118  QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1119  if ( flags == 0 )
1120  flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1121 
1122  PointSet *line = mapShape;
1123  int nbPoints = line->nbPoints;
1124  std::vector< double > &x = line->x;
1125  std::vector< double > &y = line->y;
1126 
1127  std::vector< double > segmentLengths( nbPoints - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
1128  std::vector< double >distanceToSegment( nbPoints ); // absolute distance bw pt[0] and pt[i] along the line
1129 
1130  double totalLineLength = 0.0; // line length
1131  for ( int i = 0; i < line->nbPoints - 1; i++ )
1132  {
1133  if ( i == 0 )
1134  distanceToSegment[i] = 0;
1135  else
1136  distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
1137 
1138  segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
1139  totalLineLength += segmentLengths[i];
1140  }
1141  distanceToSegment[line->nbPoints - 1] = totalLineLength;
1142 
1143  double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
1144  double currentDistanceAlongLine = 0;
1145 
1147 
1148  const std::size_t candidateTargetCount = maximumLineCandidates();
1149 
1150  if ( totalLineLength > labelWidth )
1151  {
1152  lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
1153  }
1154  else if ( !line->isClosed() ) // line length < label width => centering label position
1155  {
1156  currentDistanceAlongLine = - ( labelWidth - totalLineLength ) / 2.0;
1157  lineStepDistance = -1;
1158  totalLineLength = labelWidth;
1159  }
1160  else
1161  {
1162  // closed line, not long enough for label => no candidates!
1163  currentDistanceAlongLine = std::numeric_limits< double >::max();
1164  }
1165 
1166  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!
1167 
1168  switch ( mLF->lineAnchorType() )
1169  {
1171  break;
1172 
1174  switch ( textPoint )
1175  {
1177  currentDistanceAlongLine = std::min( lineAnchorPoint, totalLineLength * 0.99 - labelWidth );
1178  break;
1180  currentDistanceAlongLine = std::min( lineAnchorPoint - labelWidth / 2, totalLineLength * 0.99 - labelWidth );
1181  break;
1183  currentDistanceAlongLine = std::min( lineAnchorPoint - labelWidth, totalLineLength * 0.99 - labelWidth );
1184  break;
1186  // not possible here
1187  break;
1188  }
1189  lineStepDistance = -1;
1190  break;
1191  }
1192 
1193  double candidateLength;
1194  double beta;
1195  double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
1196  int i = 0;
1197  while ( currentDistanceAlongLine <= totalLineLength - labelWidth || mLF->lineAnchorType() == QgsLabelLineSettings::AnchorType::Strict )
1198  {
1199  if ( pal->isCanceled() )
1200  {
1201  return lPos.size();
1202  }
1203 
1204  // calculate positions along linestring corresponding to start and end of current label candidate
1205  line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
1206  line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
1207 
1208  if ( currentDistanceAlongLine < 0 )
1209  {
1210  // label is bigger than line, use whole available line
1211  candidateLength = std::sqrt( ( x[nbPoints - 1] - x[0] ) * ( x[nbPoints - 1] - x[0] )
1212  + ( y[nbPoints - 1] - y[0] ) * ( y[nbPoints - 1] - y[0] ) );
1213  }
1214  else
1215  {
1216  candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
1217  }
1218 
1219  cost = candidateLength / labelWidth;
1220  if ( cost > 0.98 )
1221  cost = 0.0001;
1222  else
1223  {
1224  // jaggy line has a greater cost
1225  cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
1226  }
1227 
1228  // penalize positions which are further from the line's anchor point
1229  double textAnchorPoint = 0;
1230  switch ( textPoint )
1231  {
1233  textAnchorPoint = currentDistanceAlongLine;
1234  break;
1236  textAnchorPoint = currentDistanceAlongLine + labelWidth / 2;
1237  break;
1239  textAnchorPoint = currentDistanceAlongLine + labelWidth;
1240  break;
1242  // not possible here
1243  break;
1244  }
1245  double costCenter = std::fabs( lineAnchorPoint - textAnchorPoint ) / totalLineLength; // <0, 0.5>
1246  cost += costCenter / 1000; // < 0, 0.0005 >
1247  cost += initialCost;
1248 
1249  if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
1250  {
1251  angle = 0.0;
1252  }
1253  else
1254  angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1255 
1256  labelWidth = getLabelWidth( angle );
1257  labelHeight = getLabelHeight( angle );
1258  beta = angle + M_PI_2;
1259 
1261  {
1262  // find out whether the line direction for this candidate is from right to left
1263  bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1264  // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1265  bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1266  bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1267  bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1268 
1269  if ( aboveLine )
1270  {
1271  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1272  {
1273  const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1274  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
1275  }
1276  }
1277  if ( belowLine )
1278  {
1279  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1280  {
1281  const double candidateCost = cost + ( !reversed ? 0.001 : 0 );
1282  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
1283  }
1284  }
1285  if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1286  {
1287  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1288  {
1289  const double candidateCost = cost + 0.002;
1290  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
1291  }
1292  }
1293  }
1295  {
1296  lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1297  }
1298  else
1299  {
1300  // an invalid arrangement?
1301  }
1302 
1303  currentDistanceAlongLine += lineStepDistance;
1304 
1305  i++;
1306 
1307  if ( lineStepDistance < 0 )
1308  break;
1309  }
1310 
1311  return lPos.size();
1312 }
1313 
1314 std::unique_ptr< LabelPosition > FeaturePart::curvedPlacementAtOffset( PointSet *mapShape, const std::vector< double> &pathDistances, QgsTextRendererUtils::LabelLineDirection direction, const double offsetAlongLine, bool &labeledLineSegmentIsRightToLeft, bool applyAngleConstraints, bool uprightOnly )
1315 {
1316  const QgsPrecalculatedTextMetrics *metrics = qgis::down_cast< QgsTextLabelFeature * >( mLF )->textMetrics();
1317  Q_ASSERT( metrics );
1318 
1319  const double maximumCharacterAngleInside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleInside() ) : -1;
1320  const double maximumCharacterAngleOutside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleOutside() ) : -1;
1321 
1322  std::unique_ptr< QgsTextRendererUtils::CurvePlacementProperties > placement(
1323  QgsTextRendererUtils::generateCurvedTextPlacement( *metrics, mapShape->x.data(), mapShape->y.data(), mapShape->nbPoints, pathDistances, offsetAlongLine, direction, maximumCharacterAngleInside, maximumCharacterAngleOutside, uprightOnly )
1324  );
1325 
1326  labeledLineSegmentIsRightToLeft = !uprightOnly ? placement->labeledLineSegmentIsRightToLeft : placement->flippedCharacterPlacementToGetUprightLabels;
1327 
1328  if ( placement->graphemePlacement.empty() )
1329  return nullptr;
1330 
1331  auto it = placement->graphemePlacement.constBegin();
1332  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 );
1333  firstPosition->setUpsideDownCharCount( placement->upsideDownCharCount );
1334  firstPosition->setPartId( it->graphemeIndex );
1335  LabelPosition *previousPosition = firstPosition.get();
1336  it++;
1337  while ( it != placement->graphemePlacement.constEnd() )
1338  {
1339  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 );
1340  position->setPartId( it->graphemeIndex );
1341 
1342  LabelPosition *nextPosition = position.get();
1343  previousPosition->setNextPart( std::move( position ) );
1344  previousPosition = nextPosition;
1345  it++;
1346  }
1347 
1348  return firstPosition;
1349 }
1350 
1351 std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
1352 {
1353  const QgsPrecalculatedTextMetrics *li = qgis::down_cast< QgsTextLabelFeature *>( mLF )->textMetrics();
1354  Q_ASSERT( li );
1355 
1356  // label info must be present
1357  if ( !li )
1358  return 0;
1359 
1360  const int characterCount = li->count();
1361  if ( characterCount == 0 )
1362  return 0;
1363 
1364  // TODO - we may need an explicit penalty for overhanging labels. Currently, they are penalized just because they
1365  // are further from the line center, so non-overhanding placements are picked where possible.
1366 
1367  double totalCharacterWidth = 0;
1368  for ( int i = 0; i < characterCount; ++i )
1369  totalCharacterWidth += li->characterWidth( i );
1370 
1371  std::unique_ptr< PointSet > expanded;
1372  double shapeLength = mapShape->length();
1373 
1374  if ( totalRepeats() > 1 )
1375  allowOverrun = false;
1376 
1377  // unless in strict mode, label overrun should NEVER exceed the label length (or labels would sit off in space).
1378  // in fact, let's require that a minimum of 5% of the label text has to sit on the feature,
1379  // as we don't want a label sitting right at the start or end corner of a line
1380  double overrun = 0;
1381  switch ( mLF->lineAnchorType() )
1382  {
1384  overrun = std::min( mLF->overrunDistance(), totalCharacterWidth * 0.95 );
1385  break;
1387  // in strict mode, we force sufficient overrun to ensure label will always "fit", even if it's placed
1388  // so that the label start sits right on the end of the line OR the label end sits right on the start of the line
1389  overrun = std::max( mLF->overrunDistance(), totalCharacterWidth * 1.05 );
1390  break;
1391  }
1392 
1393  if ( totalCharacterWidth > shapeLength )
1394  {
1395  if ( !allowOverrun || shapeLength < totalCharacterWidth - 2 * overrun )
1396  {
1397  // label doesn't fit on this line, don't waste time trying to make candidates
1398  return 0;
1399  }
1400  }
1401 
1402  // calculate the anchor point for the original line shape as a GEOS point.
1403  // this must be done BEFORE we account for overrun by extending the shape!
1404  const geos::unique_ptr originalPoint = mapShape->interpolatePoint( shapeLength * mLF->lineAnchorPercent() );
1405 
1406  if ( allowOverrun && overrun > 0 )
1407  {
1408  // expand out line on either side to fit label
1409  expanded = mapShape->clone();
1410  expanded->extendLineByDistance( overrun, overrun, mLF->overrunSmoothDistance() );
1411  mapShape = expanded.get();
1412  shapeLength += 2 * overrun;
1413  }
1414 
1415  QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1416  if ( flags == 0 )
1417  flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1418  const bool hasAboveBelowLinePlacement = flags & QgsLabeling::LinePlacementFlag::AboveLine || flags & QgsLabeling::LinePlacementFlag::BelowLine;
1419  const double offsetDistance = mLF->distLabel() + li->characterHeight() / 2;
1420  std::unique_ptr< PointSet > mapShapeOffsetPositive;
1421  std::unique_ptr< PointSet > mapShapeOffsetNegative;
1422  if ( hasAboveBelowLinePlacement && !qgsDoubleNear( offsetDistance, 0 ) )
1423  {
1424  // create offseted map shapes to be used for above and below line placements
1425  if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1426  mapShapeOffsetPositive = mapShape->clone();
1427  if ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) || ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1428  mapShapeOffsetNegative = mapShape->clone();
1429  if ( offsetDistance >= 0.0 || !( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) )
1430  {
1431  if ( mapShapeOffsetPositive )
1432  mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance );
1433  if ( mapShapeOffsetNegative )
1434  mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance * -1 );
1435  }
1436  else
1437  {
1438  // In case of a negative offset distance, above line placement switch to below line and vice versa
1439  if ( flags & QgsLabeling::LinePlacementFlag::AboveLine
1440  && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1441  {
1442  flags &= ~QgsLabeling::LinePlacementFlag::AboveLine;
1443  flags |= QgsLabeling::LinePlacementFlag::BelowLine;
1444  }
1445  else if ( flags & QgsLabeling::LinePlacementFlag::BelowLine
1446  && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1447  {
1448  flags &= ~QgsLabeling::LinePlacementFlag::BelowLine;
1449  flags |= QgsLabeling::LinePlacementFlag::AboveLine;
1450  }
1451  if ( mapShapeOffsetPositive )
1452  mapShapeOffsetPositive->offsetCurveByDistance( offsetDistance * -1 );
1453  if ( mapShapeOffsetNegative )
1454  mapShapeOffsetNegative->offsetCurveByDistance( offsetDistance );
1455  }
1456  }
1457 
1459 
1460  std::vector< std::unique_ptr< LabelPosition >> positions;
1461  std::unique_ptr< LabelPosition > backupPlacement;
1462  for ( PathOffset offset : { PositiveOffset, NoOffset, NegativeOffset } )
1463  {
1464  PointSet *currentMapShape = nullptr;
1465  if ( offset == PositiveOffset && hasAboveBelowLinePlacement )
1466  {
1467  currentMapShape = mapShapeOffsetPositive.get();
1468  }
1469  if ( offset == NoOffset && flags & QgsLabeling::LinePlacementFlag::OnLine )
1470  {
1471  currentMapShape = mapShape;
1472  }
1473  if ( offset == NegativeOffset && hasAboveBelowLinePlacement )
1474  {
1475  currentMapShape = mapShapeOffsetNegative.get();
1476  }
1477  if ( !currentMapShape )
1478  continue;
1479 
1480  // distance calculation
1481  const auto [ pathDistances, totalDistance ] = currentMapShape->edgeDistances();
1482  if ( qgsDoubleNear( totalDistance, 0.0 ) )
1483  continue;
1484 
1485  double lineAnchorPoint = 0;
1486  if ( originalPoint && offset != NoOffset )
1487  {
1488  // the actual anchor point for the offset curves is the closest point on those offset curves
1489  // to the anchor point on the original line. This avoids anchor points which differ greatly
1490  // on the positive/negative offset lines due to line curvature.
1491  lineAnchorPoint = currentMapShape->lineLocatePoint( originalPoint.get() );
1492  }
1493  else
1494  {
1495  lineAnchorPoint = totalDistance * mLF->lineAnchorPercent();
1496  if ( offset == NegativeOffset )
1497  lineAnchorPoint = totalDistance - lineAnchorPoint;
1498  }
1499 
1500  if ( pal->isCanceled() )
1501  return 0;
1502 
1503  const std::size_t candidateTargetCount = maximumLineCandidates();
1504  double delta = std::max( li->characterHeight() / 6, totalDistance / candidateTargetCount );
1505 
1506  // generate curved labels
1507  double distanceAlongLineToStartCandidate = 0;
1508  bool singleCandidateOnly = false;
1509  switch ( mLF->lineAnchorType() )
1510  {
1512  break;
1513 
1515  switch ( textPoint )
1516  {
1518  distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint, 0.0, totalDistance * 0.999 );
1519  break;
1521  distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint - getLabelWidth() / 2, 0.0, totalDistance * 0.999 - getLabelWidth() / 2 );
1522  break;
1524  distanceAlongLineToStartCandidate = std::clamp( lineAnchorPoint - getLabelWidth(), 0.0, totalDistance * 0.999 - getLabelWidth() ) ;
1525  break;
1527  // not possible here
1528  break;
1529  }
1530  singleCandidateOnly = true;
1531  break;
1532  }
1533 
1534  bool hasTestedFirstPlacement = false;
1535  for ( ; distanceAlongLineToStartCandidate <= totalDistance; distanceAlongLineToStartCandidate += delta )
1536  {
1537  if ( singleCandidateOnly && hasTestedFirstPlacement )
1538  break;
1539 
1540  if ( pal->isCanceled() )
1541  return 0;
1542 
1543  hasTestedFirstPlacement = true;
1544  // placements may need to be reversed if using map orientation and the line has right-to-left direction
1545  bool labeledLineSegmentIsRightToLeft = false;
1546  const QgsTextRendererUtils::LabelLineDirection direction = ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? QgsTextRendererUtils::RespectPainterOrientation : QgsTextRendererUtils::FollowLineDirection;
1547  std::unique_ptr< LabelPosition > labelPosition = curvedPlacementAtOffset( currentMapShape, pathDistances, direction, distanceAlongLineToStartCandidate, labeledLineSegmentIsRightToLeft, !singleCandidateOnly,
1548  onlyShowUprightLabels() && ( !singleCandidateOnly || !( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ) );
1549 
1550  if ( !labelPosition )
1551  {
1552  continue;
1553  }
1554 
1555  bool isBackupPlacementOnly = false;
1556  if ( flags & QgsLabeling::LinePlacementFlag::MapOrientation )
1557  {
1558  if ( ( offset != NoOffset ) && !labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::AboveLine ) )
1559  {
1560  if ( singleCandidateOnly && offset == PositiveOffset )
1561  isBackupPlacementOnly = true;
1562  else
1563  continue;
1564  }
1565  if ( ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft && !( flags & QgsLabeling::LinePlacementFlag::BelowLine ) )
1566  {
1567  if ( singleCandidateOnly && offset == PositiveOffset )
1568  isBackupPlacementOnly = true;
1569  else
1570  continue;
1571  }
1572  }
1573 
1574  backupPlacement.reset();
1575 
1576  // evaluate cost
1577  const double angleDiff = labelPosition->angleDifferential();
1578  const double angleDiffAvg = characterCount > 1 ? ( angleDiff / ( characterCount - 1 ) ) : 0; // <0, pi> but pi/8 is much already
1579 
1580  // if anchor placement is towards start or end of line, we need to slightly tweak the costs to ensure that the
1581  // anchor weighting is sufficient to push labels towards start/end
1582  const bool anchorIsFlexiblePlacement = !singleCandidateOnly && mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1583  double cost = angleDiffAvg / 100; // <0, 0.031 > but usually <0, 0.003 >
1584  if ( cost < 0.0001 )
1585  cost = 0.0001;
1586 
1587  // penalize positions which are further from the line's anchor point
1588  double labelTextAnchor = 0;
1589  switch ( textPoint )
1590  {
1592  labelTextAnchor = distanceAlongLineToStartCandidate;
1593  break;
1595  labelTextAnchor = distanceAlongLineToStartCandidate + getLabelWidth() / 2;
1596  break;
1598  labelTextAnchor = distanceAlongLineToStartCandidate + getLabelWidth();
1599  break;
1601  // not possible here
1602  break;
1603  }
1604  double costCenter = std::fabs( lineAnchorPoint - labelTextAnchor ) / totalDistance; // <0, 0.5>
1605  cost += costCenter / ( anchorIsFlexiblePlacement ? 100 : 10 ); // < 0, 0.005 >, or <0, 0.05> if preferring placement close to start/end of line
1606 
1607  const bool isBelow = ( offset != NoOffset ) && labeledLineSegmentIsRightToLeft;
1608  if ( isBelow )
1609  {
1610  // add additional cost for on line placement
1611  cost += 0.001;
1612  }
1613  else if ( offset == NoOffset )
1614  {
1615  // add additional cost for below line placement
1616  cost += 0.002;
1617  }
1618 
1619  labelPosition->setCost( cost );
1620 
1621  std::unique_ptr< LabelPosition > p = std::make_unique< LabelPosition >( *labelPosition );
1622  if ( p && mLF->permissibleZonePrepared() )
1623  {
1624  bool within = true;
1625  LabelPosition *currentPos = p.get();
1626  while ( within && currentPos )
1627  {
1628  within = GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), currentPos->getX(), currentPos->getY(), currentPos->getWidth(), currentPos->getHeight(), currentPos->getAlpha() );
1629  currentPos = currentPos->nextPart();
1630  }
1631  if ( !within )
1632  {
1633  p.reset();
1634  }
1635  }
1636 
1637  if ( p )
1638  {
1639  if ( isBackupPlacementOnly )
1640  backupPlacement = std::move( p );
1641  else
1642  positions.emplace_back( std::move( p ) );
1643  }
1644  }
1645  }
1646 
1647  for ( std::unique_ptr< LabelPosition > &pos : positions )
1648  {
1649  lPos.emplace_back( std::move( pos ) );
1650  }
1651 
1652  if ( backupPlacement )
1653  lPos.emplace_back( std::move( backupPlacement ) );
1654 
1655  return positions.size();
1656 }
1657 
1658 /*
1659  * seg 2
1660  * pt3 ____________pt2
1661  * ¦ ¦
1662  * ¦ ¦
1663  * seg 3 ¦ BBOX ¦ seg 1
1664  * ¦ ¦
1665  * ¦____________¦
1666  * pt0 seg 0 pt1
1667  *
1668  */
1669 
1670 std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
1671 {
1672  double labelWidth = getLabelWidth();
1673  double labelHeight = getLabelHeight();
1674 
1675  const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1676  const std::size_t targetPolygonCandidates = maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * area() ) ) )
1677  : 0;
1678 
1679  const double totalArea = area();
1680 
1681  mapShape->parent = nullptr;
1682 
1683  if ( pal->isCanceled() )
1684  return 0;
1685 
1686  QLinkedList<PointSet *> shapes_final = splitPolygons( mapShape, labelWidth, labelHeight );
1687 #if 0
1688  QgsDebugMsg( QStringLiteral( "PAL split polygons resulted in:" ) );
1689  for ( PointSet *ps : shapes_final )
1690  {
1691  QgsDebugMsg( ps->toWkt() );
1692  }
1693 #endif
1694 
1695  std::size_t nbp = 0;
1696 
1697  if ( !shapes_final.isEmpty() )
1698  {
1699  int id = 0; // ids for candidates
1700  double dlx, dly; // delta from label center and bottom-left corner
1701  double alpha = 0.0; // rotation for the label
1702  double px, py;
1703 
1704  double beta;
1705  double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
1706  double rx, ry;
1707  std::vector< OrientedConvexHullBoundingBox > boxes;
1708  boxes.reserve( shapes_final.size() );
1709 
1710  // Compute bounding box for each finalShape
1711  while ( !shapes_final.isEmpty() )
1712  {
1713  PointSet *shape = shapes_final.takeFirst();
1714  bool ok = false;
1716  if ( ok )
1717  boxes.emplace_back( box );
1718 
1719  if ( shape->parent )
1720  delete shape;
1721  }
1722 
1723  if ( pal->isCanceled() )
1724  return 0;
1725 
1726  double densityX = 1.0 / std::sqrt( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() );
1727  double densityY = densityX;
1728  int numTry = 0;
1729 
1730  //fit in polygon only mode slows down calculation a lot, so if it's enabled
1731  //then use a smaller limit for number of iterations
1732  int maxTry = mLF->permissibleZonePrepared() ? 7 : 10;
1733 
1734  std::size_t numberCandidatesGenerated = 0;
1735 
1736  do
1737  {
1738  for ( OrientedConvexHullBoundingBox &box : boxes )
1739  {
1740  // there is two possibilities here:
1741  // 1. no maximum candidates for polygon setting is in effect (i.e. maxPolygonCandidates == 0). In that case,
1742  // we base our dx/dy on the current maximumPolygonCandidatesPerMapUnitSquared value. That should give us the desired
1743  // density of candidates straight up. Easy!
1744  // 2. a maximum candidate setting IS in effect. In that case, we want to generate a good initial estimate for dx/dy
1745  // which gives us a good spatial coverage of the polygon while roughly matching the desired maximum number of candidates.
1746  // If dx/dy is too small, then too many candidates will be generated, which is both slow AND results in poor coverage of the
1747  // polygon (after culling candidates to the max number, only those clustered around the polygon's pole of inaccessibility
1748  // will remain).
1749  double dx = densityX;
1750  double dy = densityY;
1751  if ( numTry == 0 && maxPolygonCandidates > 0 )
1752  {
1753  // scale maxPolygonCandidates for just this convex hull
1754  const double boxArea = box.width * box.length;
1755  double maxThisBox = targetPolygonCandidates * boxArea / totalArea;
1756  dx = std::max( dx, std::sqrt( boxArea / maxThisBox ) * 0.8 );
1757  dy = dx;
1758  }
1759 
1760  if ( pal->isCanceled() )
1761  return numberCandidatesGenerated;
1762 
1763  if ( ( box.length * box.width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
1764  {
1765  // Very Large BBOX (should never occur)
1766  continue;
1767  }
1768 
1770  {
1771  //check width/height of bbox is sufficient for label
1772  if ( mLF->permissibleZone().boundingBox().width() < labelWidth ||
1773  mLF->permissibleZone().boundingBox().height() < labelHeight )
1774  {
1775  //no way label can fit in this box, skip it
1776  continue;
1777  }
1778  }
1779 
1780  bool enoughPlace = false;
1782  {
1783  enoughPlace = true;
1784  px = ( box.x[0] + box.x[2] ) / 2 - labelWidth;
1785  py = ( box.y[0] + box.y[2] ) / 2 - labelHeight;
1786  int i, j;
1787 
1788  // Virtual label: center on bbox center, label size = 2x original size
1789  // alpha = 0.
1790  // If all corner are in bbox then place candidates horizontaly
1791  for ( rx = px, i = 0; i < 2; rx = rx + 2 * labelWidth, i++ )
1792  {
1793  for ( ry = py, j = 0; j < 2; ry = ry + 2 * labelHeight, j++ )
1794  {
1795  if ( !mapShape->containsPoint( rx, ry ) )
1796  {
1797  enoughPlace = false;
1798  break;
1799  }
1800  }
1801  if ( !enoughPlace )
1802  {
1803  break;
1804  }
1805  }
1806 
1807  } // arrangement== FREE ?
1808 
1809  if ( mLF->layer()->arrangement() == Qgis::LabelPlacement::Horizontal || enoughPlace )
1810  {
1811  alpha = 0.0; // HORIZ
1812  }
1813  else if ( box.length > 1.5 * labelWidth && box.width > 1.5 * labelWidth )
1814  {
1815  if ( box.alpha <= M_PI_4 )
1816  {
1817  alpha = box.alpha;
1818  }
1819  else
1820  {
1821  alpha = box.alpha - M_PI_2;
1822  }
1823  }
1824  else if ( box.length > box.width )
1825  {
1826  alpha = box.alpha - M_PI_2;
1827  }
1828  else
1829  {
1830  alpha = box.alpha;
1831  }
1832 
1833  beta = std::atan2( labelHeight, labelWidth ) + alpha;
1834 
1835 
1836  //alpha = box->alpha;
1837 
1838  // delta from label center and down-left corner
1839  dlx = std::cos( beta ) * diago;
1840  dly = std::sin( beta ) * diago;
1841 
1842  double px0 = box.width / 2.0;
1843  double py0 = box.length / 2.0;
1844 
1845  px0 -= std::ceil( px0 / dx ) * dx;
1846  py0 -= std::ceil( py0 / dy ) * dy;
1847 
1848  for ( px = px0; px <= box.width; px += dx )
1849  {
1850  if ( pal->isCanceled() )
1851  break;
1852 
1853  for ( py = py0; py <= box.length; py += dy )
1854  {
1855 
1856  rx = std::cos( box.alpha ) * px + std::cos( box.alpha - M_PI_2 ) * py;
1857  ry = std::sin( box.alpha ) * px + std::sin( box.alpha - M_PI_2 ) * py;
1858 
1859  rx += box.x[0];
1860  ry += box.y[0];
1861 
1862  if ( mLF->permissibleZonePrepared() )
1863  {
1864  if ( GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), rx - dlx, ry - dly, labelWidth, labelHeight, alpha ) )
1865  {
1866  // cost is set to minimal value, evaluated later
1867  lPos.emplace_back( std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver ) );
1868  numberCandidatesGenerated++;
1869  }
1870  }
1871  else
1872  {
1873  // TODO - this should be an intersection test, not just a contains test of the candidate centroid
1874  // because in some cases we would want to allow candidates which mostly overlap the polygon even though
1875  // their centroid doesn't overlap (e.g. a "U" shaped polygon)
1876  // but the bugs noted in CostCalculator currently prevent this
1877  if ( mapShape->containsPoint( rx, ry ) )
1878  {
1879  std::unique_ptr< LabelPosition > potentialCandidate = std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver );
1880  // cost is set to minimal value, evaluated later
1881  lPos.emplace_back( std::move( potentialCandidate ) );
1882  numberCandidatesGenerated++;
1883  }
1884  }
1885  }
1886  }
1887  } // forall box
1888 
1889  nbp = numberCandidatesGenerated;
1890  if ( maxPolygonCandidates > 0 && nbp < targetPolygonCandidates )
1891  {
1892  densityX /= 2;
1893  densityY /= 2;
1894  numTry++;
1895  }
1896  else
1897  {
1898  break;
1899  }
1900  }
1901  while ( numTry < maxTry );
1902 
1903  nbp = numberCandidatesGenerated;
1904  }
1905  else
1906  {
1907  nbp = 0;
1908  }
1909 
1910  return nbp;
1911 }
1912 
1913 std::size_t FeaturePart::createCandidatesOutsidePolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, Pal *pal )
1914 {
1915  // calculate distance between horizontal lines
1916  const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1917  std::size_t candidatesCreated = 0;
1918 
1919  double labelWidth = getLabelWidth();
1920  double labelHeight = getLabelHeight();
1921  double distanceToLabel = getLabelDistance();
1922  const QgsMargins &visualMargin = mLF->visualMargin();
1923 
1924  /*
1925  * From Rylov & Reimer (2016) "A practical algorithm for the external annotation of area features":
1926  *
1927  * The list of rules adapted to the
1928  * needs of externally labelling areal features is as follows:
1929  * R1. Labels should be placed horizontally.
1930  * R2. Label should be placed entirely outside at some
1931  * distance from the area feature.
1932  * R3. Name should not cross the boundary of its area
1933  * feature.
1934  * R4. The name should be placed in way that takes into
1935  * account the shape of the feature by achieving a
1936  * balance between the feature and its name, emphasizing their relationship.
1937  * R5. The lettering to the right and slightly above the
1938  * symbol is prioritized.
1939  *
1940  * In the following subsections we utilize four of the five rules
1941  * for two subtasks of label placement, namely, for candidate
1942  * positions generation (R1, R2, and R3) and for measuring their
1943  * ‘goodness’ (R4). The rule R5 is applicable only in the case when
1944  * the area of a polygonal feature is small and the feature can be
1945  * treated and labelled as a point-feature
1946  */
1947 
1948  /*
1949  * QGIS approach (cite Dawson (2020) if you want ;) )
1950  *
1951  * We differ from the horizontal sweep line approach described by Rylov & Reimer and instead
1952  * rely on just generating a set of points at regular intervals along the boundary of the polygon (exterior ring).
1953  *
1954  * In practice, this generates similar results as Rylov & Reimer, but has the additional benefits that:
1955  * 1. It avoids the need to calculate intersections between the sweep line and the polygon
1956  * 2. For horizontal or near horizontal segments, Rylov & Reimer propose generating evenly spaced points along
1957  * these segments-- i.e. the same approach as we do for the whole polygon
1958  * 3. It's easier to determine in advance exactly how many candidate positions we'll be generating, and accordingly
1959  * we can easily pick the distance between points along the exterior ring so that the number of positions generated
1960  * matches our target number (targetPolygonCandidates)
1961  */
1962 
1963  // TO consider -- for very small polygons (wrt label size), treat them just like a point feature?
1964 
1965  double cx, cy;
1966  getCentroid( cx, cy, false );
1967 
1968  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1969 
1970  // be a bit sneaky and only buffer out 50% here, and then do the remaining 50% when we make the label candidate itself.
1971  // this avoids candidates being created immediately over the buffered ring and always intersecting with it...
1972  geos::unique_ptr buffer( GEOSBuffer_r( ctxt, geos(), distanceToLabel * 0.5, 1 ) );
1973  std::unique_ptr< QgsAbstractGeometry> gg( QgsGeos::fromGeos( buffer.get() ) );
1974 
1975  geos::prepared_unique_ptr preparedBuffer( GEOSPrepare_r( ctxt, buffer.get() ) );
1976 
1977  const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( gg.get() );
1978  if ( !poly )
1979  return candidatesCreated;
1980 
1981  const QgsLineString *ring = qgsgeometry_cast< const QgsLineString *>( poly->exteriorRing() );
1982  if ( !ring )
1983  return candidatesCreated;
1984 
1985  // 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,
1986  // i.e a loooooong skinny polygon with small area should still generate a large number of candidates)
1987  const double ringLength = ring->length();
1988  const double circleArea = std::pow( ringLength, 2 ) / ( 4 * M_PI );
1989  const std::size_t candidatesForArea = static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * circleArea ) );
1990  const std::size_t targetPolygonCandidates = std::max( static_cast< std::size_t >( 16 ), maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, candidatesForArea ) : candidatesForArea );
1991 
1992  // assume each position generates one candidate
1993  const double delta = ringLength / targetPolygonCandidates;
1994  geos::unique_ptr geosPoint;
1995 
1996  const double maxDistCentroidToLabelX = std::max( xmax - cx, cx - xmin ) + distanceToLabel;
1997  const double maxDistCentroidToLabelY = std::max( ymax - cy, cy - ymin ) + distanceToLabel;
1998  const double estimateOfMaxPossibleDistanceCentroidToLabel = std::sqrt( maxDistCentroidToLabelX * maxDistCentroidToLabelX + maxDistCentroidToLabelY * maxDistCentroidToLabelY );
1999 
2000  // Satisfy R1: Labels should be placed horizontally.
2001  const double labelAngle = 0;
2002 
2003  std::size_t i = lPos.size();
2004  auto addCandidate = [&]( double x, double y, Qgis::LabelPredefinedPointPosition position )
2005  {
2006  double labelX = 0;
2007  double labelY = 0;
2009 
2010  // Satisfy R2: Label should be placed entirely outside at some distance from the area feature.
2011  createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel * 0.5, visualMargin, 0, 0, labelAngle );
2012 
2013  std::unique_ptr< LabelPosition > candidate = std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, labelAngle, 0, this, false, quadrant );
2014  if ( candidate->intersects( preparedBuffer.get() ) )
2015  {
2016  // satisfy R3. Name should not cross the boundary of its area feature.
2017 
2018  // actually, we use the buffered geometry here, because a label shouldn't be closer to the polygon then the minimum distance value
2019  return;
2020  }
2021 
2022  // cost candidates by their distance to the feature's centroid (following Rylov & Reimer)
2023 
2024  // Satisfy R4. The name should be placed in way that takes into
2025  // account the shape of the feature by achieving a
2026  // balance between the feature and its name, emphasizing their relationship.
2027 
2028 
2029  // here we deviate a little from R&R, and instead of just calculating the centroid distance
2030  // to centroid of label, we calculate the distance from the centroid to the nearest point on the label
2031 
2032  const double centroidDistance = candidate->getDistanceToPoint( cx, cy );
2033  const double centroidCost = centroidDistance / estimateOfMaxPossibleDistanceCentroidToLabel;
2034  candidate->setCost( centroidCost );
2035 
2036  lPos.emplace_back( std::move( candidate ) );
2037  candidatesCreated++;
2038  ++i;
2039  };
2040 
2041  ring->visitPointsByRegularDistance( delta, [&]( double x, double y, double, double,
2042  double startSegmentX, double startSegmentY, double, double,
2043  double endSegmentX, double endSegmentY, double, double )
2044  {
2045  // get normal angle for segment
2046  float angle = atan2( static_cast< float >( endSegmentY - startSegmentY ), static_cast< float >( endSegmentX - startSegmentX ) ) * 180 / M_PI;
2047  if ( angle < 0 )
2048  angle += 360;
2049 
2050  // adapted fom Rylov & Reimer figure 9
2051  if ( angle >= 0 && angle <= 5 )
2052  {
2055  }
2056  else if ( angle <= 85 )
2057  {
2059  }
2060  else if ( angle <= 90 )
2061  {
2064  }
2065 
2066  else if ( angle <= 95 )
2067  {
2070  }
2071  else if ( angle <= 175 )
2072  {
2074  }
2075  else if ( angle <= 180 )
2076  {
2079  }
2080 
2081  else if ( angle <= 185 )
2082  {
2085  }
2086  else if ( angle <= 265 )
2087  {
2089  }
2090  else if ( angle <= 270 )
2091  {
2094  }
2095  else if ( angle <= 275 )
2096  {
2099  }
2100  else if ( angle <= 355 )
2101  {
2103  }
2104  else
2105  {
2108  }
2109 
2110  return !pal->isCanceled();
2111  } );
2112 
2113  return candidatesCreated;
2114 }
2115 
2116 std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates( Pal *pal )
2117 {
2118  std::vector< std::unique_ptr< LabelPosition > > lPos;
2119  double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
2120 
2121  if ( mLF->hasFixedPosition() )
2122  {
2123  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 ) );
2124  }
2125  else
2126  {
2127  switch ( type )
2128  {
2129  case GEOS_POINT:
2133  createCandidatesOverPoint( x[0], y[0], lPos, angle );
2134  else
2135  createCandidatesAroundPoint( x[0], y[0], lPos, angle );
2136  break;
2137 
2138  case GEOS_LINESTRING:
2141  else if ( mLF->layer()->isCurved() )
2142  createCurvedCandidatesAlongLine( lPos, this, true, pal );
2143  else
2144  createCandidatesAlongLine( lPos, this, true, pal );
2145  break;
2146 
2147  case GEOS_POLYGON:
2148  {
2149  const double labelWidth = getLabelWidth();
2150  const double labelHeight = getLabelHeight();
2151 
2152  const bool allowOutside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementOutsideOfPolygon;
2153  const bool allowInside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementInsideOfPolygon;
2154  //check width/height of bbox is sufficient for label
2155 
2156  if ( ( allowOutside && !allowInside ) || ( mLF->layer()->arrangement() == Qgis::LabelPlacement::OutsidePolygons ) )
2157  {
2158  // only allowed to place outside of polygon
2160  }
2161  else if ( allowOutside && ( std::fabs( xmax - xmin ) < labelWidth ||
2162  std::fabs( ymax - ymin ) < labelHeight ) )
2163  {
2164  //no way label can fit in this polygon -- shortcut and only place label outside
2166  }
2167  else
2168  {
2169  std::size_t created = 0;
2170  if ( allowInside )
2171  {
2172  switch ( mLF->layer()->arrangement() )
2173  {
2175  {
2176  double cx, cy;
2177  getCentroid( cx, cy, mLF->layer()->centroidInside() );
2178  if ( qgsDoubleNear( mLF->distLabel(), 0.0 ) )
2179  created += createCandidateCenteredOverPoint( cx, cy, lPos, angle );
2180  created += createCandidatesAroundPoint( cx, cy, lPos, angle );
2181  break;
2182  }
2184  {
2185  double cx, cy;
2186  getCentroid( cx, cy, mLF->layer()->centroidInside() );
2187  created += createCandidatesOverPoint( cx, cy, lPos, angle );
2188  break;
2189  }
2191  created += createCandidatesAlongLine( lPos, this, false, pal );
2192  break;
2194  created += createCurvedCandidatesAlongLine( lPos, this, false, pal );
2195  break;
2196  default:
2197  created += createCandidatesForPolygon( lPos, this, pal );
2198  break;
2199  }
2200  }
2201 
2202  if ( allowOutside )
2203  {
2204  // add fallback for labels outside the polygon
2206 
2207  if ( created > 0 )
2208  {
2209  // TODO (maybe) increase cost for outside placements (i.e. positions at indices >= created)?
2210  // From my initial testing this doesn't seem necessary
2211  }
2212  }
2213  }
2214  }
2215  }
2216  }
2217 
2218  return lPos;
2219 }
2220 
2221 void FeaturePart::addSizePenalty( std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4] ) const
2222 {
2223  if ( !mGeos )
2224  createGeosGeom();
2225 
2226  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2227  int geomType = GEOSGeomTypeId_r( ctxt, mGeos );
2228 
2229  double sizeCost = 0;
2230  if ( geomType == GEOS_LINESTRING )
2231  {
2232  const double l = length();
2233  if ( l <= 0 )
2234  return; // failed to calculate length
2235  double bbox_length = std::max( bbx[2] - bbx[0], bby[2] - bby[0] );
2236  if ( l >= bbox_length / 4 )
2237  return; // the line is longer than quarter of height or width - don't penalize it
2238 
2239  sizeCost = 1 - ( l / ( bbox_length / 4 ) ); // < 0,1 >
2240  }
2241  else if ( geomType == GEOS_POLYGON )
2242  {
2243  const double a = area();
2244  if ( a <= 0 )
2245  return;
2246  double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
2247  if ( a >= bbox_area / 16 )
2248  return; // covers more than 1/16 of our view - don't penalize it
2249 
2250  sizeCost = 1 - ( a / ( bbox_area / 16 ) ); // < 0, 1 >
2251  }
2252  else
2253  return; // no size penalty for points
2254 
2255 // apply the penalty
2256  for ( std::unique_ptr< LabelPosition > &pos : lPos )
2257  {
2258  pos->setCost( pos->cost() + sizeCost / 100 );
2259  }
2260 }
2261 
2263 {
2264  if ( !nbPoints || !p2->nbPoints )
2265  return false;
2266 
2267  // here we only care if the lines start or end at the other line -- we don't want to test
2268  // touches as that is true for "T" type joins!
2269  const double x1first = x.front();
2270  const double x1last = x.back();
2271  const double x2first = p2->x.front();
2272  const double x2last = p2->x.back();
2273  const double y1first = y.front();
2274  const double y1last = y.back();
2275  const double y2first = p2->y.front();
2276  const double y2last = p2->y.back();
2277 
2278  const bool p2startTouches = ( qgsDoubleNear( x1first, x2first ) && qgsDoubleNear( y1first, y2first ) )
2279  || ( qgsDoubleNear( x1last, x2first ) && qgsDoubleNear( y1last, y2first ) );
2280 
2281  const bool p2endTouches = ( qgsDoubleNear( x1first, x2last ) && qgsDoubleNear( y1first, y2last ) )
2282  || ( qgsDoubleNear( x1last, x2last ) && qgsDoubleNear( y1last, y2last ) );
2283  // only one endpoint can touch, not both
2284  if ( ( !p2startTouches && !p2endTouches ) || ( p2startTouches && p2endTouches ) )
2285  return false;
2286 
2287  // now we know that we have one line endpoint touching only, but there's still a chance
2288  // that the other side of p2 may touch the original line NOT at the other endpoint
2289  // so we need to check that this point doesn't intersect
2290  const double p2otherX = p2startTouches ? x2last : x2first;
2291  const double p2otherY = p2startTouches ? y2last : y2first;
2292 
2293  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
2294 
2295  GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
2296 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
2297  GEOSCoordSeq_setXY_r( geosctxt, coord, 0, p2otherX, p2otherY );
2298 #else
2299  GEOSCoordSeq_setX_r( geosctxt, coord, 0, p2otherX );
2300  GEOSCoordSeq_setY_r( geosctxt, coord, 0, p2otherY );
2301 #endif
2302 
2303  geos::unique_ptr p2OtherEnd( GEOSGeom_createPoint_r( geosctxt, coord ) );
2304  try
2305  {
2306  return ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), p2OtherEnd.get() ) != 1 );
2307  }
2308  catch ( GEOSException &e )
2309  {
2310  qWarning( "GEOS exception: %s", e.what() );
2311  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2312  return false;
2313  }
2314 }
2315 
2317 {
2318  if ( !mGeos )
2319  createGeosGeom();
2320  if ( !other->mGeos )
2321  other->createGeosGeom();
2322 
2323  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2324  try
2325  {
2326  GEOSGeometry *g1 = GEOSGeom_clone_r( ctxt, mGeos );
2327  GEOSGeometry *g2 = GEOSGeom_clone_r( ctxt, other->mGeos );
2328  GEOSGeometry *geoms[2] = { g1, g2 };
2329  geos::unique_ptr g( GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 ) );
2330  geos::unique_ptr gTmp( GEOSLineMerge_r( ctxt, g.get() ) );
2331 
2332  if ( GEOSGeomTypeId_r( ctxt, gTmp.get() ) != GEOS_LINESTRING )
2333  {
2334  // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
2335  return false;
2336  }
2337  invalidateGeos();
2338 
2339  // set up new geometry
2340  mGeos = gTmp.release();
2341  mOwnsGeom = true;
2342 
2343  deleteCoords();
2344  qDeleteAll( mHoles );
2345  mHoles.clear();
2346  extractCoords( mGeos );
2347  return true;
2348  }
2349  catch ( GEOSException &e )
2350  {
2351  qWarning( "GEOS exception: %s", e.what() );
2352  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2353  return false;
2354  }
2355 }
2356 
2358 {
2359  if ( mLF->alwaysShow() )
2360  {
2361  //if feature is set to always show, bump the priority up by orders of magnitude
2362  //so that other feature's labels are unlikely to be placed over the label for this feature
2363  //(negative numbers due to how pal::extract calculates inactive cost)
2364  return -0.2;
2365  }
2366 
2367  return mLF->priority() >= 0 ? mLF->priority() : mLF->layer()->priority();
2368 }
2369 
2371 {
2372  bool result = false;
2373 
2374  switch ( mLF->layer()->upsidedownLabels() )
2375  {
2376  case Qgis::UpsideDownLabelHandling::FlipUpsideDownLabels:
2377  result = true;
2378  break;
2379  case Qgis::UpsideDownLabelHandling::AllowUpsideDownWhenRotationIsDefined:
2380  // upright only dynamic labels
2381  if ( !hasFixedRotation() || ( !hasFixedPosition() && fixedAngle() == 0.0 ) )
2382  {
2383  result = true;
2384  }
2385  break;
2386  case Qgis::UpsideDownLabelHandling::AlwaysAllowUpsideDown:
2387  break;
2388  }
2389  return result;
2390 }
@ FromSymbolBounds
Offset distance applies from rendered symbol bounds.
@ OverPoint
Arranges candidates over a point (or centroid of a polygon), or at a preset offset from the point....
@ AroundPoint
Arranges candidates in a circle around a point (or centroid of a polygon). Applies to point or polygo...
@ Line
Arranges candidates parallel to a generalised line representing the feature or parallel to a polygon'...
@ Free
Arranges candidates scattered throughout a polygon feature. Candidates are rotated to respect the pol...
@ OrderedPositionsAroundPoint
Candidates are placed in predefined positions around a point. Preference is given to positions with g...
@ Horizontal
Arranges horizontal candidates scattered throughout a polygon feature. Applies to polygon layers only...
@ PerimeterCurved
Arranges candidates following the curvature of a polygon's boundary. Applies to polygon layers only.
@ OutsidePolygons
Candidates are placed outside of polygon boundaries. Applies to polygon layers only....
LabelPredefinedPointPosition
Positions for labels when using the Qgis::LabelPlacement::OrderedPositionsAroundPoint placement mode.
Definition: qgis.h:583
@ MiddleLeft
Label on left of point.
@ TopRight
Label on top-right of point.
@ MiddleRight
Label on right of point.
@ TopSlightlyRight
Label on top of point, slightly right of center.
@ TopMiddle
Label directly above point.
@ BottomSlightlyLeft
Label below point, slightly left of center.
@ BottomRight
Label on bottom right of point.
@ BottomLeft
Label on bottom-left of point.
@ BottomSlightlyRight
Label below point, slightly right of center.
@ TopLeft
Label on top-left of point.
@ BottomMiddle
Label directly below point.
@ TopSlightlyLeft
Label on top of point, slightly left of center.
const QgsCurve * exteriorRing() const SIP_HOLDGIL
Returns the curve polygon's exterior ring.
static double normalizedAngle(double angle) SIP_HOLDGIL
Ensures that an angle is in the range 0 <= angle < 2 pi.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
static std::unique_ptr< QgsAbstractGeometry > fromGeos(const GEOSGeometry *geos)
Create a geometry from a GEOSGeometry.
Definition: qgsgeos.cpp:1349
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:3369
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...
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.
QVector< Qgis::LabelPredefinedPointPosition > predefinedPositionOrder() const
Returns the priority ordered list of predefined positions for label candidates.
QgsLabeling::PolygonPlacementFlags polygonPlacementFlags() const
Returns the polygon placement flags, which dictate how polygon labels can be placed.
QgsPointXY positionOffset() const
Applies only to "offset from point" placement strategy.
bool hasFixedQuadrant() const
Returns whether the quadrant for the label is fixed.
bool hasFixedAngle() const
Whether the label should use a fixed angle instead of using angle from automatic placement.
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.
QgsLabelLineSettings::AnchorTextPoint lineAnchorTextPoint() const
Returns the line anchor text point, which dictates which part of the label text should be placed at t...
const GEOSPreparedGeometry * permissibleZonePrepared() const
Returns a GEOS prepared geometry representing the label's permissibleZone().
Qgis::LabelOffsetType offsetType() const
Returns the offset type, which determines how offsets and distance to label behaves.
QgsPointXY fixedPosition() const
Coordinates of the fixed position (relevant only if hasFixedPosition() returns true)
@ Strict
Line anchor is a strict placement, and other placements are not permitted.
@ HintOnly
Line anchor is a hint for preferred placement only, but other placements close to the hint are permit...
AnchorTextPoint
Anchor point of label text.
@ EndOfText
Anchor using end of text.
@ StartOfText
Anchor using start of text.
@ CenterOfText
Anchor using center of text.
@ FollowPlacement
Automatically set the anchor point based on the lineAnchorPercent() value. Values <25% will use the s...
Contains constants and enums relating to labeling.
Definition: qgslabeling.h:32
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:45
double length() const override SIP_HOLDGIL
Returns the planar, 2-dimensional length of the geometry.
void visitPointsByRegularDistance(double distance, const std::function< bool(double x, double y, double z, double m, double startSegmentX, double startSegmentY, double startSegmentZ, double startSegmentM, double endSegmentX, double endSegmentY, double endSegmentZ, double endSegmentM) > &visitPoint) const
Visits regular points along the linestring, spaced by distance.
The QgsMargins class defines the four margins of a rectangle.
Definition: qgsmargins.h:38
double top() const
Returns the top margin.
Definition: qgsmargins.h:78
double right() const
Returns the right margin.
Definition: qgsmargins.h:84
double bottom() const
Returns the bottom margin.
Definition: qgsmargins.h:90
double left() const
Returns the left margin.
Definition: qgsmargins.h:72
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::MessageLevel::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
A class to represent a 2D point.
Definition: qgspointxy.h:59
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
Polygon geometry type.
Definition: qgspolygon.h:34
Contains precalculated properties regarding text metrics for text to be renderered at a later stage.
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:1913
bool hasFixedRotation() const
Returns true if the feature's label has a fixed rotation.
Definition: feature.h:283
double getLabelHeight(double angle=0.0) const
Returns the height of the label, optionally taking an angle into account.
Definition: feature.h:274
QList< FeaturePart * > mHoles
Definition: feature.h:350
double getLabelDistance() const
Returns the distance from the anchor point to the label.
Definition: feature.h:280
~FeaturePart() override
Deletes the feature.
Definition: feature.cpp:83
bool hasFixedPosition() const
Returns true if the feature's label has a fixed position.
Definition: feature.h:289
std::size_t createCandidatesForPolygon(std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal)
Generate candidates for polygon features.
Definition: feature.cpp:1670
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:855
bool hasSameLabelFeatureAs(FeaturePart *part) const
Tests whether this feature part belongs to the same QgsLabelFeature as another feature part.
Definition: feature.cpp:215
double fixedAngle() const
Returns the fixed angle for the feature's label.
Definition: feature.h:286
std::size_t maximumLineCandidates() const
Returns the maximum number of line candidates to generate for this feature.
Definition: feature.cpp: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:2316
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:1351
bool onlyShowUprightLabels() const
Returns true if feature's label must be displayed upright.
Definition: feature.cpp:2370
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:349
double getLabelWidth(double angle=0.0) const
Returns the width of the label, optionally taking an angle into account.
Definition: feature.h:268
std::unique_ptr< LabelPosition > curvedPlacementAtOffset(PointSet *mapShape, const std::vector< double > &pathDistances, QgsTextRendererUtils::LabelLineDirection direction, double distance, bool &labeledLineSegmentIsRightToLeft, bool applyAngleConstraints, bool uprightOnly)
Returns the label position for a curved label at a specific offset along a path.
Definition: feature.cpp:1314
std::vector< std::unique_ptr< LabelPosition > > createCandidates(Pal *pal)
Generates a list of candidate positions for labels for this feature.
Definition: feature.cpp:2116
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:2262
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:1108
void addSizePenalty(std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4]) const
Increases the cost of the label candidates for this feature, based on the size of the feature.
Definition: feature.cpp:2221
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:2357
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:63
QString name() const
Returns the layer's name.
Definition: layer.h:162
std::size_t maximumPolygonLabelCandidates() const
Returns the maximum number of polygon label candidates to generate for features in this layer.
Definition: layer.h:139
Pal * mPal
Definition: layer.h:323
int connectedFeatureId(QgsFeatureId featureId) const
Returns the connected feature ID for a label feature ID, which is unique for all features which have ...
Definition: layer.cpp:361
Qgis::LabelPlacement arrangement() const
Returns the layer's arrangement policy.
Definition: layer.h:168
std::size_t maximumPointLabelCandidates() const
Returns the maximum number of point label candidates to generate for features in this layer.
Definition: layer.h:97
Qgis::UpsideDownLabelHandling upsidedownLabels() const
Returns how upside down labels are handled within the layer.
Definition: layer.h:269
bool centroidInside() const
Returns whether labels placed at the centroid of features within the layer are forced to be placed in...
Definition: layer.h:285
bool isCurved() const
Returns true if the layer has curved labels.
Definition: layer.h:173
double priority() const
Returns the layer's priority, between 0 and 1.
Definition: layer.h:243
std::size_t maximumLineLabelCandidates() const
Returns the maximum number of line label candidates to generate for features in this layer.
Definition: layer.h:118
Main Pal labeling class.
Definition: pal.h:80
double maximumLineCandidatesPerMapUnit() const
Returns the maximum number of line label candidate positions per map unit.
Definition: pal.h:170
double maximumPolygonCandidatesPerMapUnitSquared() const
Returns the maximum number of polygon label candidate positions per map unit squared.
Definition: pal.h:184
The underlying raw pal geometry class.
Definition: pointset.h:77
geos::unique_ptr interpolatePoint(double distance) const
Returns a GEOS geometry representing the point interpolated on the shape by distance.
Definition: pointset.cpp:1039
std::unique_ptr< PointSet > clone() const
Returns a copy of the point set.
Definition: pointset.cpp:261
double lineLocatePoint(const GEOSGeometry *point) const
Returns the distance along the geometry closest to the specified GEOS point.
Definition: pointset.cpp:1057
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:1085
void deleteCoords()
Definition: pointset.cpp:228
double ymax
Definition: pointset.h:261
double ymin
Definition: pointset.h:260
double area() const
Returns area of polygon geometry.
Definition: pointset.cpp:1111
bool isClosed() const
Returns true if pointset is closed.
Definition: pointset.cpp:1138
PointSet * holeOf
Definition: pointset.h:241
void createGeosGeom() const
Definition: pointset.cpp:100
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py) const
Gets a point a set distance along a line geometry.
Definition: pointset.cpp:1000
std::vector< double > y
Definition: pointset.h:231
void getCentroid(double &px, double &py, bool forceInside=false) const
Definition: pointset.cpp:932
std::vector< double > x
Definition: pointset.h:230
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:150
GEOSGeometry * mGeos
Definition: pointset.h:234
double xmin
Definition: pointset.h:258
const GEOSGeometry * geos() const
Returns the point set's GEOS geometry.
Definition: pointset.cpp:1077
void invalidateGeos() const
Definition: pointset.cpp:162
friend class FeaturePart
Definition: pointset.h:78
double xmax
Definition: pointset.h:259
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
Definition: pointset.cpp:266
std::tuple< std::vector< double >, double > edgeDistances() const
Returns a vector of edge distances as well as its total length.
Definition: pointset.cpp:1172
PointSet * parent
Definition: pointset.h:242
bool mOwnsGeom
Definition: pointset.h:235
static QLinkedList< PointSet * > splitPolygons(PointSet *inputShape, double labelWidth, double labelHeight)
Split a polygon using some random logic into some other polygons.
Definition: pointset.cpp:297
void createCandidateAtOrderedPositionOverPoint(double &labelX, double &labelY, LabelPosition::Quadrant &quadrant, double x, double y, double labelWidth, double labelHeight, Qgis::LabelPredefinedPointPosition position, double distanceToLabel, const QgsMargins &visualMargin, double symbolWidthOffset, double symbolHeightOffset, double angle)
Definition: feature.cpp: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:2260
qint64 QgsFeatureId
64 bit feature ids negative numbers are used for uncommitted/newly added features
Definition: qgsfeatureid.h:28
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
Represents the minimum area, oriented bounding box surrounding a convex hull.
Definition: pointset.h:60