QGIS API Documentation  3.2.0-Bonn (bc43194)
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  , mArrangementFlags( nullptr )
55  , mMode( LabelPerFeature )
56  , mMergeLines( false )
57  , mUpsidedownLabels( Upright )
58 {
59  mFeatureIndex = new RTree<FeaturePart *, double, 2, double>();
60  mObstacleIndex = new RTree<FeaturePart *, double, 2, double>();
61 
62  if ( defaultPriority < 0.0001 )
63  mDefaultPriority = 0.0001;
64  else if ( defaultPriority > 1.0 )
65  mDefaultPriority = 1.0;
66  else
67  mDefaultPriority = defaultPriority;
68 }
69 
71 {
72  mMutex.lock();
73 
74  qDeleteAll( mFeatureParts );
75  qDeleteAll( mObstacleParts );
76 
77  //should already be empty
78  qDeleteAll( mConnectedHashtable );
79 
80  delete mFeatureIndex;
81  delete mObstacleIndex;
82 
83  mMutex.unlock();
84 }
85 
87 {
88  if ( priority >= 1.0 ) // low priority
89  mDefaultPriority = 1.0;
90  else if ( priority <= 0.0001 )
91  mDefaultPriority = 0.0001; // high priority
92  else
94 }
95 
97 {
98  if ( lf->size().width() < 0 || lf->size().height() < 0 )
99  return false;
100 
101  mMutex.lock();
102 
103  if ( mHashtable.contains( lf->id() ) )
104  {
105  mMutex.unlock();
106  //A feature with this id already exists. Don't throw an exception as sometimes,
107  //the same feature is added twice (dateline split with otf-reprojection)
108  return false;
109  }
110 
111  // assign label feature to this PAL layer
112  lf->setLayer( this );
113 
114  // Split MULTI GEOM and Collection in simple geometries
115 
116  bool addedFeature = false;
117 
118  double geom_size = -1, biggest_size = -1;
119  FeaturePart *biggest_part = nullptr;
120 
121  // break the (possibly multi-part) geometry into simple geometries
122  QLinkedList<const GEOSGeometry *> *simpleGeometries = Util::unmulti( lf->geometry() );
123  if ( !simpleGeometries ) // unmulti() failed?
124  {
125  mMutex.unlock();
127  }
128 
129  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
130 
131  bool featureGeomIsObstacleGeom = !lf->obstacleGeometry();
132 
133  while ( !simpleGeometries->isEmpty() )
134  {
135  const GEOSGeometry *geom = simpleGeometries->takeFirst();
136 
137  // ignore invalid geometries (e.g. polygons with self-intersecting rings)
138  if ( GEOSisValid_r( geosctxt, geom ) != 1 ) // 0=invalid, 1=valid, 2=exception
139  {
140  continue;
141  }
142 
143  int type = GEOSGeomTypeId_r( geosctxt, geom );
144 
145  if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
146  {
147  mMutex.unlock();
149  }
150 
151  FeaturePart *fpart = new FeaturePart( lf, geom );
152 
153  // ignore invalid geometries
154  if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
155  ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
156  {
157  delete fpart;
158  continue;
159  }
160 
161  // polygons: reorder coordinates
162  if ( type == GEOS_POLYGON && GeomFunction::reorderPolygon( fpart->nbPoints, fpart->x, fpart->y ) != 0 )
163  {
164  delete fpart;
165  continue;
166  }
167 
168  // is the feature well defined? TODO Check epsilon
169  bool labelWellDefined = ( lf->size().width() > 0.0000001 && lf->size().height() > 0.0000001 );
170 
171  if ( lf->isObstacle() && featureGeomIsObstacleGeom )
172  {
173  //if we are not labeling the layer, only insert it into the obstacle list and avoid an
174  //unnecessary copy
175  if ( mLabelLayer && labelWellDefined )
176  {
177  addObstaclePart( new FeaturePart( *fpart ) );
178  }
179  else
180  {
181  addObstaclePart( fpart );
182  fpart = nullptr;
183  }
184  }
185 
186  // feature has to be labeled?
187  if ( !mLabelLayer || !labelWellDefined )
188  {
189  //nothing more to do for this part
190  delete fpart;
191  continue;
192  }
193 
194  if ( mMode == LabelPerFeature && ( type == GEOS_POLYGON || type == GEOS_LINESTRING ) )
195  {
196  if ( type == GEOS_LINESTRING )
197  GEOSLength_r( geosctxt, geom, &geom_size );
198  else if ( type == GEOS_POLYGON )
199  GEOSArea_r( geosctxt, geom, &geom_size );
200 
201  if ( geom_size > biggest_size )
202  {
203  biggest_size = geom_size;
204  delete biggest_part; // safe with NULL part
205  biggest_part = fpart;
206  }
207  else
208  {
209  delete fpart;
210  }
211  continue; // don't add the feature part now, do it later
212  }
213 
214  // feature part is ready!
215  addFeaturePart( fpart, lf->labelText() );
216  addedFeature = true;
217  }
218  delete simpleGeometries;
219 
220  if ( !featureGeomIsObstacleGeom )
221  {
222  //do the same for the obstacle geometry
223  simpleGeometries = Util::unmulti( lf->obstacleGeometry() );
224  if ( !simpleGeometries ) // unmulti() failed?
225  {
226  mMutex.unlock();
228  }
229 
230  while ( !simpleGeometries->isEmpty() )
231  {
232  const GEOSGeometry *geom = simpleGeometries->takeFirst();
233 
234  // ignore invalid geometries (e.g. polygons with self-intersecting rings)
235  if ( GEOSisValid_r( geosctxt, geom ) != 1 ) // 0=invalid, 1=valid, 2=exception
236  {
237  continue;
238  }
239 
240  int type = GEOSGeomTypeId_r( geosctxt, geom );
241 
242  if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
243  {
244  mMutex.unlock();
246  }
247 
248  FeaturePart *fpart = new FeaturePart( lf, geom );
249 
250  // ignore invalid geometries
251  if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
252  ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
253  {
254  delete fpart;
255  continue;
256  }
257 
258  // polygons: reorder coordinates
259  if ( type == GEOS_POLYGON && GeomFunction::reorderPolygon( fpart->nbPoints, fpart->x, fpart->y ) != 0 )
260  {
261  delete fpart;
262  continue;
263  }
264 
265  // feature part is ready!
266  addObstaclePart( fpart );
267  }
268  delete simpleGeometries;
269  }
270 
271  mMutex.unlock();
272 
273  // if using only biggest parts...
274  if ( ( mMode == LabelPerFeature || lf->hasFixedPosition() ) && biggest_part )
275  {
276  addFeaturePart( biggest_part, lf->labelText() );
277  addedFeature = true;
278  }
279 
280  // add feature to layer if we have added something
281  if ( addedFeature )
282  {
283  mHashtable.insert( lf->id(), lf );
284  }
285 
286  return addedFeature; // true if we've added something
287 }
288 
289 
290 void Layer::addFeaturePart( FeaturePart *fpart, const QString &labelText )
291 {
292  double bmin[2];
293  double bmax[2];
294  fpart->getBoundingBox( bmin, bmax );
295 
296  // add to list of layer's feature parts
297  mFeatureParts << fpart;
298 
299  // add to r-tree for fast spatial access
300  mFeatureIndex->Insert( bmin, bmax, fpart );
301 
302  // add to hashtable with equally named feature parts
303  if ( mMergeLines && !labelText.isEmpty() )
304  {
305  QLinkedList< FeaturePart *> *lst;
306  if ( !mConnectedHashtable.contains( labelText ) )
307  {
308  // entry doesn't exist yet
309  lst = new QLinkedList<FeaturePart *>;
310  mConnectedHashtable.insert( labelText, lst );
311  mConnectedTexts << labelText;
312  }
313  else
314  {
315  lst = mConnectedHashtable.value( labelText );
316  }
317  lst->append( fpart ); // add to the list
318  }
319 }
320 
322 {
323  double bmin[2];
324  double bmax[2];
325  fpart->getBoundingBox( bmin, bmax );
326 
327  // add to list of layer's feature parts
328  mObstacleParts.append( fpart );
329 
330  // add to obstacle r-tree
331  mObstacleIndex->Insert( bmin, bmax, fpart );
332 }
333 
334 static FeaturePart *_findConnectedPart( FeaturePart *partCheck, QLinkedList<FeaturePart *> *otherParts )
335 {
336  // iterate in the rest of the parts with the same label
337  QLinkedList<FeaturePart *>::const_iterator p = otherParts->constBegin();
338  while ( p != otherParts->constEnd() )
339  {
340  if ( partCheck->isConnected( *p ) )
341  {
342  // stop checking for other connected parts
343  return *p;
344  }
345  ++p;
346  }
347 
348  return nullptr; // no connected part found...
349 }
350 
352 {
353  // go through all label texts
354  int connectedFeaturesId = 0;
355  Q_FOREACH ( const QString &labelText, mConnectedTexts )
356  {
357  if ( !mConnectedHashtable.contains( labelText ) )
358  continue; // shouldn't happen
359 
360  connectedFeaturesId++;
361 
362  QLinkedList<FeaturePart *> *parts = mConnectedHashtable.value( labelText );
363 
364  // go one-by-one part, try to merge
365  while ( !parts->isEmpty() && parts->count() > 1 )
366  {
367  // part we'll be checking against other in this round
368  FeaturePart *partCheck = parts->takeFirst();
369 
370  FeaturePart *otherPart = _findConnectedPart( partCheck, parts );
371  if ( otherPart )
372  {
373  // remove partCheck from r-tree
374  double checkpartBMin[2], checkpartBMax[2];
375  partCheck->getBoundingBox( checkpartBMin, checkpartBMax );
376 
377  double otherPartBMin[2], otherPartBMax[2];
378  otherPart->getBoundingBox( otherPartBMin, otherPartBMax );
379 
380  // merge points from partCheck to p->item
381  if ( otherPart->mergeWithFeaturePart( partCheck ) )
382  {
383  // remove the parts we are joining from the index
384  mFeatureIndex->Remove( checkpartBMin, checkpartBMax, partCheck );
385  mFeatureIndex->Remove( otherPartBMin, otherPartBMax, otherPart );
386 
387  // reinsert merged line to r-tree (probably not needed)
388  otherPart->getBoundingBox( otherPartBMin, otherPartBMax );
389  mFeatureIndex->Insert( otherPartBMin, otherPartBMax, otherPart );
390 
391  mConnectedFeaturesIds.insert( partCheck->featureId(), connectedFeaturesId );
392  mConnectedFeaturesIds.insert( otherPart->featureId(), connectedFeaturesId );
393 
394  mFeatureParts.removeOne( partCheck );
395  delete partCheck;
396  }
397  }
398  }
399 
400  // we're done processing feature parts with this particular label text
401  delete parts;
402  mConnectedHashtable.remove( labelText );
403  }
404 
405  // we're done processing connected features
406 
407  //should be empty, but clear to be safe
408  qDeleteAll( mConnectedHashtable );
409  mConnectedHashtable.clear();
410 
411  mConnectedTexts.clear();
412 }
413 
415 {
416  return mConnectedFeaturesIds.value( featureId, -1 );
417 }
418 
420 {
421  GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
422  QLinkedList<FeaturePart *> newFeatureParts;
423  while ( !mFeatureParts.isEmpty() )
424  {
425  FeaturePart *fpart = mFeatureParts.takeFirst();
426  const GEOSGeometry *geom = fpart->geos();
427  double chopInterval = fpart->repeatDistance();
428  if ( chopInterval != 0. && GEOSGeomTypeId_r( geosctxt, geom ) == GEOS_LINESTRING )
429  {
430  chopInterval *= std::ceil( fpart->getLabelWidth() / fpart->repeatDistance() );
431 
432  double bmin[2], bmax[2];
433  fpart->getBoundingBox( bmin, bmax );
434  mFeatureIndex->Remove( bmin, bmax, fpart );
435 
436  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( geosctxt, geom );
437 
438  // get number of points
439  unsigned int n;
440  GEOSCoordSeq_getSize_r( geosctxt, cs, &n );
441 
442  // Read points
443  std::vector<Point> points( n );
444  for ( unsigned int i = 0; i < n; ++i )
445  {
446  GEOSCoordSeq_getX_r( geosctxt, cs, i, &points[i].x );
447  GEOSCoordSeq_getY_r( geosctxt, cs, i, &points[i].y );
448  }
449 
450  // Cumulative length vector
451  std::vector<double> len( n, 0 );
452  for ( unsigned int i = 1; i < n; ++i )
453  {
454  double dx = points[i].x - points[i - 1].x;
455  double dy = points[i].y - points[i - 1].y;
456  len[i] = len[i - 1] + std::sqrt( dx * dx + dy * dy );
457  }
458 
459  // Walk along line
460  unsigned int cur = 0;
461  double lambda = 0;
462  QVector<Point> part;
463  for ( ;; )
464  {
465  lambda += chopInterval;
466  for ( ; cur < n && lambda > len[cur]; ++cur )
467  {
468  part.push_back( points[cur] );
469  }
470  if ( cur >= n )
471  {
472  break;
473  }
474  double c = ( lambda - len[cur - 1] ) / ( len[cur] - len[cur - 1] );
475  Point p;
476  p.x = points[cur - 1].x + c * ( points[cur].x - points[cur - 1].x );
477  p.y = points[cur - 1].y + c * ( points[cur].y - points[cur - 1].y );
478  part.push_back( p );
479  GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
480  for ( int i = 0; i < part.size(); ++i )
481  {
482  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
483  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
484  }
485 
486  GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
487  FeaturePart *newfpart = new FeaturePart( fpart->feature(), newgeom );
488  newFeatureParts.append( newfpart );
489  newfpart->getBoundingBox( bmin, bmax );
490  mFeatureIndex->Insert( bmin, bmax, newfpart );
491  part.clear();
492  part.push_back( p );
493  }
494  // Create final part
495  part.push_back( points[n - 1] );
496  GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
497  for ( int i = 0; i < part.size(); ++i )
498  {
499  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
500  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
501  }
502 
503  GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
504  FeaturePart *newfpart = new FeaturePart( fpart->feature(), newgeom );
505  newFeatureParts.append( newfpart );
506  newfpart->getBoundingBox( bmin, bmax );
507  mFeatureIndex->Insert( bmin, bmax, newfpart );
508  delete fpart;
509  }
510  else
511  {
512  newFeatureParts.append( fpart );
513  }
514  }
515 
516  mFeatureParts = newFeatureParts;
517 }
QList< FeaturePart * > mObstacleParts
List of obstacle parts.
Definition: layer.h:279
QHash< QgsFeatureId, int > mConnectedFeaturesIds
Definition: layer.h:309
QString labelText() const
Text of the label.
bool mMergeLines
Definition: layer.h:295
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)
QgsLabelFeature * feature()
Returns the parent feature.
Definition: feature.h:118
bool mLabelLayer
Definition: layer.h:287
QStringList mConnectedTexts
Definition: layer.h:308
QHash< QgsFeatureId, QgsLabelFeature * > mHashtable
Lookup table of label features (owned by the label feature provider that created them) ...
Definition: layer.h:302
static QLinkedList< const GEOSGeometry * > * unmulti(const GEOSGeometry *the_geom)
Definition: util.cpp:87
virtual ~Layer()
Definition: layer.cpp:70
void setPriority(double priority)
Sets the layer&#39;s priority.
Definition: layer.cpp:86
double mDefaultPriority
Definition: layer.h:283
Main Pal labeling class.
Definition: pal.h:87
void chopFeaturesAtRepeatDistance()
Chop layer features at the repeat distance *.
Definition: layer.cpp:419
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:1673
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:1657
static GEOSContextHandle_t getGEOSHandler()
Definition: qgsgeos.cpp:2775
double repeatDistance() const
Returns the distance between repeating labels for this feature.
Definition: feature.h:274
QHash< QString, QLinkedList< FeaturePart * > *> mConnectedHashtable
Definition: layer.h:307
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:190
RTree< FeaturePart *, double, 2, double, 8, 4 > * mFeatureIndex
Definition: layer.h:300
void joinConnectedFeatures()
Join connected features with the same label text.
Definition: layer.cpp:351
double * x
Definition: pointset.h:169
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:126
void addObstaclePart(FeaturePart *fpart)
Add newly created obstacle part into r tree and to the list.
Definition: layer.cpp:321
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.
QSizeF size() const
Size of the label (in map units)
double * y
Definition: pointset.h:170
bool registerFeature(QgsLabelFeature *label)
Register a feature in the layer.
Definition: layer.cpp:96
double y
Definition: util.h:72
Placement
Placement modes which determine how label candidates are generated for a feature. ...
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...
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:276
RTree< FeaturePart *, double, 2, double, 8, 4 > * mObstacleIndex
Definition: layer.h:305
QMutex mMutex
Definition: layer.h:311
double getLabelWidth() const
Definition: feature.h:245
LabelMode mMode
Definition: layer.h:294
qint64 QgsFeatureId
Definition: qgsfeature.h:37
static int reorderPolygon(int nbPoints, double *x, double *y)
Reorder points to have cross prod ((x,y)[i], (x,y)[i+1), point) > 0 when point is outside...
const GEOSGeometry * geos() const
Returns the point set&#39;s GEOS geometry.
Definition: pointset.cpp:819
friend class FeaturePart
Definition: layer.h:66
void addFeaturePart(FeaturePart *fpart, const QString &labelText=QString())
Add newly created feature part into r tree and to the list.
Definition: layer.cpp:290
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:414