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