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