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