Branch data Line data Source code
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 : : #include "qgslogger.h"
39 : :
40 : : #include <cmath>
41 : : #include <vector>
42 : :
43 : : using namespace pal;
44 : :
45 : 0 : Layer::Layer( QgsAbstractLabelProvider *provider, const QString &name, QgsPalLayerSettings::Placement arrangement, double defaultPriority, bool active, bool toLabel, Pal *pal, bool displayAll )
46 : 0 : : mProvider( provider )
47 : 0 : , mName( name )
48 : 0 : , mPal( pal )
49 : 0 : , mActive( active )
50 : 0 : , mLabelLayer( toLabel )
51 : 0 : , mDisplayAll( displayAll )
52 : 0 : , mCentroidInside( false )
53 : 0 : , mArrangement( arrangement )
54 : 0 : , mMergeLines( false )
55 : 0 : , mUpsidedownLabels( Upright )
56 : 0 : {
57 : 0 : if ( defaultPriority < 0.0001 )
58 : 0 : mDefaultPriority = 0.0001;
59 : 0 : else if ( defaultPriority > 1.0 )
60 : 0 : mDefaultPriority = 1.0;
61 : : else
62 : 0 : mDefaultPriority = defaultPriority;
63 : 0 : }
64 : :
65 : 0 : Layer::~Layer()
66 : 0 : {
67 : 0 : mMutex.lock();
68 : :
69 : 0 : qDeleteAll( mObstacleParts );
70 : :
71 : 0 : mMutex.unlock();
72 : 0 : }
73 : :
74 : 0 : void Layer::setPriority( double priority )
75 : : {
76 : 0 : if ( priority >= 1.0 ) // low priority
77 : 0 : mDefaultPriority = 1.0;
78 : 0 : else if ( priority <= 0.0001 )
79 : 0 : mDefaultPriority = 0.0001; // high priority
80 : : else
81 : 0 : mDefaultPriority = priority;
82 : 0 : }
83 : :
84 : 0 : bool Layer::registerFeature( QgsLabelFeature *lf )
85 : : {
86 : 0 : if ( lf->size().width() < 0 || lf->size().height() < 0 )
87 : 0 : return false;
88 : :
89 : 0 : QMutexLocker locker( &mMutex );
90 : :
91 : 0 : if ( mHashtable.contains( lf->id() ) )
92 : : {
93 : : //A feature with this id already exists. Don't throw an exception as sometimes,
94 : : //the same feature is added twice (dateline split with otf-reprojection)
95 : 0 : return false;
96 : : }
97 : :
98 : : // assign label feature to this PAL layer
99 : 0 : lf->setLayer( this );
100 : :
101 : : // Split MULTI GEOM and Collection in simple geometries
102 : :
103 : 0 : bool addedFeature = false;
104 : :
105 : 0 : double geom_size = -1, biggest_size = -1;
106 : 0 : std::unique_ptr<FeaturePart> biggestPart;
107 : :
108 : : // break the (possibly multi-part) geometry into simple geometries
109 : 0 : std::unique_ptr<QLinkedList<const GEOSGeometry *>> simpleGeometries( Util::unmulti( lf->geometry() ) );
110 : 0 : if ( !simpleGeometries ) // unmulti() failed?
111 : : {
112 : 0 : throw InternalException::UnknownGeometry();
113 : : }
114 : :
115 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
116 : :
117 : 0 : bool featureGeomIsObstacleGeom = lf->obstacleSettings().obstacleGeometry().isNull();
118 : :
119 : 0 : while ( !simpleGeometries->isEmpty() )
120 : : {
121 : 0 : const GEOSGeometry *geom = simpleGeometries->takeFirst();
122 : :
123 : : // ignore invalid geometries (e.g. polygons with self-intersecting rings)
124 : 0 : if ( GEOSisValid_r( geosctxt, geom ) != 1 ) // 0=invalid, 1=valid, 2=exception
125 : : {
126 : 0 : continue;
127 : : }
128 : :
129 : 0 : int type = GEOSGeomTypeId_r( geosctxt, geom );
130 : :
131 : 0 : if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
132 : : {
133 : 0 : throw InternalException::UnknownGeometry();
134 : : }
135 : :
136 : 0 : std::unique_ptr<FeaturePart> fpart = std::make_unique<FeaturePart>( lf, geom );
137 : :
138 : : // ignore invalid geometries
139 : 0 : if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
140 : 0 : ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
141 : : {
142 : 0 : continue;
143 : : }
144 : :
145 : : // polygons: reorder coordinates
146 : 0 : if ( type == GEOS_POLYGON && !GeomFunction::reorderPolygon( fpart->x, fpart->y ) )
147 : : {
148 : 0 : continue;
149 : : }
150 : :
151 : : // is the feature well defined? TODO Check epsilon
152 : 0 : bool labelWellDefined = ( lf->size().width() > 0.0000001 && lf->size().height() > 0.0000001 );
153 : :
154 : 0 : if ( lf->obstacleSettings().isObstacle() && featureGeomIsObstacleGeom )
155 : : {
156 : : //if we are not labeling the layer, only insert it into the obstacle list and avoid an
157 : : //unnecessary copy
158 : 0 : if ( mLabelLayer && labelWellDefined )
159 : : {
160 : 0 : addObstaclePart( new FeaturePart( *fpart ) );
161 : 0 : }
162 : : else
163 : : {
164 : 0 : addObstaclePart( fpart.release() );
165 : : }
166 : 0 : }
167 : :
168 : : // feature has to be labeled?
169 : 0 : if ( !mLabelLayer || !labelWellDefined )
170 : : {
171 : : //nothing more to do for this part
172 : 0 : continue;
173 : : }
174 : :
175 : 0 : if ( !lf->labelAllParts() && ( type == GEOS_POLYGON || type == GEOS_LINESTRING ) )
176 : : {
177 : 0 : if ( type == GEOS_LINESTRING )
178 : 0 : geom_size = fpart->length();
179 : 0 : else if ( type == GEOS_POLYGON )
180 : 0 : geom_size = fpart->area();
181 : :
182 : 0 : if ( geom_size > biggest_size )
183 : : {
184 : 0 : biggest_size = geom_size;
185 : 0 : biggestPart = std::move( fpart );
186 : 0 : }
187 : : // don't add the feature part now, do it later
188 : 0 : }
189 : : else
190 : : {
191 : : // feature part is ready!
192 : 0 : addFeaturePart( std::move( fpart ), lf->labelText() );
193 : 0 : addedFeature = true;
194 : : }
195 : 0 : }
196 : :
197 : 0 : if ( lf->obstacleSettings().isObstacle() && !featureGeomIsObstacleGeom )
198 : : {
199 : : //do the same for the obstacle geometry
200 : 0 : const QgsGeometry obstacleGeometry = lf->obstacleSettings().obstacleGeometry();
201 : 0 : for ( auto it = obstacleGeometry.const_parts_begin(); it != obstacleGeometry.const_parts_end(); ++it )
202 : : {
203 : 0 : geos::unique_ptr geom = QgsGeos::asGeos( *it );
204 : :
205 : 0 : if ( !geom )
206 : : {
207 : 0 : QgsDebugMsg( QStringLiteral( "Obstacle geometry passed to PAL labeling engine could not be converted to GEOS! %1" ).arg( ( *it )->asWkt() ) );
208 : 0 : continue;
209 : : }
210 : :
211 : : // ignore invalid geometries (e.g. polygons with self-intersecting rings)
212 : 0 : if ( GEOSisValid_r( geosctxt, geom.get() ) != 1 ) // 0=invalid, 1=valid, 2=exception
213 : : {
214 : : // this shouldn't happen -- we have already checked this while registering the feature
215 : 0 : QgsDebugMsg( QStringLiteral( "Obstacle geometry passed to PAL labeling engine is not valid! %1" ).arg( ( *it )->asWkt() ) );
216 : 0 : continue;
217 : : }
218 : :
219 : 0 : int type = GEOSGeomTypeId_r( geosctxt, geom.get() );
220 : :
221 : 0 : if ( type != GEOS_POINT && type != GEOS_LINESTRING && type != GEOS_POLYGON )
222 : : {
223 : 0 : throw InternalException::UnknownGeometry();
224 : : }
225 : :
226 : 0 : std::unique_ptr<FeaturePart> fpart = std::make_unique<FeaturePart>( lf, geom.get() );
227 : :
228 : : // ignore invalid geometries
229 : 0 : if ( ( type == GEOS_LINESTRING && fpart->nbPoints < 2 ) ||
230 : 0 : ( type == GEOS_POLYGON && fpart->nbPoints < 3 ) )
231 : : {
232 : 0 : continue;
233 : : }
234 : :
235 : : // polygons: reorder coordinates
236 : 0 : if ( type == GEOS_POLYGON && !GeomFunction::reorderPolygon( fpart->x, fpart->y ) )
237 : : {
238 : 0 : continue;
239 : : }
240 : :
241 : 0 : mGeosObstacleGeometries.emplace_back( std::move( geom ) );
242 : :
243 : : // feature part is ready!
244 : 0 : addObstaclePart( fpart.release() );
245 : 0 : }
246 : 0 : }
247 : :
248 : 0 : locker.unlock();
249 : :
250 : : // if using only biggest parts...
251 : 0 : if ( ( !lf->labelAllParts() || lf->hasFixedPosition() ) && biggestPart )
252 : : {
253 : 0 : addFeaturePart( std::move( biggestPart ), lf->labelText() );
254 : 0 : addedFeature = true;
255 : 0 : }
256 : :
257 : : // add feature to layer if we have added something
258 : 0 : if ( addedFeature )
259 : : {
260 : 0 : mHashtable.insert( lf->id(), lf );
261 : 0 : }
262 : :
263 : 0 : return addedFeature; // true if we've added something
264 : 0 : }
265 : :
266 : :
267 : 0 : void Layer::addFeaturePart( std::unique_ptr<FeaturePart> fpart, const QString &labelText )
268 : : {
269 : : // add to hashtable with equally named feature parts
270 : 0 : if ( mMergeLines && !labelText.isEmpty() )
271 : : {
272 : 0 : mConnectedHashtable[ labelText ].append( fpart.get() );
273 : 0 : }
274 : :
275 : : // add to list of layer's feature parts
276 : 0 : mFeatureParts.emplace_back( std::move( fpart ) );
277 : 0 : }
278 : :
279 : 0 : void Layer::addObstaclePart( FeaturePart *fpart )
280 : : {
281 : : // add to list of layer's feature parts
282 : 0 : mObstacleParts.append( fpart );
283 : 0 : }
284 : :
285 : 0 : static FeaturePart *_findConnectedPart( FeaturePart *partCheck, const QVector<FeaturePart *> &otherParts )
286 : : {
287 : : // iterate in the rest of the parts with the same label
288 : 0 : auto it = otherParts.constBegin();
289 : 0 : while ( it != otherParts.constEnd() )
290 : : {
291 : 0 : if ( partCheck->isConnected( *it ) )
292 : : {
293 : : // stop checking for other connected parts
294 : 0 : return *it;
295 : : }
296 : 0 : ++it;
297 : : }
298 : :
299 : 0 : return nullptr; // no connected part found...
300 : 0 : }
301 : :
302 : 0 : void Layer::joinConnectedFeatures()
303 : : {
304 : : // go through all label texts
305 : 0 : int connectedFeaturesId = 0;
306 : 0 : for ( auto it = mConnectedHashtable.constBegin(); it != mConnectedHashtable.constEnd(); ++it )
307 : : {
308 : 0 : QVector<FeaturePart *> partsToMerge = it.value();
309 : :
310 : : // need to start with biggest parts first, to avoid merging in side branches before we've
311 : : // merged the whole of the longest parts of the joined network
312 : 0 : std::sort( partsToMerge.begin(), partsToMerge.end(), []( FeaturePart * a, FeaturePart * b )
313 : : {
314 : 0 : return a->length() > b->length();
315 : : } );
316 : :
317 : : // go one-by-one part, try to merge
318 : 0 : while ( partsToMerge.count() > 1 )
319 : : {
320 : 0 : connectedFeaturesId++;
321 : :
322 : : // part we'll be checking against other in this round
323 : 0 : FeaturePart *partToJoinTo = partsToMerge.takeFirst();
324 : 0 : mConnectedFeaturesIds.insert( partToJoinTo->featureId(), connectedFeaturesId );
325 : :
326 : : // loop through all other parts
327 : 0 : QVector< FeaturePart *> partsLeftToTryThisRound = partsToMerge;
328 : 0 : while ( !partsLeftToTryThisRound.empty() )
329 : : {
330 : 0 : if ( FeaturePart *otherPart = _findConnectedPart( partToJoinTo, partsLeftToTryThisRound ) )
331 : : {
332 : 0 : partsLeftToTryThisRound.removeOne( otherPart );
333 : 0 : if ( partToJoinTo->mergeWithFeaturePart( otherPart ) )
334 : : {
335 : 0 : mConnectedFeaturesIds.insert( otherPart->featureId(), connectedFeaturesId );
336 : 0 :
337 : : // otherPart was merged into partToJoinTo, so now we completely delete the redundant feature part which was merged in
338 : 0 : partsToMerge.removeAll( otherPart );
339 : 0 : auto matchingPartIt = std::find_if( mFeatureParts.begin(), mFeatureParts.end(), [otherPart]( const std::unique_ptr< FeaturePart> &part ) { return part.get() == otherPart; } );
340 : : Q_ASSERT( matchingPartIt != mFeatureParts.end() );
341 : 0 : mFeatureParts.erase( matchingPartIt );
342 : 0 : }
343 : 0 : }
344 : : else
345 : : {
346 : : // no candidate parts remain which we could possibly merge in
347 : 0 : break;
348 : : }
349 : : }
350 : 0 : }
351 : 0 : }
352 : 0 : mConnectedHashtable.clear();
353 : :
354 : : // Expunge feature parts that are smaller than the minimum size required
355 : 0 : mFeatureParts.erase( std::remove_if( mFeatureParts.begin(), mFeatureParts.end(), []( const std::unique_ptr< FeaturePart > &part )
356 : : {
357 : 0 : if ( part->feature()->minimumSize() != 0.0 && part->length() < part->feature()->minimumSize() )
358 : : {
359 : 0 : return true;
360 : : }
361 : 0 : return false;
362 : 0 : } ), mFeatureParts.end() );
363 : 0 : }
364 : :
365 : 0 : int Layer::connectedFeatureId( QgsFeatureId featureId ) const
366 : : {
367 : 0 : return mConnectedFeaturesIds.value( featureId, -1 );
368 : : }
369 : :
370 : 0 : void Layer::chopFeaturesAtRepeatDistance()
371 : : {
372 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
373 : 0 : std::deque< std::unique_ptr< FeaturePart > > newFeatureParts;
374 : 0 : while ( !mFeatureParts.empty() )
375 : : {
376 : 0 : std::unique_ptr< FeaturePart > fpart = std::move( mFeatureParts.front() );
377 : 0 : mFeatureParts.pop_front();
378 : :
379 : 0 : const GEOSGeometry *geom = fpart->geos();
380 : 0 : double chopInterval = fpart->repeatDistance();
381 : :
382 : : // whether we CAN chop
383 : 0 : bool canChop = false;
384 : 0 : double featureLen = 0;
385 : 0 : if ( chopInterval != 0. && GEOSGeomTypeId_r( geosctxt, geom ) == GEOS_LINESTRING )
386 : : {
387 : 0 : featureLen = fpart->length();
388 : 0 : if ( featureLen > chopInterval )
389 : 0 : canChop = true;
390 : 0 : }
391 : :
392 : : // whether we SHOULD chop
393 : 0 : bool shouldChop = canChop;
394 : 0 : int possibleSegments = 0;
395 : 0 : if ( canChop )
396 : : {
397 : : // never chop into segments smaller than required for the actual label text
398 : 0 : chopInterval *= std::ceil( fpart->getLabelWidth() / fpart->repeatDistance() );
399 : :
400 : : // now work out how many full segments we could chop this line into
401 : 0 : possibleSegments = static_cast< int >( std::floor( featureLen / chopInterval ) );
402 : :
403 : : // ... and use this to work out the actual chop distance for this line. Otherwise, we risk the
404 : : // situation of:
405 : : // 1. Line length of 3cm
406 : : // 2. Repeat distance of 2cm
407 : : // 3. Label size is 1.5 cm
408 : : //
409 : : // 2cm 1cm
410 : : // /--Label--/----/
411 : : //
412 : : // i.e. the labels would be off center and gravitate toward line starts
413 : 0 : chopInterval = featureLen / possibleSegments;
414 : :
415 : 0 : shouldChop = possibleSegments > 1;
416 : 0 : }
417 : :
418 : 0 : if ( shouldChop )
419 : : {
420 : 0 : const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( geosctxt, geom );
421 : :
422 : : // get number of points
423 : : unsigned int n;
424 : 0 : GEOSCoordSeq_getSize_r( geosctxt, cs, &n );
425 : :
426 : : // Read points
427 : 0 : std::vector<Point> points( n );
428 : 0 : for ( unsigned int i = 0; i < n; ++i )
429 : : {
430 : : #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
431 : 0 : GEOSCoordSeq_getXY_r( geosctxt, cs, i, &points[i].x, &points[i].y );
432 : : #else
433 : : GEOSCoordSeq_getX_r( geosctxt, cs, i, &points[i].x );
434 : : GEOSCoordSeq_getY_r( geosctxt, cs, i, &points[i].y );
435 : : #endif
436 : 0 : }
437 : :
438 : : // Cumulative length vector
439 : 0 : std::vector<double> len( n, 0 );
440 : 0 : for ( unsigned int i = 1; i < n; ++i )
441 : : {
442 : 0 : double dx = points[i].x - points[i - 1].x;
443 : 0 : double dy = points[i].y - points[i - 1].y;
444 : 0 : len[i] = len[i - 1] + std::sqrt( dx * dx + dy * dy );
445 : 0 : }
446 : :
447 : : // Walk along line
448 : 0 : unsigned int cur = 0;
449 : 0 : double lambda = 0;
450 : 0 : std::vector<Point> part;
451 : :
452 : 0 : QList<FeaturePart *> repeatParts;
453 : 0 : repeatParts.reserve( possibleSegments );
454 : :
455 : 0 : for ( int segment = 0; segment < possibleSegments; segment++ )
456 : : {
457 : 0 : lambda += chopInterval;
458 : 0 : for ( ; cur < n && lambda > len[cur]; ++cur )
459 : : {
460 : 0 : part.push_back( points[cur] );
461 : 0 : }
462 : 0 : if ( cur >= n )
463 : : {
464 : : // Create final part
465 : 0 : GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, static_cast< unsigned int >( part.size() ), 2 );
466 : 0 : for ( unsigned int i = 0; i < part.size(); ++i )
467 : : {
468 : : #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
469 : 0 : GEOSCoordSeq_setXY_r( geosctxt, cooSeq, i, part[i].x, part[i].y );
470 : : #else
471 : : GEOSCoordSeq_setX_r( geosctxt, cooSeq, i, part[i].x );
472 : : GEOSCoordSeq_setY_r( geosctxt, cooSeq, i, part[i].y );
473 : : #endif
474 : 0 : }
475 : 0 : GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
476 : 0 : std::unique_ptr< FeaturePart > newfpart = std::make_unique< FeaturePart >( fpart->feature(), newgeom );
477 : 0 : repeatParts.push_back( newfpart.get() );
478 : 0 : newFeatureParts.emplace_back( std::move( newfpart ) );
479 : : break;
480 : 0 : }
481 : 0 : double c = ( lambda - len[cur - 1] ) / ( len[cur] - len[cur - 1] );
482 : : Point p;
483 : 0 : p.x = points[cur - 1].x + c * ( points[cur].x - points[cur - 1].x );
484 : 0 : p.y = points[cur - 1].y + c * ( points[cur].y - points[cur - 1].y );
485 : 0 : part.push_back( p );
486 : 0 : GEOSCoordSequence *cooSeq = GEOSCoordSeq_create_r( geosctxt, static_cast< unsigned int >( part.size() ), 2 );
487 : 0 : for ( std::size_t i = 0; i < part.size(); ++i )
488 : : {
489 : : #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
490 : 0 : GEOSCoordSeq_setXY_r( geosctxt, cooSeq, i, part[i].x, part[i].y );
491 : : #else
492 : : GEOSCoordSeq_setX_r( geosctxt, cooSeq, static_cast< unsigned int >( i ), part[i].x );
493 : : GEOSCoordSeq_setY_r( geosctxt, cooSeq, static_cast< unsigned int >( i ), part[i].y );
494 : : #endif
495 : 0 : }
496 : :
497 : 0 : GEOSGeometry *newgeom = GEOSGeom_createLineString_r( geosctxt, cooSeq );
498 : 0 : std::unique_ptr< FeaturePart > newfpart = std::make_unique< FeaturePart >( fpart->feature(), newgeom );
499 : 0 : repeatParts.push_back( newfpart.get() );
500 : 0 : newFeatureParts.emplace_back( std::move( newfpart ) );
501 : 0 : part.clear();
502 : 0 : part.push_back( p );
503 : 0 : }
504 : :
505 : 0 : for ( FeaturePart *partPtr : repeatParts )
506 : 0 : partPtr->setTotalRepeats( repeatParts.count() );
507 : 0 : }
508 : : else
509 : : {
510 : 0 : newFeatureParts.emplace_back( std::move( fpart ) );
511 : : }
512 : 0 : }
513 : :
514 : 0 : mFeatureParts = std::move( newFeatureParts );
515 : 0 : }
516 : :
517 : :
518 : : template class QgsGenericSpatialIndex<pal::FeaturePart>;
|
