QGIS API Documentation  2.15.0-Master (94d88e6)
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  , mFitInPolygon( false )
53  , mArrangement( arrangement )
54  , mArrangementFlags( nullptr )
55  , mMode( LabelPerFeature )
56  , mMergeLines( false )
57  , mUpsidedownLabels( Upright )
58 {
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 = geosContext();
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 labelling 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  {
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 
335 {
336  // iterate in the rest of the parts with the same label
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() )
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 bmin[2], bmax[2];
375  partCheck->getBoundingBox( bmin, bmax );
376  mFeatureIndex->Remove( bmin, bmax, partCheck );
377  mFeatureParts.removeOne( partCheck );
378 
379  mConnectedFeaturesIds.insert( partCheck->featureId(), connectedFeaturesId );
380  otherPart->getBoundingBox( bmin, bmax );
381 
382  // merge points from partCheck to p->item
383  if ( otherPart->mergeWithFeaturePart( partCheck ) )
384  {
385  mConnectedFeaturesIds.insert( otherPart->featureId(), connectedFeaturesId );
386  // reinsert p->item to r-tree (probably not needed)
387  mFeatureIndex->Remove( bmin, bmax, otherPart );
388  otherPart->getBoundingBox( bmin, bmax );
389  mFeatureIndex->Insert( bmin, bmax, otherPart );
390  }
391  delete partCheck;
392  }
393  }
394 
395  // we're done processing feature parts with this particular label text
396  delete parts;
397  mConnectedHashtable.remove( labelText );
398  }
399 
400  // we're done processing connected features
401 
402  //should be empty, but clear to be safe
403  qDeleteAll( mConnectedHashtable );
404  mConnectedHashtable.clear();
405 
407 }
408 
410 {
411  return mConnectedFeaturesIds.value( featureId, -1 );
412 }
413 
415 {
416  GEOSContextHandle_t geosctxt = geosContext();
417  QLinkedList<FeaturePart*> newFeatureParts;
418  while ( !mFeatureParts.isEmpty() )
419  {
420  FeaturePart* fpart = mFeatureParts.takeFirst();
421  const GEOSGeometry* geom = fpart->geos();
422  double chopInterval = fpart->repeatDistance();
423  if ( chopInterval != 0. && GEOSGeomTypeId_r( geosctxt, geom ) == GEOS_LINESTRING )
424  {
425 
426  double bmin[2], bmax[2];
427  fpart->getBoundingBox( bmin, bmax );
428  mFeatureIndex->Remove( bmin, bmax, fpart );
429 
430  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( geosctxt, geom );
431 
432  // get number of points
433  unsigned int n;
434  GEOSCoordSeq_getSize_r( geosctxt, cs, &n );
435 
436  // Read points
437  std::vector<Point> points( n );
438  for ( unsigned int i = 0; i < n; ++i )
439  {
440  GEOSCoordSeq_getX_r( geosctxt, cs, i, &points[i].x );
441  GEOSCoordSeq_getY_r( geosctxt, cs, i, &points[i].y );
442  }
443 
444  // Cumulative length vector
445  std::vector<double> len( n, 0 );
446  for ( unsigned int i = 1; i < n; ++i )
447  {
448  double dx = points[i].x - points[i - 1].x;
449  double dy = points[i].y - points[i - 1].y;
450  len[i] = len[i - 1] + std::sqrt( dx * dx + dy * dy );
451  }
452 
453  // Walk along line
454  unsigned int cur = 0;
455  double lambda = 0;
456  QVector<Point> part;
457  for ( ;; )
458  {
459  lambda += chopInterval;
460  for ( ; cur < n && lambda > len[cur]; ++cur )
461  {
462  part.push_back( points[cur] );
463  }
464  if ( cur >= n )
465  {
466  break;
467  }
468  double c = ( lambda - len[cur - 1] ) / ( len[cur] - len[cur - 1] );
469  Point p;
470  p.x = points[cur - 1].x + c * ( points[cur].x - points[cur - 1].x );
471  p.y = points[cur - 1].y + c * ( points[cur].y - points[cur - 1].y );
472  part.push_back( p );
473  GEOSCoordSequence* cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
474  for ( int i = 0; i < part.size(); ++i )
475  {
476  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
477  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
478  }
479 
480  GEOSGeometry* newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
481  FeaturePart* newfpart = new FeaturePart( fpart->feature(), newgeom );
482  newFeatureParts.append( newfpart );
483  newfpart->getBoundingBox( bmin, bmax );
484  mFeatureIndex->Insert( bmin, bmax, newfpart );
485  part.clear();
486  part.push_back( p );
487  }
488  // Create final part
489  part.push_back( points[n - 1] );
490  GEOSCoordSequence* cooSeq = GEOSCoordSeq_create_r( geosctxt, part.size(), 2 );
491  for ( int i = 0; i < part.size(); ++i )
492  {
493  GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
494  GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
495  }
496 
497  GEOSGeometry* newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
498  FeaturePart* newfpart = new FeaturePart( fpart->feature(), newgeom );
499  newFeatureParts.append( newfpart );
500  newfpart->getBoundingBox( bmin, bmax );
501  mFeatureIndex->Insert( bmin, bmax, newfpart );
502  delete fpart;
503  }
504  else
505  {
506  newFeatureParts.append( fpart );
507  }
508  }
509 
510  mFeatureParts = newFeatureParts;
511 }
void clear()
QHash< QgsFeatureId, int > mConnectedFeaturesIds
Definition: layer.h:289
bool mMergeLines
Definition: layer.h:275
iterator insert(const Key &key, const T &value)
QgsLabelFeature * feature()
Returns the parent feature.
Definition: feature.h:109
bool mLabelLayer
Definition: layer.h:266
QLinkedList< FeaturePart * > mFeatureParts
List of feature parts.
Definition: layer.h:255
QStringList mConnectedTexts
Definition: layer.h:288
static QLinkedList< const GEOSGeometry * > * unmulti(const GEOSGeometry *the_geom)
Definition: util.cpp:97
virtual ~Layer()
Definition: layer.cpp:70
QHash< QgsFeatureId, QgsLabelFeature * > mHashtable
Lookup table of label features (owned by the label feature provider that created them) ...
Definition: layer.h:282
void setPriority(double priority)
Sets the layer&#39;s priority.
Definition: layer.cpp:86
const GEOSGeometry * geos() const
Returns the point set&#39;s GEOS geometry.
Definition: pointset.cpp:893
double mDefaultPriority
Definition: layer.h:262
Main Pal labelling class.
Definition: pal.h:84
void chopFeaturesAtRepeatDistance()
Chop layer features at the repeat distance.
Definition: layer.cpp:414
double priority() const
Returns the layer&#39;s priority, between 0 and 1.
Definition: layer.h:164
bool mergeWithFeaturePart(FeaturePart *other)
Merge other (connected) part with this one and save the result in this part (other is unchanged)...
Definition: feature.cpp:1446
void unlock()
bool isConnected(FeaturePart *p2)
Check whether this part is connected with some other part.
Definition: feature.cpp:1430
bool isObstacle() const
Returns whether the feature will act as an obstacle for labels.
double repeatDistance()
Definition: feature.h:207
GEOSGeometry * geometry() const
Get access to the associated geometry.
QSizeF size() const
Size of the label (in map units)
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:351
double * x
Definition: pointset.h:152
void addObstaclePart(FeaturePart *fpart)
Add newly created obstacle part into r tree and to the list.
Definition: layer.cpp:321
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:74
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:258
Main class to handle feature.
Definition: feature.h:90
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:285
void lock()
double * y
Definition: pointset.h:153
void getBoundingBox(double min[2], double max[2]) const
Definition: pointset.h:117
const_iterator constBegin() const
const_iterator constEnd() const
bool registerFeature(QgsLabelFeature *label)
Register a feature in the layer.
Definition: layer.cpp:96
double y
Definition: util.h:74
Placement
Placement modes which determine how label candidates are generated for a feature. ...
QHash< QString, QLinkedList< FeaturePart * > * > mConnectedHashtable
Definition: layer.h:287
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:409
RTree< FeaturePart *, double, 2, double, 8, 4 > * mFeatureIndex
Definition: layer.h:280
static FeaturePart * _findConnectedPart(FeaturePart *partCheck, QLinkedList< FeaturePart * > *otherParts)
Definition: layer.cpp:334
QMutex mMutex
Definition: layer.h:291
LabelMode mMode
Definition: layer.h:274
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:58
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:290
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:154