QGIS API Documentation  3.9.0-Master (224899f119)
layer.cpp
Go to the documentation of this file.
1 /*
2  * libpal - Automated Placement of Labels Library
3  *
4  * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5  * University of Applied Sciences, Western Switzerland
6  * http://www.hes-so.ch
7  *
8  * Contact:
9  * maxence.laurent <at> heig-vd <dot> ch
10  * or
11  * eric.taillard <at> heig-vd <dot> ch
12  *
13  * This file is part of libpal.
14  *
15  * libpal is free software: you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation, either version 3 of the License, or
18  * (at your option) any later version.
19  *
20  * libpal is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27  *
28  */
29 
30 #include "pal.h"
31 #include "layer.h"
32 #include "palexception.h"
33 #include "internalexception.h"
34 #include "feature.h"
35 #include "geomfunction.h"
36 #include "util.h"
37 #include "qgslabelingengine.h"
38 
39 #include <cmath>
40 #include <vector>
41 
42 using namespace pal;
43 
44 Layer::Layer( QgsAbstractLabelProvider *provider, const QString &name, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, Pal *pal, bool displayAll )
45  : mProvider( provider )
46  , mName( name )
47  , pal( pal )
48  , mObstacleType( QgsPalLayerSettings::PolygonInterior )
49  , mActive( active )
50  , mLabelLayer( toLabel )
51  , mDisplayAll( displayAll )
52  , mCentroidInside( false )
53  , mArrangement( arrangement )
54  , mMergeLines( false )
55  , mUpsidedownLabels( Upright )
56 {
57  mFeatureIndex = new RTree<FeaturePart *, double, 2, double>();
58  mObstacleIndex = new RTree<FeaturePart *, double, 2, double>();
59 
60  if ( defaultPriority < 0.0001 )
61  mDefaultPriority = 0.0001;
62  else if ( defaultPriority > 1.0 )
63  mDefaultPriority = 1.0;
64  else
65  mDefaultPriority = defaultPriority;
66 }
67 
69 {
70  mMutex.lock();
71 
72  qDeleteAll( mFeatureParts );
73  qDeleteAll( mObstacleParts );
74 
75  delete mFeatureIndex;
76  delete mObstacleIndex;
77 
78  mMutex.unlock();
79 }
80 
82 {
83  if ( priority >= 1.0 ) // low priority
84  mDefaultPriority = 1.0;
85  else if ( priority <= 0.0001 )
86  mDefaultPriority = 0.0001; // high priority
87  else
89 }
90 
92 {
93  if ( lf->size().width() < 0 || lf->size().height() < 0 )
94  return false;
95 
96  QMutexLocker locker( &mMutex );
97 
98  if ( mHashtable.contains( lf->id() ) )
99  {
100  //A feature with this id already exists. Don't throw an exception as sometimes,
101  //the same feature is added twice (dateline split with otf-reprojection)
102  return false;
103  }
104 
105  // assign label feature to this PAL layer
106  lf->setLayer( this );
107 
108  // Split MULTI GEOM and Collection in simple geometries
109 
110  bool addedFeature = false;
111 
112  double geom_size = -1, biggest_size = -1;
113  std::unique_ptr<FeaturePart> biggest_part;
114 
115  // break the (possibly multi-part) geometry into simple geometries
116  std::unique_ptr<QLinkedList<const GEOSGeometry *>> simpleGeometries( Util::unmulti( lf->geometry() ) );
117  if ( !simpleGeometries ) // unmulti() failed?
118  {
120  }
121 
122  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
123 
124  bool featureGeomIsObstacleGeom = !lf->obstacleGeometry();
125 
126  while ( !simpleGeometries->isEmpty() )
127  {
128  const GEOSGeometry *geom = simpleGeometries->takeFirst();
129 
130  // ignore invalid geometries (e.g. polygons with self-intersecting rings)
131  if ( GEOSisValid_r( geosctxt, geom ) != 1 ) // 0=invalid, 1=valid, 2=exception
132  {
133  continue;
134  }
135 
136  int type = GEOSGeomTypeId_r( geosctxt, geom );
137 
138  if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
139  {
141  }
142 
143  std::unique_ptr<FeaturePart> fpart = qgis::make_unique<FeaturePart>( lf, geom );
144 
145  // ignore invalid geometries
146  if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
147  ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
148  {
149  continue;
150  }
151 
152  // polygons: reorder coordinates
153  if ( type == GEOS_POLYGON && GeomFunction::reorderPolygon( fpart->nbPoints, fpart->x, fpart->y ) != 0 )
154  {
155  continue;
156  }
157 
158  // is the feature well defined? TODO Check epsilon
159  bool labelWellDefined = ( lf->size().width() > 0.0000001 && lf->size().height() > 0.0000001 );
160 
161  if ( lf->isObstacle() && featureGeomIsObstacleGeom )
162  {
163  //if we are not labeling the layer, only insert it into the obstacle list and avoid an
164  //unnecessary copy
165  if ( mLabelLayer && labelWellDefined )
166  {
167  addObstaclePart( new FeaturePart( *fpart ) );
168  }
169  else
170  {
171  addObstaclePart( fpart.release() );
172  }
173  }
174 
175  // feature has to be labeled?
176  if ( !mLabelLayer || !labelWellDefined )
177  {
178  //nothing more to do for this part
179  continue;
180  }
181 
182  if ( !lf->labelAllParts() && ( type == GEOS_POLYGON || type == GEOS_LINESTRING ) )
183  {
184  if ( type == GEOS_LINESTRING )
185  GEOSLength_r( geosctxt, geom, &geom_size );
186  else if ( type == GEOS_POLYGON )
187  GEOSArea_r( geosctxt, geom, &geom_size );
188 
189  if ( geom_size > biggest_size )
190  {
191  biggest_size = geom_size;
192  biggest_part.reset( fpart.release() );
193  }
194  continue; // don't add the feature part now, do it later
195  }
196 
197  // feature part is ready!
198  addFeaturePart( fpart.release(), lf->labelText() );
199  addedFeature = true;
200  }
201 
202  if ( lf->isObstacle() && !featureGeomIsObstacleGeom )
203  {
204  //do the same for the obstacle geometry
205  simpleGeometries.reset( Util::unmulti( lf->obstacleGeometry() ) );
206  if ( !simpleGeometries ) // unmulti() failed?
207  {
209  }
210 
211  while ( !simpleGeometries->isEmpty() )
212  {
213  const GEOSGeometry *geom = simpleGeometries->takeFirst();
214 
215  // ignore invalid geometries (e.g. polygons with self-intersecting rings)
216  if ( GEOSisValid_r( geosctxt, geom ) != 1 ) // 0=invalid, 1=valid, 2=exception
217  {
218  continue;
219  }
220 
221  int type = GEOSGeomTypeId_r( geosctxt, geom );
222 
223  if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
224  {
226  }
227 
228  std::unique_ptr<FeaturePart> fpart = qgis::make_unique<FeaturePart>( lf, geom );
229 
230  // ignore invalid geometries
231  if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
232  ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
233  {
234  continue;
235  }
236 
237  // polygons: reorder coordinates
238  if ( type == GEOS_POLYGON && GeomFunction::reorderPolygon( fpart->nbPoints, fpart->x, fpart->y ) != 0 )
239  {
240  continue;
241  }
242 
243  // feature part is ready!
244  addObstaclePart( fpart.release() );
245  }
246  }
247 
248  locker.unlock();
249 
250  // if using only biggest parts...
251  if ( ( !lf->labelAllParts() || lf->hasFixedPosition() ) && biggest_part )
252  {
253  addFeaturePart( biggest_part.release(), lf->labelText() );
254  addedFeature = true;
255  }
256 
257  // add feature to layer if we have added something
258  if ( addedFeature )
259  {
260  mHashtable.insert( lf->id(), lf );
261  }
262 
263  return addedFeature; // true if we've added something
264 }
265 
266 
267 void Layer::addFeaturePart( FeaturePart *fpart, const QString &labelText )
268 {
269  double bmin[2];
270  double bmax[2];
271  fpart->getBoundingBox( bmin, bmax );
272 
273  // add to list of layer's feature parts
274  mFeatureParts << fpart;
275 
276  // add to r-tree for fast spatial access
277  mFeatureIndex->Insert( bmin, bmax, fpart );
278 
279  // add to hashtable with equally named feature parts
280  if ( mMergeLines && !labelText.isEmpty() )
281  {
282  mConnectedHashtable[ labelText ].append( fpart );
283  }
284 }
285 
287 {
288  double bmin[2];
289  double bmax[2];
290  fpart->getBoundingBox( bmin, bmax );
291 
292  // add to list of layer's feature parts
293  mObstacleParts.append( fpart );
294 
295  // add to obstacle r-tree
296  mObstacleIndex->Insert( bmin, bmax, fpart );
297 }
298 
299 static FeaturePart *_findConnectedPart( FeaturePart *partCheck, const QVector<FeaturePart *> &otherParts )
300 {
301  // iterate in the rest of the parts with the same label
302  auto it = otherParts.constBegin();
303  while ( it != otherParts.constEnd() )
304  {
305  if ( partCheck->isConnected( *it ) )
306  {
307  // stop checking for other connected parts
308  return *it;
309  }
310  ++it;
311  }
312 
313  return nullptr; // no connected part found...
314 }
315 
317 {
318  // go through all label texts
319  int connectedFeaturesId = 0;
320  for ( auto it = mConnectedHashtable.constBegin(); it != mConnectedHashtable.constEnd(); ++it )
321  {
322  QVector<FeaturePart *> parts = it.value();
323  connectedFeaturesId++;
324 
325  // need to start with biggest parts first, to avoid merging in side branches before we've
326  // merged the whole of the longest parts of the joined network
327  std::sort( parts.begin(), parts.end(), []( FeaturePart * a, FeaturePart * b )
328  {
329  return a->length() > b->length();
330  } );
331 
332  // go one-by-one part, try to merge
333  while ( parts.count() > 1 )
334  {
335  // part we'll be checking against other in this round
336  FeaturePart *partCheck = parts.takeFirst();
337 
338  FeaturePart *otherPart = _findConnectedPart( partCheck, parts );
339  if ( otherPart )
340  {
341  // remove partCheck from r-tree
342  double checkpartBMin[2], checkpartBMax[2];
343  partCheck->getBoundingBox( checkpartBMin, checkpartBMax );
344 
345  double otherPartBMin[2], otherPartBMax[2];
346  otherPart->getBoundingBox( otherPartBMin, otherPartBMax );
347 
348  // merge points from partCheck to p->item
349  if ( otherPart->mergeWithFeaturePart( partCheck ) )
350  {
351  // remove the parts we are joining from the index
352  mFeatureIndex->Remove( checkpartBMin, checkpartBMax, partCheck );
353  mFeatureIndex->Remove( otherPartBMin, otherPartBMax, otherPart );
354 
355  // reinsert merged line to r-tree (probably not needed)
356  otherPart->getBoundingBox( otherPartBMin, otherPartBMax );
357  mFeatureIndex->Insert( otherPartBMin, otherPartBMax, otherPart );
358 
359  mConnectedFeaturesIds.insert( partCheck->featureId(), connectedFeaturesId );
360  mConnectedFeaturesIds.insert( otherPart->featureId(), connectedFeaturesId );
361 
362  mFeatureParts.removeOne( partCheck );
363  delete partCheck;
364  }
365  }
366  }
367  }
368  mConnectedHashtable.clear();
369 }
370 
372 {
373  return mConnectedFeaturesIds.value( featureId, -1 );
374 }
375 
377 {
378  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
379  QLinkedList<FeaturePart *> newFeatureParts;
380  while ( !mFeatureParts.isEmpty() )
381  {
382  std::unique_ptr< FeaturePart > fpart( mFeatureParts.takeFirst() );
383  const GEOSGeometry *geom = fpart->geos();
384  double chopInterval = fpart->repeatDistance();
385 
386  // whether we CAN chop
387  bool canChop = false;
388  double featureLen = 0;
389  if ( chopInterval != 0. && GEOSGeomTypeId_r( geosctxt, geom ) == GEOS_LINESTRING )
390  {
391  ( void )GEOSLength_r( geosctxt, geom, &featureLen );
392  if ( featureLen > chopInterval )
393  canChop = true;
394  }
395 
396  // whether we SHOULD chop
397  bool shouldChop = canChop;
398  int possibleSegments = 0;
399  if ( canChop )
400  {
401  // never chop into segments smaller than required for the actual label text
402  chopInterval *= std::ceil( fpart->getLabelWidth() / fpart->repeatDistance() );
403 
404  // now work out how many full segments we could chop this line into
405  possibleSegments = static_cast< int >( std::floor( featureLen / chopInterval ) );
406 
407  // ... and use this to work out the actual chop distance for this line. Otherwise, we risk the
408  // situation of:
409  // 1. Line length of 3cm
410  // 2. Repeat distance of 2cm
411  // 3. Label size is 1.5 cm
412  //
413  // 2cm 1cm
414  // /--Label--/----/
415  //
416  // i.e. the labels would be off center and gravitate toward line starts
417  chopInterval = featureLen / possibleSegments;
418 
419  shouldChop = possibleSegments > 1;
420  }
421 
422  if ( shouldChop )
423  {
424  double bmin[2], bmax[2];
425  fpart->getBoundingBox( bmin, bmax );
426  mFeatureIndex->Remove( bmin, bmax, fpart.get() );
427 
428  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( geosctxt, geom );
429 
430  // get number of points
431  unsigned int n;
432  GEOSCoordSeq_getSize_r( geosctxt, cs, &n );
433 
434  // Read points
435  std::vector<Point> points( n );
436  for ( unsigned int i = 0; i < n; ++i )
437  {
438  GEOSCoordSeq_getX_r( geosctxt, cs, i, &points[i].x );
439  GEOSCoordSeq_getY_r( geosctxt, cs, i, &points[i].y );
440  }
441 
442  // Cumulative length vector
443  std::vector<double> len( n, 0 );
444  for ( unsigned int i = 1; i < n; ++i )
445  {
446  double dx = points[i].x - points[i - 1].x;
447  double dy = points[i].y - points[i - 1].y;
448  len[i] = len[i - 1] + std::sqrt( dx * dx + dy * dy );
449  }
450 
451  // Walk along line
452  unsigned int cur = 0;
453  double lambda = 0;
454  QVector<Point> part;
455 
456  QList<FeaturePart *> repeatParts;
457  repeatParts.reserve( possibleSegments );
458 
459  for ( int segment = 0; segment < possibleSegments; segment++ )
460  {
461  lambda += chopInterval;
462  for ( ; cur < n && lambda > len[cur]; ++cur )
463  {
464  part.push_back( points[cur] );
465  }
466  if ( cur >= n )
467  {
468  // Create final part
469  GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
470  for ( int i = 0; i < part.size(); ++i )
471  {
472  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
473  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
474  }
475  GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
476  FeaturePart *newfpart = new FeaturePart( fpart->feature(), newgeom );
477  newFeatureParts.append( newfpart );
478  newfpart->getBoundingBox( bmin, bmax );
479  mFeatureIndex->Insert( bmin, bmax, newfpart );
480  repeatParts.push_back( newfpart );
481 
482  break;
483  }
484  double c = ( lambda - len[cur - 1] ) / ( len[cur] - len[cur - 1] );
485  Point p;
486  p.x = points[cur - 1].x + c * ( points[cur].x - points[cur - 1].x );
487  p.y = points[cur - 1].y + c * ( points[cur].y - points[cur - 1].y );
488  part.push_back( p );
489  GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
490  for ( int i = 0; i < part.size(); ++i )
491  {
492  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
493  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
494  }
495 
496  GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
497  FeaturePart *newfpart = new FeaturePart( fpart->feature(), newgeom );
498  newFeatureParts.append( newfpart );
499  newfpart->getBoundingBox( bmin, bmax );
500  mFeatureIndex->Insert( bmin, bmax, newfpart );
501  part.clear();
502  part.push_back( p );
503  repeatParts.push_back( newfpart );
504  }
505 
506  for ( FeaturePart *part : repeatParts )
507  part->setTotalRepeats( repeatParts.count() );
508  }
509  else
510  {
511  newFeatureParts.append( fpart.release() );
512  }
513  }
514 
515  mFeatureParts = newFeatureParts;
516 }
QList< FeaturePart * > mObstacleParts
List of obstacle parts.
Definition: layer.h:252
QHash< QgsFeatureId, int > mConnectedFeaturesIds
Definition: layer.h:280
QString labelText() const
Text of the label.
bool mMergeLines
Definition: layer.h:267
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)
bool mLabelLayer
Definition: layer.h:260
QHash< QgsFeatureId, QgsLabelFeature * > mHashtable
Lookup table of label features (owned by the label feature provider that created them) ...
Definition: layer.h:274
static QLinkedList< const GEOSGeometry * > * unmulti(const GEOSGeometry *the_geom)
Definition: util.cpp:87
virtual ~Layer()
Definition: layer.cpp:68
void setPriority(double priority)
Sets the layer&#39;s priority.
Definition: layer.cpp:81
double mDefaultPriority
Definition: layer.h:256
qint64 QgsFeatureId
Definition: qgsfeatureid.h:25
Main Pal labeling class.
Definition: pal.h:87
void chopFeaturesAtRepeatDistance()
Chop layer features at the repeat distance *.
Definition: layer.cpp:376
GEOSGeometry * geometry() const
Gets access to the associated geometry.
bool mergeWithFeaturePart(FeaturePart *other)
Merge other (connected) part with this one and save the result in this part (other is unchanged)...
Definition: feature.cpp:1764
bool isObstacle() const
Returns whether the feature will act as an obstacle for labels.
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:1748
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2825
QHash< QString, QVector< FeaturePart * > > mConnectedHashtable
Definition: layer.h:279
As part of the API refactoring and improvements which landed in the Processing API was substantially reworked from the x version This was done in order to allow much of the underlying Processing framework to be ported into c
double priority() const
Returns the layer&#39;s priority, between 0 and 1.
Definition: layer.h:176
RTree< FeaturePart *, double, 2, double, 8, 4 > * mFeatureIndex
Definition: layer.h:272
void joinConnectedFeatures()
Join connected features with the same label text.
Definition: layer.cpp:316
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:143
void addObstaclePart(FeaturePart *fpart)
Add newly created obstacle part into r tree and to the list.
Definition: layer.cpp:286
void setLayer(pal::Layer *layer)
Assign PAL layer to the label feature. Should be only used internally in PAL.
Layer(QgsAbstractLabelProvider *provider, const QString &name, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, Pal *pal, bool displayAll=false)
Create a new layer.
Definition: layer.cpp:44
double x
Definition: util.h:72
Main class to handle feature.
Definition: feature.h:96
The QgsAbstractLabelProvider class is an interface class.
Thrown when a geometry type is not like expected.
bool registerFeature(QgsLabelFeature *label)
Register a feature in the layer.
Definition: layer.cpp:91
double y
Definition: util.h:72
Placement
Placement modes which determine how label candidates are generated for a feature. ...
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.
The QgsLabelFeature class describes a feature that should be used within the labeling engine...
double length() const
Returns length of line geometry.
Definition: pointset.cpp:908
GEOSGeometry * obstacleGeometry() const
Returns the label&#39;s obstacle geometry, if different to the feature geometry.
QLinkedList< FeaturePart * > mFeatureParts
List of feature parts.
Definition: layer.h:249
RTree< FeaturePart *, double, 2, double, 8, 4 > * mObstacleIndex
Definition: layer.h:277
QMutex mMutex
Definition: layer.h:282
QSizeF size(double angle=0.0) const
Size of the label (in map units)
friend class FeaturePart
Definition: layer.h:66
bool labelAllParts() const
Returns true if all parts of the feature should be labeled.
void addFeaturePart(FeaturePart *fpart, const QString &labelText=QString())
Add newly created feature part into r tree and to the list.
Definition: layer.cpp:267
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