QGIS API Documentation  3.8.0-Zanzibar (11aff65)
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 "qgsgeometry.h"
31 #include "pal.h"
32 #include "layer.h"
33 #include "feature.h"
34 #include "geomfunction.h"
35 #include "labelposition.h"
36 #include "pointset.h"
37 #include "util.h"
38 #include "qgis.h"
39 #include "qgsgeos.h"
40 #include "qgsmessagelog.h"
41 #include "costcalculator.h"
42 #include "qgsgeometryutils.h"
43 #include <QLinkedList>
44 #include <cmath>
45 #include <cfloat>
46 
47 using namespace pal;
48 
49 FeaturePart::FeaturePart( QgsLabelFeature *feat, const GEOSGeometry *geom )
50  : mLF( feat )
51 {
52  // we'll remove const, but we won't modify that geometry
53  mGeos = const_cast<GEOSGeometry *>( geom );
54  mOwnsGeom = false; // geometry is owned by Feature class
55 
56  extractCoords( geom );
57 
58  holeOf = nullptr;
59  for ( int i = 0; i < mHoles.count(); i++ )
60  {
61  mHoles.at( i )->holeOf = this;
62  }
63 
64 }
65 
67  : PointSet( other )
68  , mLF( other.mLF )
69 {
70  for ( const FeaturePart *hole : qgis::as_const( other.mHoles ) )
71  {
72  mHoles << new FeaturePart( *hole );
73  mHoles.last()->holeOf = this;
74  }
75 }
76 
78 {
79  // X and Y are deleted in PointSet
80 
81  qDeleteAll( mHoles );
82  mHoles.clear();
83 }
84 
85 void FeaturePart::extractCoords( const GEOSGeometry *geom )
86 {
87  const GEOSCoordSequence *coordSeq = nullptr;
88  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
89 
90  type = GEOSGeomTypeId_r( geosctxt, geom );
91 
92  if ( type == GEOS_POLYGON )
93  {
94  if ( GEOSGetNumInteriorRings_r( geosctxt, geom ) > 0 )
95  {
96  int numHoles = GEOSGetNumInteriorRings_r( geosctxt, geom );
97 
98  for ( int i = 0; i < numHoles; ++i )
99  {
100  const GEOSGeometry *interior = GEOSGetInteriorRingN_r( geosctxt, geom, i );
101  FeaturePart *hole = new FeaturePart( mLF, interior );
102  hole->holeOf = nullptr;
103  // possibly not needed. it's not done for the exterior ring, so I'm not sure
104  // why it's just done here...
105  GeomFunction::reorderPolygon( hole->nbPoints, hole->x, hole->y );
106 
107  mHoles << hole;
108  }
109  }
110 
111  // use exterior ring for the extraction of coordinates that follows
112  geom = GEOSGetExteriorRing_r( geosctxt, geom );
113  }
114  else
115  {
116  qDeleteAll( mHoles );
117  mHoles.clear();
118  }
119 
120  // find out number of points
121  nbPoints = GEOSGetNumCoordinates_r( geosctxt, geom );
122  coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, geom );
123 
124  // initialize bounding box
125  xmin = ymin = std::numeric_limits<double>::max();
126  xmax = ymax = std::numeric_limits<double>::lowest();
127 
128  // initialize coordinate arrays
129  deleteCoords();
130  x = new double[nbPoints];
131  y = new double[nbPoints];
132 
133  for ( int i = 0; i < nbPoints; ++i )
134  {
135  GEOSCoordSeq_getX_r( geosctxt, coordSeq, i, &x[i] );
136  GEOSCoordSeq_getY_r( geosctxt, coordSeq, i, &y[i] );
137 
138  xmax = x[i] > xmax ? x[i] : xmax;
139  xmin = x[i] < xmin ? x[i] : xmin;
140 
141  ymax = y[i] > ymax ? y[i] : ymax;
142  ymin = y[i] < ymin ? y[i] : ymin;
143  }
144 }
145 
147 {
148  return mLF->layer();
149 }
150 
152 {
153  return mLF->id();
154 }
155 
157 {
158  if ( !part )
159  return false;
160 
161  if ( mLF->layer()->name() != part->layer()->name() )
162  return false;
163 
164  if ( mLF->id() == part->featureId() )
165  return true;
166 
167  // any part of joined features are also treated as having the same label feature
168  int connectedFeatureId = mLF->layer()->connectedFeatureId( mLF->id() );
169  return connectedFeatureId >= 0 && connectedFeatureId == mLF->layer()->connectedFeatureId( part->featureId() );
170 }
171 
172 LabelPosition::Quadrant FeaturePart::quadrantFromOffset() const
173 {
174  QPointF quadOffset = mLF->quadOffset();
175  qreal quadOffsetX = quadOffset.x(), quadOffsetY = quadOffset.y();
176 
177  if ( quadOffsetX < 0 )
178  {
179  if ( quadOffsetY < 0 )
180  {
182  }
183  else if ( quadOffsetY > 0 )
184  {
186  }
187  else
188  {
190  }
191  }
192  else if ( quadOffsetX > 0 )
193  {
194  if ( quadOffsetY < 0 )
195  {
197  }
198  else if ( quadOffsetY > 0 )
199  {
201  }
202  else
203  {
205  }
206  }
207  else
208  {
209  if ( quadOffsetY < 0 )
210  {
212  }
213  else if ( quadOffsetY > 0 )
214  {
216  }
217  else
218  {
220  }
221  }
222 }
223 
224 int FeaturePart::createCandidatesOverPoint( double x, double y, QList< LabelPosition *> &lPos, double angle )
225 {
226  int nbp = 1;
227 
228  // get from feature
229  double labelW = getLabelWidth();
230  double labelH = getLabelHeight();
231 
232  double cost = 0.0001;
233  int id = 0;
234 
235  double xdiff = -labelW / 2.0;
236  double ydiff = -labelH / 2.0;
237 
238  if ( !qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
239  {
240  xdiff += labelW / 2.0 * mLF->quadOffset().x();
241  }
242  if ( !qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
243  {
244  ydiff += labelH / 2.0 * mLF->quadOffset().y();
245  }
246 
247  if ( ! mLF->hasFixedPosition() )
248  {
249  if ( !qgsDoubleNear( angle, 0.0 ) )
250  {
251  double xd = xdiff * std::cos( angle ) - ydiff * std::sin( angle );
252  double yd = xdiff * std::sin( angle ) + ydiff * std::cos( angle );
253  xdiff = xd;
254  ydiff = yd;
255  }
256  }
257 
259  {
260  //if in "around point" placement mode, then we use the label distance to determine
261  //the label's offset
262  if ( qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
263  {
264  ydiff += mLF->quadOffset().y() * mLF->distLabel();
265  }
266  else if ( qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
267  {
268  xdiff += mLF->quadOffset().x() * mLF->distLabel();
269  }
270  else
271  {
272  xdiff += mLF->quadOffset().x() * M_SQRT1_2 * mLF->distLabel();
273  ydiff += mLF->quadOffset().y() * M_SQRT1_2 * mLF->distLabel();
274  }
275  }
276  else
277  {
278  if ( !qgsDoubleNear( mLF->positionOffset().x(), 0.0 ) )
279  {
280  xdiff += mLF->positionOffset().x();
281  }
282  if ( !qgsDoubleNear( mLF->positionOffset().y(), 0.0 ) )
283  {
284  ydiff += mLF->positionOffset().y();
285  }
286  }
287 
288  double lx = x + xdiff;
289  double ly = y + ydiff;
290 
291  if ( mLF->permissibleZonePrepared() )
292  {
293  if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), lx, ly, labelW, labelH, angle ) )
294  {
295  return 0;
296  }
297  }
298 
299  lPos << new LabelPosition( id, lx, ly, labelW, labelH, angle, cost, this, false, quadrantFromOffset() );
300  return nbp;
301 }
302 
303 int FeaturePart::createCandidatesAtOrderedPositionsOverPoint( double x, double y, QList<LabelPosition *> &lPos, double angle )
304 {
305  QVector< QgsPalLayerSettings::PredefinedPointPosition > positions = mLF->predefinedPositionOrder();
306  double labelWidth = getLabelWidth();
307  double labelHeight = getLabelHeight();
308  double distanceToLabel = getLabelDistance();
309  const QgsMargins &visualMargin = mLF->visualMargin();
310 
311  double symbolWidthOffset = ( mLF->offsetType() == QgsPalLayerSettings::FromSymbolBounds ? mLF->symbolSize().width() / 2.0 : 0.0 );
312  double symbolHeightOffset = ( mLF->offsetType() == QgsPalLayerSettings::FromSymbolBounds ? mLF->symbolSize().height() / 2.0 : 0.0 );
313 
314  double cost = 0.0001;
315  int i = 0;
316  const auto constPositions = positions;
317  for ( QgsPalLayerSettings::PredefinedPointPosition position : constPositions )
318  {
319  double alpha = 0.0;
320  double deltaX = 0;
321  double deltaY = 0;
323  switch ( position )
324  {
327  alpha = 3 * M_PI_4;
328  deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
329  deltaY = -visualMargin.bottom() + symbolHeightOffset;
330  break;
331 
333  quadrant = LabelPosition::QuadrantAboveRight; //right quadrant, so labels are left-aligned
334  alpha = M_PI_2;
335  deltaX = -labelWidth / 4.0 - visualMargin.left();
336  deltaY = -visualMargin.bottom() + symbolHeightOffset;
337  break;
338 
340  quadrant = LabelPosition::QuadrantAbove;
341  alpha = M_PI_2;
342  deltaX = -labelWidth / 2.0;
343  deltaY = -visualMargin.bottom() + symbolHeightOffset;
344  break;
345 
347  quadrant = LabelPosition::QuadrantAboveLeft; //left quadrant, so labels are right-aligned
348  alpha = M_PI_2;
349  deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
350  deltaY = -visualMargin.bottom() + symbolHeightOffset;
351  break;
352 
355  alpha = M_PI_4;
356  deltaX = - visualMargin.left() + symbolWidthOffset;
357  deltaY = -visualMargin.bottom() + symbolHeightOffset;
358  break;
359 
361  quadrant = LabelPosition::QuadrantLeft;
362  alpha = M_PI;
363  deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
364  deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
365  break;
366 
368  quadrant = LabelPosition::QuadrantRight;
369  alpha = 0.0;
370  deltaX = -visualMargin.left() + symbolWidthOffset;
371  deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
372  break;
373 
376  alpha = 5 * M_PI_4;
377  deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
378  deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
379  break;
380 
382  quadrant = LabelPosition::QuadrantBelowRight; //right quadrant, so labels are left-aligned
383  alpha = 3 * M_PI_2;
384  deltaX = -labelWidth / 4.0 - visualMargin.left();
385  deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
386  break;
387 
389  quadrant = LabelPosition::QuadrantBelow;
390  alpha = 3 * M_PI_2;
391  deltaX = -labelWidth / 2.0;
392  deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
393  break;
394 
396  quadrant = LabelPosition::QuadrantBelowLeft; //left quadrant, so labels are right-aligned
397  alpha = 3 * M_PI_2;
398  deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
399  deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
400  break;
401 
404  alpha = 7 * M_PI_4;
405  deltaX = -visualMargin.left() + symbolWidthOffset;
406  deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
407  break;
408  }
409 
410  //have bearing, distance - calculate reference point
411  double referenceX = std::cos( alpha ) * distanceToLabel + x;
412  double referenceY = std::sin( alpha ) * distanceToLabel + y;
413 
414  double labelX = referenceX + deltaX;
415  double labelY = referenceY + deltaY;
416 
417  if ( ! mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
418  {
419  lPos << new LabelPosition( i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant );
420  //TODO - tweak
421  cost += 0.001;
422  }
423 
424  ++i;
425  }
426 
427  return lPos.count();
428 }
429 
430 int FeaturePart::createCandidatesAroundPoint( double x, double y, QList< LabelPosition * > &lPos, double angle )
431 {
432  double labelWidth = getLabelWidth();
433  double labelHeight = getLabelHeight();
434  double distanceToLabel = getLabelDistance();
435 
436  int numberCandidates = mLF->layer()->pal->point_p;
437 
438  int icost = 0;
439  int inc = 2;
440 
441  double candidateAngleIncrement = 2 * M_PI / numberCandidates; /* angle bw 2 pos */
442 
443  /* various angles */
444  double a90 = M_PI_2;
445  double a180 = M_PI;
446  double a270 = a180 + a90;
447  double a360 = 2 * M_PI;
448 
449  double gamma1, gamma2;
450 
451  if ( distanceToLabel > 0 )
452  {
453  gamma1 = std::atan2( labelHeight / 2, distanceToLabel + labelWidth / 2 );
454  gamma2 = std::atan2( labelWidth / 2, distanceToLabel + labelHeight / 2 );
455  }
456  else
457  {
458  gamma1 = gamma2 = a90 / 3.0;
459  }
460 
461  if ( gamma1 > a90 / 3.0 )
462  gamma1 = a90 / 3.0;
463 
464  if ( gamma2 > a90 / 3.0 )
465  gamma2 = a90 / 3.0;
466 
467  QList< LabelPosition * > candidates;
468 
469  int i;
470  double angleToCandidate;
471  for ( i = 0, angleToCandidate = M_PI_4; i < numberCandidates; i++, angleToCandidate += candidateAngleIncrement )
472  {
473  double labelX = x;
474  double labelY = y;
475 
476  if ( angleToCandidate > a360 )
477  angleToCandidate -= a360;
478 
480 
481  if ( angleToCandidate < gamma1 || angleToCandidate > a360 - gamma1 ) // on the right
482  {
483  labelX += distanceToLabel;
484  double iota = ( angleToCandidate + gamma1 );
485  if ( iota > a360 - gamma1 )
486  iota -= a360;
487 
488  //ly += -yrm/2.0 + tan(alpha)*(distlabel + xrm/2);
489  labelY += -labelHeight + labelHeight * iota / ( 2 * gamma1 );
490 
491  quadrant = LabelPosition::QuadrantRight;
492  }
493  else if ( angleToCandidate < a90 - gamma2 ) // top-right
494  {
495  labelX += distanceToLabel * std::cos( angleToCandidate );
496  labelY += distanceToLabel * std::sin( angleToCandidate );
498  }
499  else if ( angleToCandidate < a90 + gamma2 ) // top
500  {
501  //lx += -xrm/2.0 - tan(alpha+a90)*(distlabel + yrm/2);
502  labelX += -labelWidth * ( angleToCandidate - a90 + gamma2 ) / ( 2 * gamma2 );
503  labelY += distanceToLabel;
504  quadrant = LabelPosition::QuadrantAbove;
505  }
506  else if ( angleToCandidate < a180 - gamma1 ) // top left
507  {
508  labelX += distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
509  labelY += distanceToLabel * std::sin( angleToCandidate );
511  }
512  else if ( angleToCandidate < a180 + gamma1 ) // left
513  {
514  labelX += -distanceToLabel - labelWidth;
515  //ly += -yrm/2.0 - tan(alpha)*(distlabel + xrm/2);
516  labelY += - ( angleToCandidate - a180 + gamma1 ) * labelHeight / ( 2 * gamma1 );
517  quadrant = LabelPosition::QuadrantLeft;
518  }
519  else if ( angleToCandidate < a270 - gamma2 ) // down - left
520  {
521  labelX += distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
522  labelY += distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
524  }
525  else if ( angleToCandidate < a270 + gamma2 ) // down
526  {
527  labelY += -distanceToLabel - labelHeight;
528  //lx += -xrm/2.0 + tan(alpha+a90)*(distlabel + yrm/2);
529  labelX += -labelWidth + ( angleToCandidate - a270 + gamma2 ) * labelWidth / ( 2 * gamma2 );
530  quadrant = LabelPosition::QuadrantBelow;
531  }
532  else if ( angleToCandidate < a360 ) // down - right
533  {
534  labelX += distanceToLabel * std::cos( angleToCandidate );
535  labelY += distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
537  }
538 
539  double cost;
540 
541  if ( numberCandidates == 1 )
542  cost = 0.0001;
543  else
544  cost = 0.0001 + 0.0020 * double( icost ) / double( numberCandidates - 1 );
545 
546 
547  if ( mLF->permissibleZonePrepared() )
548  {
549  if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
550  {
551  continue;
552  }
553  }
554 
555  candidates << new LabelPosition( i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant );
556 
557  icost += inc;
558 
559  if ( icost == numberCandidates )
560  {
561  icost = numberCandidates - 1;
562  inc = -2;
563  }
564  else if ( icost > numberCandidates )
565  {
566  icost = numberCandidates - 2;
567  inc = -2;
568  }
569 
570  }
571 
572  if ( !candidates.isEmpty() )
573  {
574  for ( int i = 0; i < candidates.count(); ++i )
575  {
576  lPos << candidates.at( i );
577  }
578  }
579 
580  return candidates.count();
581 }
582 
583 int FeaturePart::createCandidatesAlongLine( QList< LabelPosition * > &lPos, PointSet *mapShape )
584 {
585  //prefer to label along straightish segments:
586  int candidates = createCandidatesAlongLineNearStraightSegments( lPos, mapShape );
587 
588  if ( candidates < mLF->layer()->pal->line_p )
589  {
590  // but not enough candidates yet, so fallback to labeling near whole line's midpoint
591  candidates = createCandidatesAlongLineNearMidpoint( lPos, mapShape, candidates > 0 ? 0.01 : 0.0 );
592  }
593  return candidates;
594 }
595 
596 int FeaturePart::createCandidatesAlongLineNearStraightSegments( QList<LabelPosition *> &lPos, PointSet *mapShape )
597 {
598  double labelWidth = getLabelWidth();
599  double labelHeight = getLabelHeight();
600  double distanceLineToLabel = getLabelDistance();
601  LineArrangementFlags flags = mLF->arrangementFlags();
602  if ( flags == 0 )
603  flags = FLAG_ON_LINE; // default flag
604 
605  // 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
606  QVector< int > extremeAngleNodes;
607  PointSet *line = mapShape;
608  int numberNodes = line->nbPoints;
609  double *x = line->x;
610  double *y = line->y;
611 
612  // closed line? if so, we need to handle the final node angle
613  bool closedLine = qgsDoubleNear( x[0], x[ numberNodes - 1] ) && qgsDoubleNear( y[0], y[numberNodes - 1 ] );
614  for ( int i = 1; i <= numberNodes - ( closedLine ? 1 : 2 ); ++i )
615  {
616  double x1 = x[i - 1];
617  double x2 = x[i];
618  double x3 = x[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
619  double y1 = y[i - 1];
620  double y2 = y[i];
621  double y3 = y[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
622  if ( qgsDoubleNear( y2, y3 ) && qgsDoubleNear( x2, x3 ) )
623  continue;
624  if ( qgsDoubleNear( y1, y2 ) && qgsDoubleNear( x1, x2 ) )
625  continue;
626  double vertexAngle = M_PI - ( std::atan2( y3 - y2, x3 - x2 ) - std::atan2( y2 - y1, x2 - x1 ) );
627  vertexAngle = QgsGeometryUtils::normalizedAngle( vertexAngle );
628 
629  // extreme angles form more than 45 degree angle at a node - these are the ones we don't want labels to cross
630  if ( vertexAngle < M_PI * 135.0 / 180.0 || vertexAngle > M_PI * 225.0 / 180.0 )
631  extremeAngleNodes << i;
632  }
633  extremeAngleNodes << numberNodes - 1;
634 
635  if ( extremeAngleNodes.isEmpty() )
636  {
637  // no extreme angles - createCandidatesAlongLineNearMidpoint will be more appropriate
638  return 0;
639  }
640 
641  // calculate lengths of segments, and work out longest straight-ish segment
642  double *segmentLengths = new double[ numberNodes - 1 ]; // segments lengths distance bw pt[i] && pt[i+1]
643  double *distanceToSegment = new double[ numberNodes ]; // absolute distance bw pt[0] and pt[i] along the line
644  double totalLineLength = 0.0;
645  QVector< double > straightSegmentLengths;
646  QVector< double > straightSegmentAngles;
647  straightSegmentLengths.reserve( extremeAngleNodes.size() + 1 );
648  straightSegmentAngles.reserve( extremeAngleNodes.size() + 1 );
649  double currentStraightSegmentLength = 0;
650  double longestSegmentLength = 0;
651  int segmentIndex = 0;
652  double segmentStartX = x[0];
653  double segmentStartY = y[0];
654  for ( int i = 0; i < numberNodes - 1; i++ )
655  {
656  if ( i == 0 )
657  distanceToSegment[i] = 0;
658  else
659  distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
660 
661  segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
662  totalLineLength += segmentLengths[i];
663  if ( extremeAngleNodes.contains( i ) )
664  {
665  // at an extreme angle node, so reset counters
666  straightSegmentLengths << currentStraightSegmentLength;
667  straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[i] - segmentStartY, x[i] - segmentStartX ) );
668  longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
669  segmentIndex++;
670  currentStraightSegmentLength = 0;
671  segmentStartX = x[i];
672  segmentStartY = y[i];
673  }
674  currentStraightSegmentLength += segmentLengths[i];
675  }
676  distanceToSegment[line->nbPoints - 1] = totalLineLength;
677  straightSegmentLengths << currentStraightSegmentLength;
678  straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[numberNodes - 1] - segmentStartY, x[numberNodes - 1] - segmentStartX ) );
679  longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
680  double middleOfLine = totalLineLength / 2.0;
681 
682  if ( totalLineLength < labelWidth )
683  {
684  delete[] segmentLengths;
685  delete[] distanceToSegment;
686  return 0; //createCandidatesAlongLineNearMidpoint will be more appropriate
687  }
688 
689  double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
690  lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / mLF->layer()->pal->line_p );
691 
692  double distanceToEndOfSegment = 0.0;
693  int lastNodeInSegment = 0;
694  // finally, loop through all these straight segments. For each we create candidates along the straight segment.
695  for ( int i = 0; i < straightSegmentLengths.count(); ++i )
696  {
697  currentStraightSegmentLength = straightSegmentLengths.at( i );
698  double currentSegmentAngle = straightSegmentAngles.at( i );
699  lastNodeInSegment = extremeAngleNodes.at( i );
700  double distanceToStartOfSegment = distanceToEndOfSegment;
701  distanceToEndOfSegment = distanceToSegment[ lastNodeInSegment ];
702  double distanceToCenterOfSegment = 0.5 * ( distanceToEndOfSegment + distanceToStartOfSegment );
703 
704  if ( currentStraightSegmentLength < labelWidth )
705  // can't fit a label on here
706  continue;
707 
708  double currentDistanceAlongLine = distanceToStartOfSegment;
709  double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
710  double candidateLength = 0.0;
711  double cost = 0.0;
712  double angle = 0.0;
713  double beta = 0.0;
714 
715  //calculate some cost penalties
716  double segmentCost = 1.0 - ( distanceToEndOfSegment - distanceToStartOfSegment ) / longestSegmentLength; // 0 -> 1 (lower for longer segments)
717  double segmentAngleCost = 1 - std::fabs( std::fmod( currentSegmentAngle, M_PI ) - M_PI_2 ) / M_PI_2; // 0 -> 1, lower for more horizontal segments
718 
719  while ( currentDistanceAlongLine + labelWidth < distanceToEndOfSegment )
720  {
721  // calculate positions along linestring corresponding to start and end of current label candidate
722  line->getPointByDistance( segmentLengths, distanceToSegment, currentDistanceAlongLine, &candidateStartX, &candidateStartY );
723  line->getPointByDistance( segmentLengths, distanceToSegment, currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
724 
725  candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
726 
727 
728  // LOTS OF DIFFERENT COSTS TO BALANCE HERE - feel free to tweak these, but please add a unit test
729  // which covers the situation you are adjusting for (e.g., "given equal length lines, choose the more horizontal line")
730 
731  cost = candidateLength / labelWidth;
732  if ( cost > 0.98 )
733  cost = 0.0001;
734  else
735  {
736  // jaggy line has a greater cost
737  cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
738  }
739 
740  // penalize positions which are further from the straight segments's midpoint
741  double labelCenter = currentDistanceAlongLine + labelWidth / 2.0;
742  double costCenter = 2 * std::fabs( labelCenter - distanceToCenterOfSegment ) / ( distanceToEndOfSegment - distanceToStartOfSegment ); // 0 -> 1
743  cost += costCenter * 0.0005; // < 0, 0.0005 >
744 
745  if ( !closedLine )
746  {
747  // penalize positions which are further from absolute center of whole linestring
748  // this only applies to non closed linestrings, since the middle of a closed linestring is effectively arbitrary
749  // and irrelevant to labeling
750  double costLineCenter = 2 * std::fabs( labelCenter - middleOfLine ) / totalLineLength; // 0 -> 1
751  cost += costLineCenter * 0.0005; // < 0, 0.0005 >
752  }
753 
754  cost += segmentCost * 0.0005; // prefer labels on longer straight segments
755  cost += segmentAngleCost * 0.0001; // prefer more horizontal segments, but this is less important than length considerations
756 
757  if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
758  {
759  angle = 0.0;
760  }
761  else
762  angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
763 
764  beta = angle + M_PI_2;
765 
767  {
768  // find out whether the line direction for this candidate is from right to left
769  bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
770  // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
771  bool reversed = ( ( flags & FLAG_MAP_ORIENTATION ) ? isRightToLeft : false );
772  bool aboveLine = ( !reversed && ( flags & FLAG_ABOVE_LINE ) ) || ( reversed && ( flags & FLAG_BELOW_LINE ) );
773  bool belowLine = ( !reversed && ( flags & FLAG_BELOW_LINE ) ) || ( reversed && ( flags & FLAG_ABOVE_LINE ) );
774 
775  if ( belowLine )
776  {
777  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
778  {
779  const double candidateCost = cost + ( reversed ? 0 : 0.001 );
780  lPos.append( new LabelPosition( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
781  }
782  }
783  if ( aboveLine )
784  {
785  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
786  {
787  const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
788  lPos.append( new LabelPosition( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
789  }
790  }
791  if ( flags & FLAG_ON_LINE )
792  {
793  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
794  {
795  const double candidateCost = cost + 0.002;
796  lPos.append( new LabelPosition( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
797  }
798  }
799  }
801  {
802  lPos.append( new LabelPosition( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this ) ); // Line
803  }
804  else
805  {
806  // an invalid arrangement?
807  }
808 
809  currentDistanceAlongLine += lineStepDistance;
810  }
811  }
812 
813  delete[] segmentLengths;
814  delete[] distanceToSegment;
815  return lPos.size();
816 }
817 
818 int FeaturePart::createCandidatesAlongLineNearMidpoint( QList<LabelPosition *> &lPos, PointSet *mapShape, double initialCost )
819 {
820  double distanceLineToLabel = getLabelDistance();
821 
822  double labelWidth = getLabelWidth();
823  double labelHeight = getLabelHeight();
824 
825  double angle;
826  double cost;
827 
828  LineArrangementFlags flags = mLF->arrangementFlags();
829  if ( flags == 0 )
830  flags = FLAG_ON_LINE; // default flag
831 
832  QList<LabelPosition *> positions;
833 
834  PointSet *line = mapShape;
835  int nbPoints = line->nbPoints;
836  double *x = line->x;
837  double *y = line->y;
838 
839  double *segmentLengths = new double[nbPoints - 1]; // segments lengths distance bw pt[i] && pt[i+1]
840  double *distanceToSegment = new double[nbPoints]; // absolute distance bw pt[0] and pt[i] along the line
841 
842  double totalLineLength = 0.0; // line length
843  for ( int i = 0; i < line->nbPoints - 1; i++ )
844  {
845  if ( i == 0 )
846  distanceToSegment[i] = 0;
847  else
848  distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
849 
850  segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
851  totalLineLength += segmentLengths[i];
852  }
853  distanceToSegment[line->nbPoints - 1] = totalLineLength;
854 
855  double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
856  double currentDistanceAlongLine = 0;
857 
858  if ( totalLineLength > labelWidth )
859  {
860  lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / mLF->layer()->pal->line_p );
861  }
862  else if ( !line->isClosed() ) // line length < label width => centering label position
863  {
864  currentDistanceAlongLine = - ( labelWidth - totalLineLength ) / 2.0;
865  lineStepDistance = -1;
866  totalLineLength = labelWidth;
867  }
868  else
869  {
870  // closed line, not long enough for label => no candidates!
871  currentDistanceAlongLine = std::numeric_limits< double >::max();
872  }
873 
874  double candidateLength;
875  double beta;
876  double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
877  int i = 0;
878  while ( currentDistanceAlongLine < totalLineLength - labelWidth )
879  {
880  // calculate positions along linestring corresponding to start and end of current label candidate
881  line->getPointByDistance( segmentLengths, distanceToSegment, currentDistanceAlongLine, &candidateStartX, &candidateStartY );
882  line->getPointByDistance( segmentLengths, distanceToSegment, currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
883 
884  if ( currentDistanceAlongLine < 0 )
885  {
886  // label is bigger than line, use whole available line
887  candidateLength = std::sqrt( ( x[nbPoints - 1] - x[0] ) * ( x[nbPoints - 1] - x[0] )
888  + ( y[nbPoints - 1] - y[0] ) * ( y[nbPoints - 1] - y[0] ) );
889  }
890  else
891  {
892  candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
893  }
894 
895  cost = candidateLength / labelWidth;
896  if ( cost > 0.98 )
897  cost = 0.0001;
898  else
899  {
900  // jaggy line has a greater cost
901  cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
902  }
903 
904  // penalize positions which are further from the line's midpoint
905  double costCenter = std::fabs( totalLineLength / 2 - ( currentDistanceAlongLine + labelWidth / 2 ) ) / totalLineLength; // <0, 0.5>
906  cost += costCenter / 1000; // < 0, 0.0005 >
907  cost += initialCost;
908 
909  if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
910  {
911  angle = 0.0;
912  }
913  else
914  angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
915 
916  beta = angle + M_PI_2;
917 
919  {
920  // find out whether the line direction for this candidate is from right to left
921  bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
922  // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
923  bool reversed = ( ( flags & FLAG_MAP_ORIENTATION ) ? isRightToLeft : false );
924  bool aboveLine = ( !reversed && ( flags & FLAG_ABOVE_LINE ) ) || ( reversed && ( flags & FLAG_BELOW_LINE ) );
925  bool belowLine = ( !reversed && ( flags & FLAG_BELOW_LINE ) ) || ( reversed && ( flags & FLAG_ABOVE_LINE ) );
926 
927  if ( aboveLine )
928  {
929  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
930  {
931  const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
932  positions.append( new LabelPosition( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
933  }
934  }
935  if ( belowLine )
936  {
937  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
938  {
939  const double candidateCost = cost + ( !reversed ? 0.001 : 0 );
940  positions.append( new LabelPosition( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
941  }
942  }
943  if ( flags & FLAG_ON_LINE )
944  {
945  if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
946  {
947  const double candidateCost = cost + 0.002;
948  positions.append( new LabelPosition( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft ) ); // Line
949  }
950  }
951  }
953  {
954  positions.append( new LabelPosition( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this ) ); // Line
955  }
956  else
957  {
958  // an invalid arrangement?
959  }
960 
961  currentDistanceAlongLine += lineStepDistance;
962 
963  i++;
964 
965  if ( lineStepDistance < 0 )
966  break;
967  }
968 
969  //delete line;
970 
971  delete[] segmentLengths;
972  delete[] distanceToSegment;
973 
974  lPos.append( positions );
975  return lPos.size();
976 }
977 
978 
979 LabelPosition *FeaturePart::curvedPlacementAtOffset( PointSet *path_positions, double *path_distances, int &orientation, const double offsetAlongLine, bool &reversed, bool &flip )
980 {
981  double offsetAlongSegment = offsetAlongLine;
982  int index = 1;
983  // Find index of segment corresponding to starting offset
984  while ( index < path_positions->nbPoints && offsetAlongSegment > path_distances[index] )
985  {
986  offsetAlongSegment -= path_distances[index];
987  index += 1;
988  }
989  if ( index >= path_positions->nbPoints )
990  {
991  return nullptr;
992  }
993 
994  LabelInfo *li = mLF->curvedLabelInfo();
995 
996  double string_height = li->label_height;
997 
998  const double segment_length = path_distances[index];
999  if ( qgsDoubleNear( segment_length, 0.0 ) )
1000  {
1001  // Not allowed to place across on 0 length segments or discontinuities
1002  return nullptr;
1003  }
1004 
1005  if ( orientation == 0 ) // Must be map orientation
1006  {
1007  // Calculate the orientation based on the angle of the path segment under consideration
1008 
1009  double _distance = offsetAlongSegment;
1010  int endindex = index;
1011 
1012  double startLabelX = 0;
1013  double startLabelY = 0;
1014  double endLabelX = 0;
1015  double endLabelY = 0;
1016  for ( int i = 0; i < li->char_num; i++ )
1017  {
1018  LabelInfo::CharacterInfo &ci = li->char_info[i];
1019  double characterStartX, characterStartY;
1020  if ( !nextCharPosition( ci.width, path_distances[endindex], path_positions, endindex, _distance, characterStartX, characterStartY, endLabelX, endLabelY ) )
1021  {
1022  return nullptr;
1023  }
1024  if ( i == 0 )
1025  {
1026  startLabelX = characterStartX;
1027  startLabelY = characterStartY;
1028  }
1029  }
1030 
1031  // Determine the angle of the path segment under consideration
1032  double dx = endLabelX - startLabelX;
1033  double dy = endLabelY - startLabelY;
1034  const double lineAngle = std::atan2( -dy, dx ) * 180 / M_PI;
1035 
1036  bool isRightToLeft = ( lineAngle > 90 || lineAngle < -90 );
1037  reversed = isRightToLeft;
1038  orientation = isRightToLeft ? -1 : 1;
1039  }
1040 
1041  if ( !showUprightLabels() )
1042  {
1043  if ( orientation < 0 )
1044  {
1045  flip = true; // Report to the caller, that the orientation is flipped
1046  reversed = !reversed;
1047  orientation = 1;
1048  }
1049  }
1050 
1051  LabelPosition *slp = nullptr;
1052  LabelPosition *slp_tmp = nullptr;
1053 
1054  double old_x = path_positions->x[index - 1];
1055  double old_y = path_positions->y[index - 1];
1056 
1057  double new_x = path_positions->x[index];
1058  double new_y = path_positions->y[index];
1059 
1060  double dx = new_x - old_x;
1061  double dy = new_y - old_y;
1062 
1063  double angle = std::atan2( -dy, dx );
1064 
1065  for ( int i = 0; i < li->char_num; i++ )
1066  {
1067  double last_character_angle = angle;
1068 
1069  // grab the next character according to the orientation
1070  LabelInfo::CharacterInfo &ci = ( orientation > 0 ? li->char_info[i] : li->char_info[li->char_num - i - 1] );
1071  if ( qgsDoubleNear( ci.width, 0.0 ) )
1072  // Certain scripts rely on zero-width character, skip those to prevent failure (see #15801)
1073  continue;
1074 
1075  double start_x, start_y, end_x, end_y;
1076  if ( !nextCharPosition( ci.width, path_distances[index], path_positions, index, offsetAlongSegment, start_x, start_y, end_x, end_y ) )
1077  {
1078  delete slp;
1079  return nullptr;
1080  }
1081 
1082  // Calculate angle from the start of the character to the end based on start_/end_ position
1083  angle = std::atan2( start_y - end_y, end_x - start_x );
1084 
1085  // Test last_character_angle vs angle
1086  // since our rendering angle has changed then check against our
1087  // max allowable angle change.
1088  double angle_delta = last_character_angle - angle;
1089  // normalise between -180 and 180
1090  while ( angle_delta > M_PI ) angle_delta -= 2 * M_PI;
1091  while ( angle_delta < -M_PI ) angle_delta += 2 * M_PI;
1092  if ( ( li->max_char_angle_inside > 0 && angle_delta > 0
1093  && angle_delta > li->max_char_angle_inside * ( M_PI / 180 ) )
1094  || ( li->max_char_angle_outside < 0 && angle_delta < 0
1095  && angle_delta < li->max_char_angle_outside * ( M_PI / 180 ) ) )
1096  {
1097  delete slp;
1098  return nullptr;
1099  }
1100 
1101  // Shift the character downwards since the draw position is specified at the baseline
1102  // and we're calculating the mean line here
1103  double dist = 0.9 * li->label_height / 2;
1104  if ( orientation < 0 )
1105  {
1106  dist = -dist;
1107  flip = true;
1108  }
1109  start_x += dist * std::cos( angle + M_PI_2 );
1110  start_y -= dist * std::sin( angle + M_PI_2 );
1111 
1112  double render_angle = angle;
1113 
1114  double render_x = start_x;
1115  double render_y = start_y;
1116 
1117  // Center the text on the line
1118  //render_x -= ((string_height/2.0) - 1.0)*math.cos(render_angle+math.pi/2)
1119  //render_y += ((string_height/2.0) - 1.0)*math.sin(render_angle+math.pi/2)
1120 
1121  if ( orientation < 0 )
1122  {
1123  // rotate in place
1124  render_x += ci.width * std::cos( render_angle ); //- (string_height-2)*sin(render_angle);
1125  render_y -= ci.width * std::sin( render_angle ); //+ (string_height-2)*cos(render_angle);
1126  render_angle += M_PI;
1127  }
1128 
1129  LabelPosition *tmp = new LabelPosition( 0, render_x /*- xBase*/, render_y /*- yBase*/, ci.width, string_height, -render_angle, 0.0001, this );
1130  tmp->setPartId( orientation > 0 ? i : li->char_num - i - 1 );
1131  if ( !slp )
1132  slp = tmp;
1133  else
1134  slp_tmp->setNextPart( tmp );
1135  slp_tmp = tmp;
1136 
1137  // Normalise to 0 <= angle < 2PI
1138  while ( render_angle >= 2 * M_PI ) render_angle -= 2 * M_PI;
1139  while ( render_angle < 0 ) render_angle += 2 * M_PI;
1140 
1141  if ( render_angle > M_PI_2 && render_angle < 1.5 * M_PI )
1143  }
1144 
1145  return slp;
1146 }
1147 
1148 static LabelPosition *_createCurvedCandidate( LabelPosition *lp, double angle, double dist )
1149 {
1150  LabelPosition *newLp = new LabelPosition( *lp );
1151  newLp->offsetPosition( dist * std::cos( angle + M_PI_2 ), dist * std::sin( angle + M_PI_2 ) );
1152  return newLp;
1153 }
1154 
1155 int FeaturePart::createCurvedCandidatesAlongLine( QList< LabelPosition * > &lPos, PointSet *mapShape )
1156 {
1157  LabelInfo *li = mLF->curvedLabelInfo();
1158 
1159  // label info must be present
1160  if ( !li || li->char_num == 0 )
1161  return 0;
1162 
1163  // distance calculation
1164  std::unique_ptr< double [] > path_distances = qgis::make_unique<double[]>( mapShape->nbPoints );
1165  double total_distance = 0;
1166  double old_x = -1.0, old_y = -1.0;
1167  for ( int i = 0; i < mapShape->nbPoints; i++ )
1168  {
1169  if ( i == 0 )
1170  path_distances[i] = 0;
1171  else
1172  path_distances[i] = std::sqrt( std::pow( old_x - mapShape->x[i], 2 ) + std::pow( old_y - mapShape->y[i], 2 ) );
1173  old_x = mapShape->x[i];
1174  old_y = mapShape->y[i];
1175 
1176  total_distance += path_distances[i];
1177  }
1178 
1179  if ( qgsDoubleNear( total_distance, 0.0 ) )
1180  {
1181  return 0;
1182  }
1183 
1184  double totalCharacterWidth = 0;
1185  for ( int i = 0; i < li->char_num; ++i )
1186  totalCharacterWidth += li->char_info[ i ].width;
1187 
1188  if ( totalCharacterWidth > total_distance )
1189  {
1190  // label doesn't fit on this line, don't waste time trying to make candidates
1191  // TODO: in future allow this, and allow label to overlap end of line
1192  return 0;
1193  }
1194 
1195  QLinkedList<LabelPosition *> positions;
1196  double delta = std::max( li->label_height, total_distance / mLF->layer()->pal->line_p );
1197 
1198  pal::LineArrangementFlags flags = mLF->arrangementFlags();
1199  if ( flags == 0 )
1200  flags = FLAG_ON_LINE; // default flag
1201 
1202  // generate curved labels
1203  for ( double distanceAlongLineToStartCandidate = 0; distanceAlongLineToStartCandidate < total_distance; distanceAlongLineToStartCandidate += delta )
1204  {
1205  bool flip = false;
1206  // placements may need to be reversed if using map orientation and the line has right-to-left direction
1207  bool reversed = false;
1208 
1209  // an orientation of 0 means try both orientations and choose the best
1210  int orientation = 0;
1211  if ( !( flags & FLAG_MAP_ORIENTATION ) )
1212  {
1213  //... but if we are using line orientation flags, then we can only accept a single orientation,
1214  // as we need to ensure that the labels fall inside or outside the polyline or polygon (and not mixed)
1215  orientation = 1;
1216  }
1217 
1218  LabelPosition *slp = curvedPlacementAtOffset( mapShape, path_distances.get(), orientation, distanceAlongLineToStartCandidate, reversed, flip );
1219  if ( !slp )
1220  continue;
1221 
1222  // If we placed too many characters upside down
1223  if ( slp->upsideDownCharCount() >= li->char_num / 2.0 )
1224  {
1225  // if labels should be shown upright then retry with the opposite orientation
1226  if ( ( showUprightLabels() && !flip ) )
1227  {
1228  delete slp;
1229  orientation = -orientation;
1230  slp = curvedPlacementAtOffset( mapShape, path_distances.get(), orientation, distanceAlongLineToStartCandidate, reversed, flip );
1231  }
1232  }
1233  if ( !slp )
1234  continue;
1235 
1236  // evaluate cost
1237  double angle_diff = 0.0, angle_last = 0.0, diff;
1238  LabelPosition *tmp = slp;
1239  double sin_avg = 0, cos_avg = 0;
1240  while ( tmp )
1241  {
1242  if ( tmp != slp ) // not first?
1243  {
1244  diff = std::fabs( tmp->getAlpha() - angle_last );
1245  if ( diff > 2 * M_PI ) diff -= 2 * M_PI;
1246  diff = std::min( diff, 2 * M_PI - diff ); // difference 350 deg is actually just 10 deg...
1247  angle_diff += diff;
1248  }
1249 
1250  sin_avg += std::sin( tmp->getAlpha() );
1251  cos_avg += std::cos( tmp->getAlpha() );
1252  angle_last = tmp->getAlpha();
1253  tmp = tmp->getNextPart();
1254  }
1255 
1256  double angle_diff_avg = li->char_num > 1 ? ( angle_diff / ( li->char_num - 1 ) ) : 0; // <0, pi> but pi/8 is much already
1257  double cost = angle_diff_avg / 100; // <0, 0.031 > but usually <0, 0.003 >
1258  if ( cost < 0.0001 ) cost = 0.0001;
1259 
1260  // penalize positions which are further from the line's midpoint
1261  double labelCenter = distanceAlongLineToStartCandidate + getLabelWidth() / 2;
1262  double costCenter = std::fabs( total_distance / 2 - labelCenter ) / total_distance; // <0, 0.5>
1263  cost += costCenter / 100; // < 0, 0.005 >
1264  slp->setCost( cost );
1265 
1266  // average angle is calculated with respect to periodicity of angles
1267  double angle_avg = std::atan2( sin_avg / li->char_num, cos_avg / li->char_num );
1268  bool localreversed = flip ? !reversed : reversed;
1269  // displacement - we loop through 3 times, generating above, online then below line placements successively
1270  for ( int i = 0; i <= 2; ++i )
1271  {
1272  LabelPosition *p = nullptr;
1273  if ( i == 0 && ( ( !localreversed && ( flags & FLAG_ABOVE_LINE ) ) || ( localreversed && ( flags & FLAG_BELOW_LINE ) ) ) )
1274  p = _createCurvedCandidate( slp, angle_avg, mLF->distLabel() + li->label_height / 2 );
1275  if ( i == 1 && flags & FLAG_ON_LINE )
1276  {
1277  p = _createCurvedCandidate( slp, angle_avg, 0 );
1278  p->setCost( p->cost() + 0.002 );
1279  }
1280  if ( i == 2 && ( ( !localreversed && ( flags & FLAG_BELOW_LINE ) ) || ( localreversed && ( flags & FLAG_ABOVE_LINE ) ) ) )
1281  {
1282  p = _createCurvedCandidate( slp, angle_avg, -li->label_height / 2 - mLF->distLabel() );
1283  p->setCost( p->cost() + 0.001 );
1284  }
1285 
1286  if ( p && mLF->permissibleZonePrepared() )
1287  {
1288  bool within = true;
1289  LabelPosition *currentPos = p;
1290  while ( within && currentPos )
1291  {
1292  within = GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), currentPos->getX(), currentPos->getY(), currentPos->getWidth(), currentPos->getHeight(), currentPos->getAlpha() );
1293  currentPos = currentPos->getNextPart();
1294  }
1295  if ( !within )
1296  {
1297  delete p;
1298  p = nullptr;
1299  }
1300  }
1301 
1302  if ( p )
1303  positions.append( p );
1304  }
1305 
1306  // delete original candidate
1307  delete slp;
1308  }
1309 
1310  int nbp = positions.size();
1311  for ( int i = 0; i < nbp; i++ )
1312  {
1313  lPos << positions.takeFirst();
1314  }
1315 
1316  return nbp;
1317 }
1318 
1319 /*
1320  * seg 2
1321  * pt3 ____________pt2
1322  * ¦ ¦
1323  * ¦ ¦
1324  * seg 3 ¦ BBOX ¦ seg 1
1325  * ¦ ¦
1326  * ¦____________¦
1327  * pt0 seg 0 pt1
1328  *
1329  */
1330 
1331 int FeaturePart::createCandidatesForPolygon( QList< LabelPosition *> &lPos, PointSet *mapShape )
1332 {
1333  int i;
1334  int j;
1335 
1336  double labelWidth = getLabelWidth();
1337  double labelHeight = getLabelHeight();
1338 
1339  QLinkedList<PointSet *> shapes_toProcess;
1340  QLinkedList<PointSet *> shapes_final;
1341 
1342  mapShape->parent = nullptr;
1343 
1344  shapes_toProcess.append( mapShape );
1345 
1346  splitPolygons( shapes_toProcess, shapes_final, labelWidth, labelHeight );
1347 
1348  int nbp;
1349 
1350  if ( !shapes_final.isEmpty() )
1351  {
1352  QLinkedList<LabelPosition *> positions;
1353 
1354  int id = 0; // ids for candidates
1355  double dlx, dly; // delta from label center and bottom-left corner
1356  double alpha = 0.0; // rotation for the label
1357  double px, py;
1358  double dx;
1359  double dy;
1360  int bbid;
1361  double beta;
1362  double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
1363  double rx, ry;
1364  CHullBox **boxes = new CHullBox*[shapes_final.size()];
1365  j = 0;
1366 
1367  // Compute bounding box foreach finalShape
1368  while ( !shapes_final.isEmpty() )
1369  {
1370  PointSet *shape = shapes_final.takeFirst();
1371  boxes[j] = shape->compute_chull_bbox();
1372 
1373  if ( shape->parent )
1374  delete shape;
1375 
1376  j++;
1377  }
1378 
1379  //dx = dy = min( yrm, xrm ) / 2;
1380  dx = labelWidth / 2.0;
1381  dy = labelHeight / 2.0;
1382 
1383  int numTry = 0;
1384 
1385  //fit in polygon only mode slows down calculation a lot, so if it's enabled
1386  //then use a smaller limit for number of iterations
1387  int maxTry = mLF->permissibleZonePrepared() ? 7 : 10;
1388 
1389  do
1390  {
1391  for ( bbid = 0; bbid < j; bbid++ )
1392  {
1393  CHullBox *box = boxes[bbid];
1394 
1395  if ( ( box->length * box->width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
1396  {
1397  // Very Large BBOX (should never occur)
1398  continue;
1399  }
1400 
1402  {
1403  //check width/height of bbox is sufficient for label
1404  if ( mLF->permissibleZone().boundingBox().width() < labelWidth ||
1405  mLF->permissibleZone().boundingBox().height() < labelHeight )
1406  {
1407  //no way label can fit in this box, skip it
1408  continue;
1409  }
1410  }
1411 
1412  bool enoughPlace = false;
1414  {
1415  enoughPlace = true;
1416  px = ( box->x[0] + box->x[2] ) / 2 - labelWidth;
1417  py = ( box->y[0] + box->y[2] ) / 2 - labelHeight;
1418  int i, j;
1419 
1420  // Virtual label: center on bbox center, label size = 2x original size
1421  // alpha = 0.
1422  // If all corner are in bbox then place candidates horizontaly
1423  for ( rx = px, i = 0; i < 2; rx = rx + 2 * labelWidth, i++ )
1424  {
1425  for ( ry = py, j = 0; j < 2; ry = ry + 2 * labelHeight, j++ )
1426  {
1427  if ( !mapShape->containsPoint( rx, ry ) )
1428  {
1429  enoughPlace = false;
1430  break;
1431  }
1432  }
1433  if ( !enoughPlace )
1434  {
1435  break;
1436  }
1437  }
1438 
1439  } // arrangement== FREE ?
1440 
1441  if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal || enoughPlace )
1442  {
1443  alpha = 0.0; // HORIZ
1444  }
1445  else if ( box->length > 1.5 * labelWidth && box->width > 1.5 * labelWidth )
1446  {
1447  if ( box->alpha <= M_PI_4 )
1448  {
1449  alpha = box->alpha;
1450  }
1451  else
1452  {
1453  alpha = box->alpha - M_PI_2;
1454  }
1455  }
1456  else if ( box->length > box->width )
1457  {
1458  alpha = box->alpha - M_PI_2;
1459  }
1460  else
1461  {
1462  alpha = box->alpha;
1463  }
1464 
1465  beta = std::atan2( labelHeight, labelWidth ) + alpha;
1466 
1467 
1468  //alpha = box->alpha;
1469 
1470  // delta from label center and down-left corner
1471  dlx = std::cos( beta ) * diago;
1472  dly = std::sin( beta ) * diago;
1473 
1474  double px0, py0;
1475 
1476  px0 = box->width / 2.0;
1477  py0 = box->length / 2.0;
1478 
1479  px0 -= std::ceil( px0 / dx ) * dx;
1480  py0 -= std::ceil( py0 / dy ) * dy;
1481 
1482  for ( px = px0; px <= box->width; px += dx )
1483  {
1484  for ( py = py0; py <= box->length; py += dy )
1485  {
1486 
1487  rx = std::cos( box->alpha ) * px + std::cos( box->alpha - M_PI_2 ) * py;
1488  ry = std::sin( box->alpha ) * px + std::sin( box->alpha - M_PI_2 ) * py;
1489 
1490  rx += box->x[0];
1491  ry += box->y[0];
1492 
1493  bool candidateAcceptable = ( mLF->permissibleZonePrepared()
1494  ? GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), rx - dlx, ry - dly, labelWidth, labelHeight, alpha )
1495  : mapShape->containsPoint( rx, ry ) );
1496  if ( candidateAcceptable )
1497  {
1498  // cost is set to minimal value, evaluated later
1499  positions.append( new LabelPosition( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this ) ); // Polygon
1500  }
1501  }
1502  }
1503  } // forall box
1504 
1505  nbp = positions.size();
1506  if ( nbp == 0 )
1507  {
1508  dx /= 2;
1509  dy /= 2;
1510  numTry++;
1511  }
1512  }
1513  while ( nbp == 0 && numTry < maxTry );
1514 
1515  nbp = positions.size();
1516 
1517  for ( i = 0; i < nbp; i++ )
1518  {
1519  lPos << positions.takeFirst();
1520  }
1521 
1522  for ( bbid = 0; bbid < j; bbid++ )
1523  {
1524  delete boxes[bbid];
1525  }
1526 
1527  delete[] boxes;
1528  }
1529  else
1530  {
1531  nbp = 0;
1532  }
1533 
1534  return nbp;
1535 }
1536 
1537 int FeaturePart::createCandidates( QList< LabelPosition *> &lPos,
1538  const GEOSPreparedGeometry *mapBoundary,
1539  PointSet *mapShape, RTree<LabelPosition *, double, 2, double> *candidates )
1540 {
1541  double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
1542 
1543  if ( mLF->hasFixedPosition() )
1544  {
1545  lPos << new LabelPosition( 0, mLF->fixedPosition().x(), mLF->fixedPosition().y(), getLabelWidth(), getLabelHeight(), angle, 0.0, this );
1546  }
1547  else
1548  {
1549  switch ( type )
1550  {
1551  case GEOS_POINT:
1553  createCandidatesAtOrderedPositionsOverPoint( x[0], y[0], lPos, angle );
1555  createCandidatesOverPoint( x[0], y[0], lPos, angle );
1556  else
1557  createCandidatesAroundPoint( x[0], y[0], lPos, angle );
1558  break;
1559  case GEOS_LINESTRING:
1560  if ( mLF->layer()->isCurved() )
1561  createCurvedCandidatesAlongLine( lPos, mapShape );
1562  else
1563  createCandidatesAlongLine( lPos, mapShape );
1564  break;
1565 
1566  case GEOS_POLYGON:
1567  switch ( mLF->layer()->arrangement() )
1568  {
1571  double cx, cy;
1572  mapShape->getCentroid( cx, cy, mLF->layer()->centroidInside() );
1574  createCandidatesOverPoint( cx, cy, lPos, angle );
1575  else
1576  createCandidatesAroundPoint( cx, cy, lPos, angle );
1577  break;
1579  createCandidatesAlongLine( lPos, mapShape );
1580  break;
1582  createCurvedCandidatesAlongLine( lPos, mapShape );
1583  break;
1584  default:
1585  createCandidatesForPolygon( lPos, mapShape );
1586  break;
1587  }
1588  }
1589  }
1590 
1591  // purge candidates that are outside the bbox
1592 
1593  QMutableListIterator< LabelPosition *> i( lPos );
1594  while ( i.hasNext() )
1595  {
1596  LabelPosition *pos = i.next();
1597  bool outside = false;
1598 
1599  if ( mLF->layer()->pal->getShowPartial() )
1600  outside = !pos->intersects( mapBoundary );
1601  else
1602  outside = !pos->within( mapBoundary );
1603  if ( outside )
1604  {
1605  i.remove();
1606  delete pos;
1607  }
1608  else // this one is OK
1609  {
1610  pos->insertIntoIndex( candidates );
1611  }
1612  }
1613 
1614  std::sort( lPos.begin(), lPos.end(), CostCalculator::candidateSortGrow );
1615  return lPos.count();
1616 }
1617 
1618 void FeaturePart::addSizePenalty( int nbp, QList< LabelPosition * > &lPos, double bbx[4], double bby[4] )
1619 {
1620  if ( !mGeos )
1621  createGeosGeom();
1622 
1623  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1624  int geomType = GEOSGeomTypeId_r( ctxt, mGeos );
1625 
1626  double sizeCost = 0;
1627  if ( geomType == GEOS_LINESTRING )
1628  {
1629  double length;
1630  try
1631  {
1632  if ( GEOSLength_r( ctxt, mGeos, &length ) != 1 )
1633  return; // failed to calculate length
1634  }
1635  catch ( GEOSException &e )
1636  {
1637  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
1638  return;
1639  }
1640  double bbox_length = std::max( bbx[2] - bbx[0], bby[2] - bby[0] );
1641  if ( length >= bbox_length / 4 )
1642  return; // the line is longer than quarter of height or width - don't penalize it
1643 
1644  sizeCost = 1 - ( length / ( bbox_length / 4 ) ); // < 0,1 >
1645  }
1646  else if ( geomType == GEOS_POLYGON )
1647  {
1648  double area;
1649  try
1650  {
1651  if ( GEOSArea_r( ctxt, mGeos, &area ) != 1 )
1652  return;
1653  }
1654  catch ( GEOSException &e )
1655  {
1656  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
1657  return;
1658  }
1659  double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
1660  if ( area >= bbox_area / 16 )
1661  return; // covers more than 1/16 of our view - don't penalize it
1662 
1663  sizeCost = 1 - ( area / ( bbox_area / 16 ) ); // < 0, 1 >
1664  }
1665  else
1666  return; // no size penalty for points
1667 
1668  // apply the penalty
1669  for ( int i = 0; i < nbp; i++ )
1670  {
1671  lPos.at( i )->setCost( lPos.at( i )->cost() + sizeCost / 100 );
1672  }
1673 }
1674 
1676 {
1677  if ( !p2->mGeos )
1678  p2->createGeosGeom();
1679 
1680  try
1681  {
1682  return ( GEOSPreparedTouches_r( QgsGeos::getGEOSHandler(), preparedGeom(), p2->mGeos ) == 1 );
1683  }
1684  catch ( GEOSException &e )
1685  {
1686  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
1687  return false;
1688  }
1689 }
1690 
1692 {
1693  if ( !mGeos )
1694  createGeosGeom();
1695  if ( !other->mGeos )
1696  other->createGeosGeom();
1697 
1698  GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1699  try
1700  {
1701  GEOSGeometry *g1 = GEOSGeom_clone_r( ctxt, mGeos );
1702  GEOSGeometry *g2 = GEOSGeom_clone_r( ctxt, other->mGeos );
1703  GEOSGeometry *geoms[2] = { g1, g2 };
1704  geos::unique_ptr g( GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 ) );
1705  geos::unique_ptr gTmp( GEOSLineMerge_r( ctxt, g.get() ) );
1706 
1707  if ( GEOSGeomTypeId_r( ctxt, gTmp.get() ) != GEOS_LINESTRING )
1708  {
1709  // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
1710  return false;
1711  }
1712  invalidateGeos();
1713 
1714  // set up new geometry
1715  mGeos = gTmp.release();
1716  mOwnsGeom = true;
1717 
1718  deleteCoords();
1719  qDeleteAll( mHoles );
1720  mHoles.clear();
1721  extractCoords( mGeos );
1722  return true;
1723  }
1724  catch ( GEOSException &e )
1725  {
1726  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
1727  return false;
1728  }
1729 }
1730 
1732 {
1733  if ( mLF->alwaysShow() )
1734  {
1735  //if feature is set to always show, bump the priority up by orders of magnitude
1736  //so that other feature's labels are unlikely to be placed over the label for this feature
1737  //(negative numbers due to how pal::extract calculates inactive cost)
1738  return -0.2;
1739  }
1740 
1741  return mLF->priority() >= 0 ? mLF->priority() : mLF->layer()->priority();
1742 }
1743 
1745 {
1746  bool uprightLabel = false;
1747 
1748  switch ( mLF->layer()->upsidedownLabels() )
1749  {
1750  case Layer::Upright:
1751  uprightLabel = true;
1752  break;
1753  case Layer::ShowDefined:
1754  // upright only dynamic labels
1755  if ( !hasFixedRotation() || ( !hasFixedPosition() && fixedAngle() == 0.0 ) )
1756  {
1757  uprightLabel = true;
1758  }
1759  break;
1760  case Layer::ShowAll:
1761  break;
1762  default:
1763  uprightLabel = true;
1764  }
1765  return uprightLabel;
1766 }
1767 
1768 bool FeaturePart::nextCharPosition( double charWidth, double segmentLength, PointSet *path_positions, int &index, double &currentDistanceAlongSegment,
1769  double &characterStartX, double &characterStartY, double &characterEndX, double &characterEndY ) const
1770 {
1771  // Coordinates this character will start at
1772  if ( qgsDoubleNear( segmentLength, 0.0 ) )
1773  {
1774  // Not allowed to place across on 0 length segments or discontinuities
1775  return false;
1776  }
1777 
1778  double segmentStartX = path_positions->x[index - 1];
1779  double segmentStartY = path_positions->y[index - 1];
1780 
1781  double segmentEndX = path_positions->x[index];
1782  double segmentEndY = path_positions->y[index];
1783 
1784  double segmentDx = segmentEndX - segmentStartX;
1785  double segmentDy = segmentEndY - segmentStartY;
1786 
1787  characterStartX = segmentStartX + segmentDx * currentDistanceAlongSegment / segmentLength;
1788  characterStartY = segmentStartY + segmentDy * currentDistanceAlongSegment / segmentLength;
1789 
1790  // Coordinates this character ends at, calculated below
1791  characterEndX = 0;
1792  characterEndY = 0;
1793 
1794  if ( segmentLength - currentDistanceAlongSegment >= charWidth )
1795  {
1796  // if the distance remaining in this segment is enough, we just go further along the segment
1797  currentDistanceAlongSegment += charWidth;
1798  characterEndX = segmentStartX + segmentDx * currentDistanceAlongSegment / segmentLength;
1799  characterEndY = segmentStartY + segmentDy * currentDistanceAlongSegment / segmentLength;
1800  }
1801  else
1802  {
1803  // If there isn't enough distance left on this segment
1804  // then we need to search until we find the line segment that ends further than ci.width away
1805  do
1806  {
1807  segmentStartX = segmentEndX;
1808  segmentStartY = segmentEndY;
1809  index++;
1810  if ( index >= path_positions->nbPoints ) // Bail out if we run off the end of the shape
1811  {
1812  return false;
1813  }
1814  segmentEndX = path_positions->x[index];
1815  segmentEndY = path_positions->y[index];
1816  }
1817  while ( std::sqrt( std::pow( characterStartX - segmentEndX, 2 ) + std::pow( characterStartY - segmentEndY, 2 ) ) < charWidth ); // Distance from start_ to new_
1818 
1819  // Calculate the position to place the end of the character on
1820  GeomFunction::findLineCircleIntersection( characterStartX, characterStartY, charWidth, segmentStartX, segmentStartY, segmentEndX, segmentEndY, characterEndX, characterEndY );
1821 
1822  // Need to calculate distance on the new segment
1823  currentDistanceAlongSegment = std::sqrt( std::pow( segmentStartX - characterEndX, 2 ) + std::pow( segmentStartY - characterEndY, 2 ) );
1824  }
1825  return true;
1826 }
Label on bottom right of point.
double right() const
Returns the right margin.
Definition: qgsmargins.h:84
bool centroidInside() const
Returns whether labels placed at the centroid of features within the layer are forced to be placed in...
Definition: layer.h:232
double length
Definition: pointset.h:60
Label on bottom-left of point.
int createCandidatesForPolygon(QList< LabelPosition *> &lPos, PointSet *mapShape)
Generate candidates for polygon features.
Definition: feature.cpp:1331
Label on top of point, slightly left of center.
void invalidateGeos()
Definition: pointset.cpp:179
double distLabel() const
Applies to "around point" placement strategy or linestring features.
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
Definition: pointset.cpp:242
double fixedAngle() const
Returns the fixed angle for the feature&#39;s label.
Definition: feature.h:252
QgsFeatureId featureId() const
Returns the unique ID of the feature.
Definition: feature.cpp:151
QgsFeatureId id() const
Identifier of the label (unique within the parent label provider)
static bool candidateSortGrow(const LabelPosition *c1, const LabelPosition *c2)
Sorts label candidates in ascending order of cost.
double max_char_angle_outside
Definition: feature.h:80
double priority() const
Returns the feature&#39;s labeling priority.
bool alwaysShow() const
Whether label should be always shown (sets very high label priority)
Label on top-left of point.
void setCost(double newCost)
Sets the candidate label position&#39;s geographical cost.
int incrementUpsideDownCharCount()
Increases the count of upside down characters for this label position.
Arranges candidates over a point (or centroid of a polygon), or at a preset offset from the point...
bool hasFixedRotation() const
Returns true if the feature&#39;s label has a fixed rotation.
Definition: feature.h:249
double getY(int i=0) const
Returns the down-left y coordinate.
double y
Definition: qgspointxy.h:48
A set of features which influence the labeling process.
Definition: layer.h:63
PredefinedPointPosition
Positions for labels when using the QgsPalLabeling::OrderedPositionsAroundPoint placement mode...
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:265
void offsetPosition(double xOffset, double yOffset)
Shift the label by specified offset.
int createCandidatesAlongLineNearStraightSegments(QList< LabelPosition *> &lPos, PointSet *mapShape)
Generate candidates for line feature, by trying to place candidates towards the middle of the longest...
Definition: feature.cpp:596
void createGeosGeom() const
Definition: pointset.cpp:125
Candidates are placed in predefined positions around a point. Preference is given to positions with g...
friend class LabelPosition
Definition: pointset.h:71
const GEOSPreparedGeometry * permissibleZonePrepared() const
Returns a GEOS prepared geometry representing the label&#39;s permissibleZone().
qint64 QgsFeatureId
Definition: qgsfeatureid.h:25
static void findLineCircleIntersection(double cx, double cy, double radius, double x1, double y1, double x2, double y2, double &xRes, double &yRes)
Label on top-right of point.
const QSizeF & symbolSize() const
Returns the size of the rendered symbol associated with this feature, if applicable.
bool isClosed() const
Returns true if pointset is closed.
Definition: pointset.cpp:849
bool mergeWithFeaturePart(FeaturePart *other)
Merge other (connected) part with this one and save the result in this part (other is unchanged)...
Definition: feature.cpp:1691
UpsideDownLabels upsidedownLabels() const
Returns how upside down labels are handled within the layer.
Definition: layer.h:216
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:1675
const QgsMargins & visualMargin() const
Returns the visual margin for the label feature.
double getLabelDistance() const
Definition: feature.h:246
int createCandidatesAtOrderedPositionsOverPoint(double x, double y, QList< LabelPosition *> &lPos, double angle)
Generates candidates following a prioritized list of predefined positions around a point...
Definition: feature.cpp:303
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
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2815
QgsPointXY positionOffset() const
Applies only to "offset from point" placement strategy.
Arranges horizontal candidates scattered throughout a polygon feature. Applies to polygon layers only...
CharacterInfo * char_info
Definition: feature.h:83
double width
Definition: pointset.h:59
int createCandidatesAroundPoint(double x, double y, QList< LabelPosition *> &lPos, double angle)
Generate candidates for point feature, located around a specified point.
Definition: feature.cpp:430
double priority() const
Returns the layer&#39;s priority, between 0 and 1.
Definition: layer.h:177
LabelPosition * curvedPlacementAtOffset(PointSet *path_positions, double *path_distances, int &orientation, double distance, bool &reversed, bool &flip)
Returns the label position for a curved label at a specific offset along a path.
Definition: feature.cpp:979
double cost() const
Returns the candidate label position&#39;s geographical cost.
pal::LabelInfo * curvedLabelInfo() const
Gets additional infor required for curved label placement. Returns nullptr if not set...
bool hasFixedQuadrant() const
Returns whether the quadrant for the label is fixed.
Label on left of point.
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.
QgsGeometry permissibleZone() const
Returns the label&#39;s permissible zone geometry.
bool getShowPartial()
Returns whether partial labels should be allowed.
Definition: pal.cpp:565
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py)
Gets a point a set distance along a line geometry.
Definition: pointset.cpp:779
void addSizePenalty(int nbp, QList< LabelPosition *> &lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1618
PointSet * parent
Definition: pointset.h:178
double * x
Definition: pointset.h:169
double ymax
Definition: pointset.h:192
bool nextCharPosition(double charWidth, double segmentLength, PointSet *path_positions, int &index, double &currentDistanceAlongSegment, double &characterStartX, double &characterStartY, double &characterEndX, double &characterEndY) const
Returns true if the next char position is found. The referenced parameters are updated.
Definition: feature.cpp:1768
double bottom() const
Returns the bottom margin.
Definition: qgsmargins.h:90
double xmin
Definition: pointset.h:189
double getHeight() const
double width() const
Returns the width of the rectangle.
Definition: qgsrectangle.h:202
PointSet * holeOf
Definition: pointset.h:177
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:79
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
double ymin
Definition: pointset.h:191
Arranges candidates in a circle around a point (or centroid of a polygon). Applies to point or polygo...
LabelPosition * getNextPart() const
Optional additional info about label (for curved labels)
Definition: feature.h:55
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:146
double calculatePriority() const
Calculates the priority for the feature.
Definition: feature.cpp:1731
QgsPalLayerSettings::Placement arrangement() const
Returns the layer&#39;s arrangement policy.
Definition: layer.h:102
bool hasFixedAngle() const
Whether the label should use a fixed angle instead of using angle from automatic placement.
double label_height
Definition: feature.h:81
double top() const
Returns the top margin.
Definition: qgsmargins.h:78
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
int createCandidates(QList< LabelPosition *> &lPos, const GEOSPreparedGeometry *mapBoundary, PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
Generic method to generate label candidates for the feature.
Definition: feature.cpp:1537
pal::LineArrangementFlags arrangementFlags() const
Returns the feature&#39;s arrangement flags.
static double dist_euc2d(double x1, double y1, double x2, double y2)
Definition: geomfunction.h:66
pal::Layer * layer() const
Gets PAL layer of the label feature. Should be only used internally in PAL.
int createCandidatesAlongLine(QList< LabelPosition *> &lPos, PointSet *mapShape)
Generate candidates for line feature.
Definition: feature.cpp:583
double fixedAngle() const
Angle in degrees of the fixed angle (relevant only if hasFixedAngle() returns true) ...
Label below point, slightly right of center.
double getLabelHeight() const
Definition: feature.h:245
void deleteCoords()
Definition: pointset.cpp:206
static double normalizedAngle(double angle)
Ensures that an angle is in the range 0 <= angle < 2 pi.
Main class to handle feature.
Definition: feature.h:96
int upsideDownCharCount() const
Returns the number of upside down characters for this label position.
Offset distance applies from rendered symbol bounds.
void setPartId(int id)
double x
Definition: qgspointxy.h:47
bool hasFixedPosition() const
Returns true if the feature&#39;s label has a fixed position.
Definition: feature.h:255
int createCandidatesOverPoint(double x, double y, QList< LabelPosition *> &lPos, double angle)
Generate one candidate over or offset the specified point.
Definition: feature.cpp:224
double * y
Definition: pointset.h:170
QPointF quadOffset() const
Applies to "offset from point" placement strategy and "around point" (in case hasFixedQuadrant() retu...
Pal * pal
Definition: layer.h:268
void setNextPart(LabelPosition *next)
CHullBox * compute_chull_bbox()
Definition: pointset.cpp:545
Arranges candidates parallel to a generalised line representing the feature or parallel to a polygon&#39;...
bool hasFixedPosition() const
Whether the label should use a fixed position instead of being automatically placed.
double x[4]
Definition: pointset.h:54
The QgsLabelFeature class describes a feature that should be used within the labeling engine...
bool hasSameLabelFeatureAs(FeaturePart *part) const
Tests whether this feature part belongs to the same QgsLabelFeature as another feature part...
Definition: feature.cpp:156
double getAlpha() const
Returns the angle to rotate text (in rad).
double length() const
Returns length of line geometry.
Definition: pointset.cpp:826
QgsPalLayerSettings::OffsetType offsetType() const
Returns the offset type, which determines how offsets and distance to label behaves.
Label below point, slightly left of center.
~FeaturePart() override
Delete the feature.
Definition: feature.cpp:77
QList< FeaturePart * > mHoles
Definition: feature.h:306
double getWidth() const
double getX(int i=0) const
Returns the down-left x coordinate.
double y[4]
Definition: pointset.h:55
double max_char_angle_inside
Definition: feature.h:79
Label on top of point, slightly right of center.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
int createCandidatesAlongLineNearMidpoint(QList< LabelPosition *> &lPos, PointSet *mapShape, double initialCost=0.0)
Generate candidates for line feature, by trying to place candidates as close as possible to the line&#39;...
Definition: feature.cpp:818
Label directly below point.
void extractCoords(const GEOSGeometry *geom)
read coordinates from a GEOS geom
Definition: feature.cpp:85
QString name() const
Returns the layer&#39;s name.
Definition: layer.h:96
double getLabelWidth() const
Definition: feature.h:244
GEOSGeometry * mGeos
Definition: pointset.h:165
LabelPosition is a candidate feature label position.
Definition: labelposition.h:55
QgsLabelFeature * mLF
Definition: feature.h:305
Label directly above point.
Quadrant
Position of label candidate relative to feature.
Definition: labelposition.h:65
Label on right of point.
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:167
double alpha
Definition: pointset.h:57
static int reorderPolygon(int nbPoints, double *x, double *y)
Reorder points to have cross prod ((x,y)[i], (x,y)[i+1), point) > 0 when point is outside...
FeaturePart(QgsLabelFeature *lf, const GEOSGeometry *geom)
Creates a new generic feature.
Definition: feature.cpp:49
bool within(const GEOSPreparedGeometry *geometry)
Returns true if the label position is within a geometry.
QgsPointXY fixedPosition() const
Coordinates of the fixed position (relevant only if hasFixedPosition() returns true) ...
QVector< QgsPalLayerSettings::PredefinedPointPosition > predefinedPositionOrder() const
Returns the priority ordered list of predefined positions for label candidates.
bool intersects(const GEOSPreparedGeometry *geometry)
Returns true if the label position intersects a geometry.
void getCentroid(double &px, double &py, bool forceInside=false) const
Definition: pointset.cpp:740
static void splitPolygons(QLinkedList< PointSet *> &shapes_toProcess, QLinkedList< PointSet *> &shapes_final, double xrm, double yrm)
Split a concave shape into several convex shapes.
Definition: pointset.cpp:268
Arranges candidates following the curvature of a polygon&#39;s boundary. Applies to polygon layers only...
double xmax
Definition: pointset.h:190
double left() const
Returns the left margin.
Definition: qgsmargins.h:72
int char_num
Definition: feature.h:82
bool isCurved() const
Returns true if the layer has curved labels.
Definition: layer.h:107
bool showUprightLabels() const
Returns true if feature&#39;s label must be displayed upright.
Definition: feature.cpp:1744
bool mOwnsGeom
Definition: pointset.h:166
The QgsMargins class defines the four margins of a rectangle.
Definition: qgsmargins.h:37
double height() const
Returns the height of the rectangle.
Definition: qgsrectangle.h:209
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:372
int createCurvedCandidatesAlongLine(QList< LabelPosition *> &lPos, PointSet *mapShape)
Generate curved candidates for line features.
Definition: feature.cpp:1155
Arranges candidates scattered throughout a polygon feature. Candidates are rotated to respect the pol...