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 "feature.h"
33 : : #include "geomfunction.h"
34 : : #include "labelposition.h"
35 : : #include "pointset.h"
36 : : #include "util.h"
37 : : #include "costcalculator.h"
38 : :
39 : : #include "qgis.h"
40 : : #include "qgsgeometry.h"
41 : : #include "qgsgeos.h"
42 : : #include "qgstextlabelfeature.h"
43 : : #include "qgsmessagelog.h"
44 : : #include "qgsgeometryutils.h"
45 : : #include "qgslabeling.h"
46 : : #include "qgspolygon.h"
47 : : #include "qgstextrendererutils.h"
48 : :
49 : : #include <QLinkedList>
50 : : #include <cmath>
51 : : #include <cfloat>
52 : :
53 : : using namespace pal;
54 : :
55 : 0 : FeaturePart::FeaturePart( QgsLabelFeature *feat, const GEOSGeometry *geom )
56 : 0 : : mLF( feat )
57 : 0 : {
58 : : // we'll remove const, but we won't modify that geometry
59 : 0 : mGeos = const_cast<GEOSGeometry *>( geom );
60 : 0 : mOwnsGeom = false; // geometry is owned by Feature class
61 : :
62 : 0 : extractCoords( geom );
63 : :
64 : 0 : holeOf = nullptr;
65 : 0 : for ( int i = 0; i < mHoles.count(); i++ )
66 : : {
67 : 0 : mHoles.at( i )->holeOf = this;
68 : 0 : }
69 : :
70 : 0 : }
71 : :
72 : 0 : FeaturePart::FeaturePart( const FeaturePart &other )
73 : 0 : : PointSet( other )
74 : 0 : , mLF( other.mLF )
75 : 0 : {
76 : 0 : for ( const FeaturePart *hole : std::as_const( other.mHoles ) )
77 : : {
78 : 0 : mHoles << new FeaturePart( *hole );
79 : 0 : mHoles.last()->holeOf = this;
80 : : }
81 : 0 : }
82 : :
83 : 0 : FeaturePart::~FeaturePart()
84 : 0 : {
85 : : // X and Y are deleted in PointSet
86 : :
87 : 0 : qDeleteAll( mHoles );
88 : 0 : mHoles.clear();
89 : 0 : }
90 : :
91 : 0 : void FeaturePart::extractCoords( const GEOSGeometry *geom )
92 : : {
93 : 0 : const GEOSCoordSequence *coordSeq = nullptr;
94 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
95 : :
96 : 0 : type = GEOSGeomTypeId_r( geosctxt, geom );
97 : :
98 : 0 : if ( type == GEOS_POLYGON )
99 : : {
100 : 0 : if ( GEOSGetNumInteriorRings_r( geosctxt, geom ) > 0 )
101 : : {
102 : 0 : int numHoles = GEOSGetNumInteriorRings_r( geosctxt, geom );
103 : :
104 : 0 : for ( int i = 0; i < numHoles; ++i )
105 : : {
106 : 0 : const GEOSGeometry *interior = GEOSGetInteriorRingN_r( geosctxt, geom, i );
107 : 0 : FeaturePart *hole = new FeaturePart( mLF, interior );
108 : 0 : hole->holeOf = nullptr;
109 : : // possibly not needed. it's not done for the exterior ring, so I'm not sure
110 : : // why it's just done here...
111 : 0 : GeomFunction::reorderPolygon( hole->x, hole->y );
112 : :
113 : 0 : mHoles << hole;
114 : 0 : }
115 : 0 : }
116 : :
117 : : // use exterior ring for the extraction of coordinates that follows
118 : 0 : geom = GEOSGetExteriorRing_r( geosctxt, geom );
119 : 0 : }
120 : : else
121 : : {
122 : 0 : qDeleteAll( mHoles );
123 : 0 : mHoles.clear();
124 : : }
125 : :
126 : : // find out number of points
127 : 0 : nbPoints = GEOSGetNumCoordinates_r( geosctxt, geom );
128 : 0 : coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, geom );
129 : :
130 : : // initialize bounding box
131 : 0 : xmin = ymin = std::numeric_limits<double>::max();
132 : 0 : xmax = ymax = std::numeric_limits<double>::lowest();
133 : :
134 : : // initialize coordinate arrays
135 : 0 : deleteCoords();
136 : 0 : x.resize( nbPoints );
137 : 0 : y.resize( nbPoints );
138 : :
139 : 0 : for ( int i = 0; i < nbPoints; ++i )
140 : : {
141 : : #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
142 : 0 : GEOSCoordSeq_getXY_r( geosctxt, coordSeq, i, &x[i], &y[i] );
143 : : #else
144 : : GEOSCoordSeq_getX_r( geosctxt, coordSeq, i, &x[i] );
145 : : GEOSCoordSeq_getY_r( geosctxt, coordSeq, i, &y[i] );
146 : : #endif
147 : :
148 : 0 : xmax = x[i] > xmax ? x[i] : xmax;
149 : 0 : xmin = x[i] < xmin ? x[i] : xmin;
150 : :
151 : 0 : ymax = y[i] > ymax ? y[i] : ymax;
152 : 0 : ymin = y[i] < ymin ? y[i] : ymin;
153 : 0 : }
154 : 0 : }
155 : :
156 : 0 : Layer *FeaturePart::layer()
157 : : {
158 : 0 : return mLF->layer();
159 : : }
160 : :
161 : 0 : QgsFeatureId FeaturePart::featureId() const
162 : : {
163 : 0 : return mLF->id();
164 : : }
165 : :
166 : 0 : std::size_t FeaturePart::maximumPointCandidates() const
167 : : {
168 : 0 : return mLF->layer()->maximumPointLabelCandidates();
169 : : }
170 : :
171 : 0 : std::size_t FeaturePart::maximumLineCandidates() const
172 : : {
173 : 0 : if ( mCachedMaxLineCandidates > 0 )
174 : 0 : return mCachedMaxLineCandidates;
175 : :
176 : 0 : const double l = length();
177 : 0 : if ( l > 0 )
178 : : {
179 : 0 : const std::size_t candidatesForLineLength = static_cast< std::size_t >( std::ceil( mLF->layer()->mPal->maximumLineCandidatesPerMapUnit() * l ) );
180 : 0 : const std::size_t maxForLayer = mLF->layer()->maximumLineLabelCandidates();
181 : 0 : if ( maxForLayer == 0 )
182 : 0 : mCachedMaxLineCandidates = candidatesForLineLength;
183 : : else
184 : 0 : mCachedMaxLineCandidates = std::min( candidatesForLineLength, maxForLayer );
185 : 0 : }
186 : : else
187 : : {
188 : 0 : mCachedMaxLineCandidates = 1;
189 : : }
190 : 0 : return mCachedMaxLineCandidates;
191 : 0 : }
192 : :
193 : 0 : std::size_t FeaturePart::maximumPolygonCandidates() const
194 : : {
195 : 0 : if ( mCachedMaxPolygonCandidates > 0 )
196 : 0 : return mCachedMaxPolygonCandidates;
197 : :
198 : 0 : const double a = area();
199 : 0 : if ( a > 0 )
200 : : {
201 : 0 : const std::size_t candidatesForArea = static_cast< std::size_t >( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * a ) );
202 : 0 : const std::size_t maxForLayer = mLF->layer()->maximumPolygonLabelCandidates();
203 : 0 : if ( maxForLayer == 0 )
204 : 0 : mCachedMaxPolygonCandidates = candidatesForArea;
205 : : else
206 : 0 : mCachedMaxPolygonCandidates = std::min( candidatesForArea, maxForLayer );
207 : 0 : }
208 : : else
209 : : {
210 : 0 : mCachedMaxPolygonCandidates = 1;
211 : : }
212 : 0 : return mCachedMaxPolygonCandidates;
213 : 0 : }
214 : :
215 : 0 : bool FeaturePart::hasSameLabelFeatureAs( FeaturePart *part ) const
216 : : {
217 : 0 : if ( !part )
218 : 0 : return false;
219 : :
220 : 0 : if ( mLF->layer()->name() != part->layer()->name() )
221 : 0 : return false;
222 : :
223 : 0 : if ( mLF->id() == part->featureId() )
224 : 0 : return true;
225 : :
226 : : // any part of joined features are also treated as having the same label feature
227 : 0 : int connectedFeatureId = mLF->layer()->connectedFeatureId( mLF->id() );
228 : 0 : return connectedFeatureId >= 0 && connectedFeatureId == mLF->layer()->connectedFeatureId( part->featureId() );
229 : 0 : }
230 : :
231 : 0 : LabelPosition::Quadrant FeaturePart::quadrantFromOffset() const
232 : : {
233 : 0 : QPointF quadOffset = mLF->quadOffset();
234 : 0 : qreal quadOffsetX = quadOffset.x(), quadOffsetY = quadOffset.y();
235 : :
236 : 0 : if ( quadOffsetX < 0 )
237 : : {
238 : 0 : if ( quadOffsetY < 0 )
239 : : {
240 : 0 : return LabelPosition::QuadrantAboveLeft;
241 : : }
242 : 0 : else if ( quadOffsetY > 0 )
243 : : {
244 : 0 : return LabelPosition::QuadrantBelowLeft;
245 : : }
246 : : else
247 : : {
248 : 0 : return LabelPosition::QuadrantLeft;
249 : : }
250 : : }
251 : 0 : else if ( quadOffsetX > 0 )
252 : : {
253 : 0 : if ( quadOffsetY < 0 )
254 : : {
255 : 0 : return LabelPosition::QuadrantAboveRight;
256 : : }
257 : 0 : else if ( quadOffsetY > 0 )
258 : : {
259 : 0 : return LabelPosition::QuadrantBelowRight;
260 : : }
261 : : else
262 : : {
263 : 0 : return LabelPosition::QuadrantRight;
264 : : }
265 : : }
266 : : else
267 : : {
268 : 0 : if ( quadOffsetY < 0 )
269 : : {
270 : 0 : return LabelPosition::QuadrantAbove;
271 : : }
272 : 0 : else if ( quadOffsetY > 0 )
273 : : {
274 : 0 : return LabelPosition::QuadrantBelow;
275 : : }
276 : : else
277 : : {
278 : 0 : return LabelPosition::QuadrantOver;
279 : : }
280 : : }
281 : 0 : }
282 : :
283 : 0 : int FeaturePart::totalRepeats() const
284 : : {
285 : 0 : return mTotalRepeats;
286 : : }
287 : :
288 : 0 : void FeaturePart::setTotalRepeats( int totalRepeats )
289 : : {
290 : 0 : mTotalRepeats = totalRepeats;
291 : 0 : }
292 : :
293 : 0 : std::size_t FeaturePart::createCandidateCenteredOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
294 : : {
295 : : // get from feature
296 : 0 : double labelW = getLabelWidth( angle );
297 : 0 : double labelH = getLabelHeight( angle );
298 : :
299 : 0 : double cost = 0.00005;
300 : 0 : int id = lPos.size();
301 : :
302 : 0 : double xdiff = -labelW / 2.0;
303 : 0 : double ydiff = -labelH / 2.0;
304 : :
305 : 0 : feature()->setAnchorPosition( QgsPointXY( x, y ) );
306 : :
307 : 0 : double lx = x + xdiff;
308 : 0 : double ly = y + ydiff;
309 : :
310 : 0 : if ( mLF->permissibleZonePrepared() )
311 : : {
312 : 0 : if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), lx, ly, labelW, labelH, angle ) )
313 : : {
314 : 0 : return 0;
315 : : }
316 : 0 : }
317 : :
318 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( id, lx, ly, labelW, labelH, angle, cost, this, false, LabelPosition::QuadrantOver ) );
319 : 0 : return 1;
320 : 0 : }
321 : :
322 : 0 : std::size_t FeaturePart::createCandidatesOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
323 : : {
324 : : // get from feature
325 : 0 : double labelW = getLabelWidth( angle );
326 : 0 : double labelH = getLabelHeight( angle );
327 : :
328 : 0 : double cost = 0.0001;
329 : 0 : int id = lPos.size();
330 : :
331 : 0 : double xdiff = -labelW / 2.0;
332 : 0 : double ydiff = -labelH / 2.0;
333 : :
334 : 0 : feature()->setAnchorPosition( QgsPointXY( x, y ) );
335 : :
336 : 0 : if ( !qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
337 : : {
338 : 0 : xdiff += labelW / 2.0 * mLF->quadOffset().x();
339 : 0 : }
340 : 0 : if ( !qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
341 : : {
342 : 0 : ydiff += labelH / 2.0 * mLF->quadOffset().y();
343 : 0 : }
344 : :
345 : 0 : if ( ! mLF->hasFixedPosition() )
346 : : {
347 : 0 : if ( !qgsDoubleNear( angle, 0.0 ) )
348 : : {
349 : 0 : double xd = xdiff * std::cos( angle ) - ydiff * std::sin( angle );
350 : 0 : double yd = xdiff * std::sin( angle ) + ydiff * std::cos( angle );
351 : 0 : xdiff = xd;
352 : 0 : ydiff = yd;
353 : 0 : }
354 : 0 : }
355 : :
356 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::AroundPoint )
357 : : {
358 : : //if in "around point" placement mode, then we use the label distance to determine
359 : : //the label's offset
360 : 0 : if ( qgsDoubleNear( mLF->quadOffset().x(), 0.0 ) )
361 : : {
362 : 0 : ydiff += mLF->quadOffset().y() * mLF->distLabel();
363 : 0 : }
364 : 0 : else if ( qgsDoubleNear( mLF->quadOffset().y(), 0.0 ) )
365 : : {
366 : 0 : xdiff += mLF->quadOffset().x() * mLF->distLabel();
367 : 0 : }
368 : : else
369 : : {
370 : 0 : xdiff += mLF->quadOffset().x() * M_SQRT1_2 * mLF->distLabel();
371 : 0 : ydiff += mLF->quadOffset().y() * M_SQRT1_2 * mLF->distLabel();
372 : : }
373 : 0 : }
374 : : else
375 : : {
376 : 0 : if ( !qgsDoubleNear( mLF->positionOffset().x(), 0.0 ) )
377 : : {
378 : 0 : xdiff += mLF->positionOffset().x();
379 : 0 : }
380 : 0 : if ( !qgsDoubleNear( mLF->positionOffset().y(), 0.0 ) )
381 : : {
382 : 0 : ydiff += mLF->positionOffset().y();
383 : 0 : }
384 : : }
385 : :
386 : 0 : double lx = x + xdiff;
387 : 0 : double ly = y + ydiff;
388 : :
389 : 0 : if ( mLF->permissibleZonePrepared() )
390 : : {
391 : 0 : if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), lx, ly, labelW, labelH, angle ) )
392 : : {
393 : 0 : return 0;
394 : : }
395 : 0 : }
396 : :
397 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( id, lx, ly, labelW, labelH, angle, cost, this, false, quadrantFromOffset() ) );
398 : 0 : return 1;
399 : 0 : }
400 : :
401 : 0 : std::unique_ptr<LabelPosition> FeaturePart::createCandidatePointOnSurface( PointSet *mapShape )
402 : : {
403 : : double px, py;
404 : : try
405 : : {
406 : 0 : GEOSContextHandle_t geosctxt = QgsGeos::getGEOSHandler();
407 : 0 : geos::unique_ptr pointGeom( GEOSPointOnSurface_r( geosctxt, mapShape->geos() ) );
408 : 0 : if ( pointGeom )
409 : : {
410 : 0 : const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
411 : : #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8
412 : 0 : unsigned int nPoints = 0;
413 : 0 : GEOSCoordSeq_getSize_r( geosctxt, coordSeq, &nPoints );
414 : 0 : if ( nPoints == 0 )
415 : 0 : return nullptr;
416 : 0 : GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
417 : : #else
418 : : GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
419 : : GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
420 : : #endif
421 : 0 : }
422 : 0 : }
423 : : catch ( GEOSException &e )
424 : : {
425 : 0 : qWarning( "GEOS exception: %s", e.what() );
426 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
427 : 0 : return nullptr;
428 : 0 : }
429 : :
430 : 0 : return std::make_unique< LabelPosition >( 0, px, py, getLabelWidth(), getLabelHeight(), 0.0, 0.0, this, false, LabelPosition::QuadrantOver );
431 : 0 : }
432 : :
433 : 0 : void createCandidateAtOrderedPositionOverPoint( double &labelX, double &labelY, LabelPosition::Quadrant &quadrant, double x, double y, double labelWidth, double labelHeight, QgsPalLayerSettings::PredefinedPointPosition position, double distanceToLabel, const QgsMargins &visualMargin, double symbolWidthOffset, double symbolHeightOffset )
434 : : {
435 : 0 : double alpha = 0.0;
436 : 0 : double deltaX = 0;
437 : 0 : double deltaY = 0;
438 : 0 : switch ( position )
439 : : {
440 : : case QgsPalLayerSettings::TopLeft:
441 : 0 : quadrant = LabelPosition::QuadrantAboveLeft;
442 : 0 : alpha = 3 * M_PI_4;
443 : 0 : deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
444 : 0 : deltaY = -visualMargin.bottom() + symbolHeightOffset;
445 : 0 : break;
446 : :
447 : : case QgsPalLayerSettings::TopSlightlyLeft:
448 : 0 : quadrant = LabelPosition::QuadrantAboveRight; //right quadrant, so labels are left-aligned
449 : 0 : alpha = M_PI_2;
450 : 0 : deltaX = -labelWidth / 4.0 - visualMargin.left();
451 : 0 : deltaY = -visualMargin.bottom() + symbolHeightOffset;
452 : 0 : break;
453 : :
454 : : case QgsPalLayerSettings::TopMiddle:
455 : 0 : quadrant = LabelPosition::QuadrantAbove;
456 : 0 : alpha = M_PI_2;
457 : 0 : deltaX = -labelWidth / 2.0;
458 : 0 : deltaY = -visualMargin.bottom() + symbolHeightOffset;
459 : 0 : break;
460 : :
461 : : case QgsPalLayerSettings::TopSlightlyRight:
462 : 0 : quadrant = LabelPosition::QuadrantAboveLeft; //left quadrant, so labels are right-aligned
463 : 0 : alpha = M_PI_2;
464 : 0 : deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
465 : 0 : deltaY = -visualMargin.bottom() + symbolHeightOffset;
466 : 0 : break;
467 : :
468 : : case QgsPalLayerSettings::TopRight:
469 : 0 : quadrant = LabelPosition::QuadrantAboveRight;
470 : 0 : alpha = M_PI_4;
471 : 0 : deltaX = - visualMargin.left() + symbolWidthOffset;
472 : 0 : deltaY = -visualMargin.bottom() + symbolHeightOffset;
473 : 0 : break;
474 : :
475 : : case QgsPalLayerSettings::MiddleLeft:
476 : 0 : quadrant = LabelPosition::QuadrantLeft;
477 : 0 : alpha = M_PI;
478 : 0 : deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
479 : 0 : deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
480 : 0 : break;
481 : :
482 : : case QgsPalLayerSettings::MiddleRight:
483 : 0 : quadrant = LabelPosition::QuadrantRight;
484 : 0 : alpha = 0.0;
485 : 0 : deltaX = -visualMargin.left() + symbolWidthOffset;
486 : 0 : deltaY = -labelHeight / 2.0;// TODO - should this be adjusted by visual margin??
487 : 0 : break;
488 : :
489 : : case QgsPalLayerSettings::BottomLeft:
490 : 0 : quadrant = LabelPosition::QuadrantBelowLeft;
491 : 0 : alpha = 5 * M_PI_4;
492 : 0 : deltaX = -labelWidth + visualMargin.right() - symbolWidthOffset;
493 : 0 : deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
494 : 0 : break;
495 : :
496 : : case QgsPalLayerSettings::BottomSlightlyLeft:
497 : 0 : quadrant = LabelPosition::QuadrantBelowRight; //right quadrant, so labels are left-aligned
498 : 0 : alpha = 3 * M_PI_2;
499 : 0 : deltaX = -labelWidth / 4.0 - visualMargin.left();
500 : 0 : deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
501 : 0 : break;
502 : :
503 : : case QgsPalLayerSettings::BottomMiddle:
504 : 0 : quadrant = LabelPosition::QuadrantBelow;
505 : 0 : alpha = 3 * M_PI_2;
506 : 0 : deltaX = -labelWidth / 2.0;
507 : 0 : deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
508 : 0 : break;
509 : :
510 : : case QgsPalLayerSettings::BottomSlightlyRight:
511 : 0 : quadrant = LabelPosition::QuadrantBelowLeft; //left quadrant, so labels are right-aligned
512 : 0 : alpha = 3 * M_PI_2;
513 : 0 : deltaX = -labelWidth * 3.0 / 4.0 + visualMargin.right();
514 : 0 : deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
515 : 0 : break;
516 : :
517 : : case QgsPalLayerSettings::BottomRight:
518 : 0 : quadrant = LabelPosition::QuadrantBelowRight;
519 : 0 : alpha = 7 * M_PI_4;
520 : 0 : deltaX = -visualMargin.left() + symbolWidthOffset;
521 : 0 : deltaY = -labelHeight + visualMargin.top() - symbolHeightOffset;
522 : 0 : break;
523 : : }
524 : :
525 : : //have bearing, distance - calculate reference point
526 : 0 : double referenceX = std::cos( alpha ) * distanceToLabel + x;
527 : 0 : double referenceY = std::sin( alpha ) * distanceToLabel + y;
528 : :
529 : 0 : labelX = referenceX + deltaX;
530 : 0 : labelY = referenceY + deltaY;
531 : 0 : }
532 : :
533 : 0 : std::size_t FeaturePart::createCandidatesAtOrderedPositionsOverPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
534 : : {
535 : 0 : const QVector< QgsPalLayerSettings::PredefinedPointPosition > positions = mLF->predefinedPositionOrder();
536 : 0 : double labelWidth = getLabelWidth( angle );
537 : 0 : double labelHeight = getLabelHeight( angle );
538 : 0 : double distanceToLabel = getLabelDistance();
539 : 0 : const QgsMargins &visualMargin = mLF->visualMargin();
540 : :
541 : 0 : double symbolWidthOffset = ( mLF->offsetType() == QgsPalLayerSettings::FromSymbolBounds ? mLF->symbolSize().width() / 2.0 : 0.0 );
542 : 0 : double symbolHeightOffset = ( mLF->offsetType() == QgsPalLayerSettings::FromSymbolBounds ? mLF->symbolSize().height() / 2.0 : 0.0 );
543 : :
544 : 0 : double cost = 0.0001;
545 : 0 : std::size_t i = lPos.size();
546 : :
547 : 0 : const std::size_t maxNumberCandidates = mLF->layer()->maximumPointLabelCandidates();
548 : 0 : std::size_t created = 0;
549 : 0 : for ( QgsPalLayerSettings::PredefinedPointPosition position : positions )
550 : : {
551 : 0 : LabelPosition::Quadrant quadrant = LabelPosition::QuadrantAboveLeft;
552 : :
553 : 0 : double labelX = 0;
554 : 0 : double labelY = 0;
555 : 0 : createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel, visualMargin, symbolWidthOffset, symbolHeightOffset );
556 : :
557 : 0 : if ( ! mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
558 : : {
559 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant ) );
560 : 0 : created++;
561 : : //TODO - tweak
562 : 0 : cost += 0.001;
563 : 0 : if ( maxNumberCandidates > 0 && created >= maxNumberCandidates )
564 : 0 : break;
565 : 0 : }
566 : 0 : ++i;
567 : : }
568 : :
569 : 0 : return created;
570 : 0 : }
571 : :
572 : 0 : std::size_t FeaturePart::createCandidatesAroundPoint( double x, double y, std::vector< std::unique_ptr< LabelPosition > > &lPos, double angle )
573 : : {
574 : 0 : double labelWidth = getLabelWidth( angle );
575 : 0 : double labelHeight = getLabelHeight( angle );
576 : 0 : double distanceToLabel = getLabelDistance();
577 : :
578 : 0 : std::size_t maxNumberCandidates = mLF->layer()->maximumPointLabelCandidates();
579 : 0 : if ( maxNumberCandidates == 0 )
580 : 0 : maxNumberCandidates = 16;
581 : :
582 : 0 : int icost = 0;
583 : 0 : int inc = 2;
584 : 0 : int id = lPos.size();
585 : :
586 : 0 : double candidateAngleIncrement = 2 * M_PI / maxNumberCandidates; /* angle bw 2 pos */
587 : :
588 : : /* various angles */
589 : 0 : double a90 = M_PI_2;
590 : 0 : double a180 = M_PI;
591 : 0 : double a270 = a180 + a90;
592 : 0 : double a360 = 2 * M_PI;
593 : :
594 : : double gamma1, gamma2;
595 : :
596 : 0 : if ( distanceToLabel > 0 )
597 : : {
598 : 0 : gamma1 = std::atan2( labelHeight / 2, distanceToLabel + labelWidth / 2 );
599 : 0 : gamma2 = std::atan2( labelWidth / 2, distanceToLabel + labelHeight / 2 );
600 : 0 : }
601 : : else
602 : : {
603 : 0 : gamma1 = gamma2 = a90 / 3.0;
604 : : }
605 : :
606 : 0 : if ( gamma1 > a90 / 3.0 )
607 : 0 : gamma1 = a90 / 3.0;
608 : :
609 : 0 : if ( gamma2 > a90 / 3.0 )
610 : 0 : gamma2 = a90 / 3.0;
611 : :
612 : 0 : std::size_t numberCandidatesGenerated = 0;
613 : :
614 : : std::size_t i;
615 : : double angleToCandidate;
616 : 0 : for ( i = 0, angleToCandidate = M_PI_4; i < maxNumberCandidates; i++, angleToCandidate += candidateAngleIncrement )
617 : : {
618 : 0 : double labelX = x;
619 : 0 : double labelY = y;
620 : :
621 : 0 : if ( angleToCandidate > a360 )
622 : 0 : angleToCandidate -= a360;
623 : :
624 : 0 : LabelPosition::Quadrant quadrant = LabelPosition::QuadrantOver;
625 : :
626 : 0 : if ( angleToCandidate < gamma1 || angleToCandidate > a360 - gamma1 ) // on the right
627 : : {
628 : 0 : labelX += distanceToLabel;
629 : 0 : double iota = ( angleToCandidate + gamma1 );
630 : 0 : if ( iota > a360 - gamma1 )
631 : 0 : iota -= a360;
632 : :
633 : : //ly += -yrm/2.0 + tan(alpha)*(distlabel + xrm/2);
634 : 0 : labelY += -labelHeight + labelHeight * iota / ( 2 * gamma1 );
635 : :
636 : 0 : quadrant = LabelPosition::QuadrantRight;
637 : 0 : }
638 : 0 : else if ( angleToCandidate < a90 - gamma2 ) // top-right
639 : : {
640 : 0 : labelX += distanceToLabel * std::cos( angleToCandidate );
641 : 0 : labelY += distanceToLabel * std::sin( angleToCandidate );
642 : 0 : quadrant = LabelPosition::QuadrantAboveRight;
643 : 0 : }
644 : 0 : else if ( angleToCandidate < a90 + gamma2 ) // top
645 : : {
646 : : //lx += -xrm/2.0 - tan(alpha+a90)*(distlabel + yrm/2);
647 : 0 : labelX += -labelWidth * ( angleToCandidate - a90 + gamma2 ) / ( 2 * gamma2 );
648 : 0 : labelY += distanceToLabel;
649 : 0 : quadrant = LabelPosition::QuadrantAbove;
650 : 0 : }
651 : 0 : else if ( angleToCandidate < a180 - gamma1 ) // top left
652 : : {
653 : 0 : labelX += distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
654 : 0 : labelY += distanceToLabel * std::sin( angleToCandidate );
655 : 0 : quadrant = LabelPosition::QuadrantAboveLeft;
656 : 0 : }
657 : 0 : else if ( angleToCandidate < a180 + gamma1 ) // left
658 : : {
659 : 0 : labelX += -distanceToLabel - labelWidth;
660 : : //ly += -yrm/2.0 - tan(alpha)*(distlabel + xrm/2);
661 : 0 : labelY += - ( angleToCandidate - a180 + gamma1 ) * labelHeight / ( 2 * gamma1 );
662 : 0 : quadrant = LabelPosition::QuadrantLeft;
663 : 0 : }
664 : 0 : else if ( angleToCandidate < a270 - gamma2 ) // down - left
665 : : {
666 : 0 : labelX += distanceToLabel * std::cos( angleToCandidate ) - labelWidth;
667 : 0 : labelY += distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
668 : 0 : quadrant = LabelPosition::QuadrantBelowLeft;
669 : 0 : }
670 : 0 : else if ( angleToCandidate < a270 + gamma2 ) // down
671 : : {
672 : 0 : labelY += -distanceToLabel - labelHeight;
673 : : //lx += -xrm/2.0 + tan(alpha+a90)*(distlabel + yrm/2);
674 : 0 : labelX += -labelWidth + ( angleToCandidate - a270 + gamma2 ) * labelWidth / ( 2 * gamma2 );
675 : 0 : quadrant = LabelPosition::QuadrantBelow;
676 : 0 : }
677 : 0 : else if ( angleToCandidate < a360 ) // down - right
678 : : {
679 : 0 : labelX += distanceToLabel * std::cos( angleToCandidate );
680 : 0 : labelY += distanceToLabel * std::sin( angleToCandidate ) - labelHeight;
681 : 0 : quadrant = LabelPosition::QuadrantBelowRight;
682 : 0 : }
683 : :
684 : : double cost;
685 : :
686 : 0 : if ( maxNumberCandidates == 1 )
687 : 0 : cost = 0.0001;
688 : : else
689 : 0 : cost = 0.0001 + 0.0020 * double( icost ) / double( maxNumberCandidates - 1 );
690 : :
691 : :
692 : 0 : if ( mLF->permissibleZonePrepared() )
693 : : {
694 : 0 : if ( !GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), labelX, labelY, labelWidth, labelHeight, angle ) )
695 : : {
696 : 0 : continue;
697 : : }
698 : 0 : }
699 : :
700 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( id + i, labelX, labelY, labelWidth, labelHeight, angle, cost, this, false, quadrant ) );
701 : 0 : numberCandidatesGenerated++;
702 : :
703 : 0 : icost += inc;
704 : :
705 : 0 : if ( icost == static_cast< int >( maxNumberCandidates ) )
706 : : {
707 : 0 : icost = static_cast< int >( maxNumberCandidates ) - 1;
708 : 0 : inc = -2;
709 : 0 : }
710 : 0 : else if ( icost > static_cast< int >( maxNumberCandidates ) )
711 : : {
712 : 0 : icost = static_cast< int >( maxNumberCandidates ) - 2;
713 : 0 : inc = -2;
714 : 0 : }
715 : :
716 : 0 : }
717 : :
718 : 0 : return numberCandidatesGenerated;
719 : 0 : }
720 : :
721 : 0 : std::size_t FeaturePart::createCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
722 : : {
723 : 0 : if ( allowOverrun )
724 : : {
725 : 0 : double shapeLength = mapShape->length();
726 : 0 : if ( totalRepeats() > 1 && shapeLength < getLabelWidth() )
727 : 0 : return 0;
728 : 0 : else if ( shapeLength < getLabelWidth() - 2 * std::min( getLabelWidth(), mLF->overrunDistance() ) )
729 : : {
730 : : // label doesn't fit on this line, don't waste time trying to make candidates
731 : 0 : return 0;
732 : : }
733 : 0 : }
734 : :
735 : : //prefer to label along straightish segments:
736 : 0 : std::size_t candidates = 0;
737 : :
738 : 0 : if ( mLF->lineAnchorType() == QgsLabelLineSettings::AnchorType::HintOnly )
739 : 0 : candidates = createCandidatesAlongLineNearStraightSegments( lPos, mapShape, pal );
740 : :
741 : 0 : const std::size_t candidateTargetCount = maximumLineCandidates();
742 : 0 : if ( candidates < candidateTargetCount )
743 : : {
744 : : // but not enough candidates yet, so fallback to labeling near whole line's midpoint
745 : 0 : candidates = createCandidatesAlongLineNearMidpoint( lPos, mapShape, candidates > 0 ? 0.01 : 0.0, pal );
746 : 0 : }
747 : 0 : return candidates;
748 : 0 : }
749 : :
750 : 0 : std::size_t FeaturePart::createHorizontalCandidatesAlongLine( std::vector<std::unique_ptr<LabelPosition> > &lPos, PointSet *mapShape, Pal *pal )
751 : : {
752 : 0 : const double labelWidth = getLabelWidth();
753 : 0 : const double labelHeight = getLabelHeight();
754 : :
755 : 0 : PointSet *line = mapShape;
756 : 0 : int nbPoints = line->nbPoints;
757 : 0 : std::vector< double > &x = line->x;
758 : 0 : std::vector< double > &y = line->y;
759 : :
760 : 0 : std::vector< double > segmentLengths( nbPoints - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
761 : 0 : std::vector< double >distanceToSegment( nbPoints ); // absolute distance bw pt[0] and pt[i] along the line
762 : :
763 : 0 : double totalLineLength = 0.0; // line length
764 : 0 : for ( int i = 0; i < line->nbPoints - 1; i++ )
765 : : {
766 : 0 : if ( i == 0 )
767 : 0 : distanceToSegment[i] = 0;
768 : : else
769 : 0 : distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
770 : :
771 : 0 : segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
772 : 0 : totalLineLength += segmentLengths[i];
773 : 0 : }
774 : 0 : distanceToSegment[line->nbPoints - 1] = totalLineLength;
775 : :
776 : 0 : const std::size_t candidateTargetCount = maximumLineCandidates();
777 : 0 : double lineStepDistance = 0;
778 : :
779 : 0 : const double lineAnchorPoint = totalLineLength * mLF->lineAnchorPercent();
780 : 0 : double currentDistanceAlongLine = lineStepDistance;
781 : 0 : switch ( mLF->lineAnchorType() )
782 : : {
783 : : case QgsLabelLineSettings::AnchorType::HintOnly:
784 : 0 : lineStepDistance = totalLineLength / ( candidateTargetCount + 1 ); // distance to move along line with each candidate
785 : 0 : break;
786 : :
787 : : case QgsLabelLineSettings::AnchorType::Strict:
788 : 0 : currentDistanceAlongLine = lineAnchorPoint;
789 : 0 : lineStepDistance = -1;
790 : 0 : break;
791 : : }
792 : :
793 : : double candidateCenterX, candidateCenterY;
794 : 0 : int i = 0;
795 : 0 : while ( currentDistanceAlongLine <= totalLineLength )
796 : : {
797 : 0 : if ( pal->isCanceled() )
798 : : {
799 : 0 : return lPos.size();
800 : : }
801 : :
802 : 0 : line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateCenterX, &candidateCenterY );
803 : :
804 : : // penalize positions which are further from the line's anchor point
805 : 0 : double cost = std::fabs( lineAnchorPoint - currentDistanceAlongLine ) / totalLineLength; // <0, 0.5>
806 : 0 : cost /= 1000; // < 0, 0.0005 >
807 : :
808 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateCenterX - labelWidth / 2, candidateCenterY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) );
809 : :
810 : 0 : currentDistanceAlongLine += lineStepDistance;
811 : :
812 : 0 : i++;
813 : :
814 : 0 : if ( lineStepDistance < 0 )
815 : 0 : break;
816 : : }
817 : :
818 : 0 : return lPos.size();
819 : 0 : }
820 : :
821 : 0 : std::size_t FeaturePart::createCandidatesAlongLineNearStraightSegments( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
822 : : {
823 : 0 : double labelWidth = getLabelWidth();
824 : 0 : double labelHeight = getLabelHeight();
825 : 0 : double distanceLineToLabel = getLabelDistance();
826 : 0 : QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
827 : 0 : if ( flags == 0 )
828 : 0 : flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
829 : :
830 : : // first scan through the whole line and look for segments where the angle at a node is greater than 45 degrees - these form a "hard break" which labels shouldn't cross over
831 : 0 : QVector< int > extremeAngleNodes;
832 : 0 : PointSet *line = mapShape;
833 : 0 : int numberNodes = line->nbPoints;
834 : 0 : std::vector< double > &x = line->x;
835 : 0 : std::vector< double > &y = line->y;
836 : :
837 : : // closed line? if so, we need to handle the final node angle
838 : 0 : bool closedLine = qgsDoubleNear( x[0], x[ numberNodes - 1] ) && qgsDoubleNear( y[0], y[numberNodes - 1 ] );
839 : 0 : for ( int i = 1; i <= numberNodes - ( closedLine ? 1 : 2 ); ++i )
840 : : {
841 : 0 : double x1 = x[i - 1];
842 : 0 : double x2 = x[i];
843 : 0 : double x3 = x[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
844 : 0 : double y1 = y[i - 1];
845 : 0 : double y2 = y[i];
846 : 0 : double y3 = y[ i == numberNodes - 1 ? 1 : i + 1]; // wraparound for closed linestrings
847 : 0 : if ( qgsDoubleNear( y2, y3 ) && qgsDoubleNear( x2, x3 ) )
848 : 0 : continue;
849 : 0 : if ( qgsDoubleNear( y1, y2 ) && qgsDoubleNear( x1, x2 ) )
850 : 0 : continue;
851 : 0 : double vertexAngle = M_PI - ( std::atan2( y3 - y2, x3 - x2 ) - std::atan2( y2 - y1, x2 - x1 ) );
852 : 0 : vertexAngle = QgsGeometryUtils::normalizedAngle( vertexAngle );
853 : :
854 : : // extreme angles form more than 45 degree angle at a node - these are the ones we don't want labels to cross
855 : 0 : if ( vertexAngle < M_PI * 135.0 / 180.0 || vertexAngle > M_PI * 225.0 / 180.0 )
856 : 0 : extremeAngleNodes << i;
857 : 0 : }
858 : 0 : extremeAngleNodes << numberNodes - 1;
859 : :
860 : 0 : if ( extremeAngleNodes.isEmpty() )
861 : : {
862 : : // no extreme angles - createCandidatesAlongLineNearMidpoint will be more appropriate
863 : 0 : return 0;
864 : : }
865 : :
866 : : // calculate lengths of segments, and work out longest straight-ish segment
867 : 0 : std::vector< double > segmentLengths( numberNodes - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
868 : 0 : std::vector< double > distanceToSegment( numberNodes ); // absolute distance bw pt[0] and pt[i] along the line
869 : 0 : double totalLineLength = 0.0;
870 : 0 : QVector< double > straightSegmentLengths;
871 : 0 : QVector< double > straightSegmentAngles;
872 : 0 : straightSegmentLengths.reserve( extremeAngleNodes.size() + 1 );
873 : 0 : straightSegmentAngles.reserve( extremeAngleNodes.size() + 1 );
874 : 0 : double currentStraightSegmentLength = 0;
875 : 0 : double longestSegmentLength = 0;
876 : 0 : int segmentIndex = 0;
877 : 0 : double segmentStartX = x[0];
878 : 0 : double segmentStartY = y[0];
879 : 0 : for ( int i = 0; i < numberNodes - 1; i++ )
880 : : {
881 : 0 : if ( i == 0 )
882 : 0 : distanceToSegment[i] = 0;
883 : : else
884 : 0 : distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
885 : :
886 : 0 : segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
887 : 0 : totalLineLength += segmentLengths[i];
888 : 0 : if ( extremeAngleNodes.contains( i ) )
889 : : {
890 : : // at an extreme angle node, so reset counters
891 : 0 : straightSegmentLengths << currentStraightSegmentLength;
892 : 0 : straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[i] - segmentStartY, x[i] - segmentStartX ) );
893 : 0 : longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
894 : 0 : segmentIndex++;
895 : 0 : currentStraightSegmentLength = 0;
896 : 0 : segmentStartX = x[i];
897 : 0 : segmentStartY = y[i];
898 : 0 : }
899 : 0 : currentStraightSegmentLength += segmentLengths[i];
900 : 0 : }
901 : 0 : distanceToSegment[line->nbPoints - 1] = totalLineLength;
902 : 0 : straightSegmentLengths << currentStraightSegmentLength;
903 : 0 : straightSegmentAngles << QgsGeometryUtils::normalizedAngle( std::atan2( y[numberNodes - 1] - segmentStartY, x[numberNodes - 1] - segmentStartX ) );
904 : 0 : longestSegmentLength = std::max( longestSegmentLength, currentStraightSegmentLength );
905 : 0 : const double lineAnchorPoint = totalLineLength * mLF->lineAnchorPercent();
906 : :
907 : 0 : if ( totalLineLength < labelWidth )
908 : : {
909 : 0 : return 0; //createCandidatesAlongLineNearMidpoint will be more appropriate
910 : : }
911 : :
912 : 0 : const std::size_t candidateTargetCount = maximumLineCandidates();
913 : 0 : double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
914 : 0 : lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
915 : :
916 : 0 : double distanceToEndOfSegment = 0.0;
917 : 0 : int lastNodeInSegment = 0;
918 : : // finally, loop through all these straight segments. For each we create candidates along the straight segment.
919 : 0 : for ( int i = 0; i < straightSegmentLengths.count(); ++i )
920 : : {
921 : 0 : currentStraightSegmentLength = straightSegmentLengths.at( i );
922 : 0 : double currentSegmentAngle = straightSegmentAngles.at( i );
923 : 0 : lastNodeInSegment = extremeAngleNodes.at( i );
924 : 0 : double distanceToStartOfSegment = distanceToEndOfSegment;
925 : 0 : distanceToEndOfSegment = distanceToSegment[ lastNodeInSegment ];
926 : 0 : double distanceToCenterOfSegment = 0.5 * ( distanceToEndOfSegment + distanceToStartOfSegment );
927 : :
928 : 0 : if ( currentStraightSegmentLength < labelWidth )
929 : : // can't fit a label on here
930 : 0 : continue;
931 : :
932 : 0 : double currentDistanceAlongLine = distanceToStartOfSegment;
933 : : double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
934 : 0 : double candidateLength = 0.0;
935 : 0 : double cost = 0.0;
936 : 0 : double angle = 0.0;
937 : 0 : double beta = 0.0;
938 : :
939 : : //calculate some cost penalties
940 : 0 : double segmentCost = 1.0 - ( distanceToEndOfSegment - distanceToStartOfSegment ) / longestSegmentLength; // 0 -> 1 (lower for longer segments)
941 : 0 : double segmentAngleCost = 1 - std::fabs( std::fmod( currentSegmentAngle, M_PI ) - M_PI_2 ) / M_PI_2; // 0 -> 1, lower for more horizontal segments
942 : :
943 : 0 : while ( currentDistanceAlongLine + labelWidth < distanceToEndOfSegment )
944 : : {
945 : 0 : if ( pal->isCanceled() )
946 : : {
947 : 0 : return lPos.size();
948 : : }
949 : :
950 : : // calculate positions along linestring corresponding to start and end of current label candidate
951 : 0 : line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
952 : 0 : line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
953 : :
954 : 0 : candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
955 : :
956 : :
957 : : // LOTS OF DIFFERENT COSTS TO BALANCE HERE - feel free to tweak these, but please add a unit test
958 : : // which covers the situation you are adjusting for (e.g., "given equal length lines, choose the more horizontal line")
959 : :
960 : 0 : cost = candidateLength / labelWidth;
961 : 0 : if ( cost > 0.98 )
962 : 0 : cost = 0.0001;
963 : : else
964 : : {
965 : : // jaggy line has a greater cost
966 : 0 : cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
967 : : }
968 : :
969 : : // penalize positions which are further from the straight segments's midpoint
970 : 0 : double labelCenter = currentDistanceAlongLine + labelWidth / 2.0;
971 : 0 : const bool placementIsFlexible = mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
972 : 0 : if ( placementIsFlexible )
973 : : {
974 : : // only apply this if labels are being placed toward the center of overall lines -- otherwise it messes with the distance from anchor cost
975 : 0 : double costCenter = 2 * std::fabs( labelCenter - distanceToCenterOfSegment ) / ( distanceToEndOfSegment - distanceToStartOfSegment ); // 0 -> 1
976 : 0 : cost += costCenter * 0.0005; // < 0, 0.0005 >
977 : 0 : }
978 : :
979 : 0 : if ( !closedLine )
980 : : {
981 : : // penalize positions which are further from absolute center of whole linestring
982 : : // this only applies to non closed linestrings, since the middle of a closed linestring is effectively arbitrary
983 : : // and irrelevant to labeling
984 : 0 : double costLineCenter = 2 * std::fabs( labelCenter - lineAnchorPoint ) / totalLineLength; // 0 -> 1
985 : 0 : cost += costLineCenter * 0.0005; // < 0, 0.0005 >
986 : 0 : }
987 : :
988 : 0 : if ( placementIsFlexible )
989 : : {
990 : 0 : cost += segmentCost * 0.0005; // prefer labels on longer straight segments
991 : 0 : cost += segmentAngleCost * 0.0001; // prefer more horizontal segments, but this is less important than length considerations
992 : 0 : }
993 : :
994 : 0 : if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
995 : : {
996 : 0 : angle = 0.0;
997 : 0 : }
998 : : else
999 : 0 : angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1000 : :
1001 : 0 : labelWidth = getLabelWidth( angle );
1002 : 0 : labelHeight = getLabelHeight( angle );
1003 : 0 : beta = angle + M_PI_2;
1004 : :
1005 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Line )
1006 : : {
1007 : : // find out whether the line direction for this candidate is from right to left
1008 : 0 : bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1009 : : // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1010 : 0 : bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1011 : 0 : bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1012 : 0 : bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1013 : :
1014 : 0 : if ( belowLine )
1015 : : {
1016 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1017 : : {
1018 : 0 : const double candidateCost = cost + ( reversed ? 0 : 0.001 );
1019 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1020 : 0 : }
1021 : 0 : }
1022 : 0 : if ( aboveLine )
1023 : : {
1024 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1025 : : {
1026 : 0 : const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1027 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1028 : 0 : }
1029 : 0 : }
1030 : 0 : if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1031 : : {
1032 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1033 : : {
1034 : 0 : const double candidateCost = cost + 0.002;
1035 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1036 : 0 : }
1037 : 0 : }
1038 : 0 : }
1039 : 0 : else if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal )
1040 : : {
1041 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1042 : 0 : }
1043 : : else
1044 : : {
1045 : : // an invalid arrangement?
1046 : : }
1047 : :
1048 : 0 : currentDistanceAlongLine += lineStepDistance;
1049 : : }
1050 : 0 : }
1051 : :
1052 : 0 : return lPos.size();
1053 : 0 : }
1054 : :
1055 : 0 : std::size_t FeaturePart::createCandidatesAlongLineNearMidpoint( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, double initialCost, Pal *pal )
1056 : : {
1057 : 0 : double distanceLineToLabel = getLabelDistance();
1058 : :
1059 : 0 : double labelWidth = getLabelWidth();
1060 : 0 : double labelHeight = getLabelHeight();
1061 : :
1062 : : double angle;
1063 : : double cost;
1064 : :
1065 : 0 : QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1066 : 0 : if ( flags == 0 )
1067 : 0 : flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1068 : :
1069 : 0 : PointSet *line = mapShape;
1070 : 0 : int nbPoints = line->nbPoints;
1071 : 0 : std::vector< double > &x = line->x;
1072 : 0 : std::vector< double > &y = line->y;
1073 : :
1074 : 0 : std::vector< double > segmentLengths( nbPoints - 1 ); // segments lengths distance bw pt[i] && pt[i+1]
1075 : 0 : std::vector< double >distanceToSegment( nbPoints ); // absolute distance bw pt[0] and pt[i] along the line
1076 : :
1077 : 0 : double totalLineLength = 0.0; // line length
1078 : 0 : for ( int i = 0; i < line->nbPoints - 1; i++ )
1079 : : {
1080 : 0 : if ( i == 0 )
1081 : 0 : distanceToSegment[i] = 0;
1082 : : else
1083 : 0 : distanceToSegment[i] = distanceToSegment[i - 1] + segmentLengths[i - 1];
1084 : :
1085 : 0 : segmentLengths[i] = GeomFunction::dist_euc2d( x[i], y[i], x[i + 1], y[i + 1] );
1086 : 0 : totalLineLength += segmentLengths[i];
1087 : 0 : }
1088 : 0 : distanceToSegment[line->nbPoints - 1] = totalLineLength;
1089 : :
1090 : 0 : double lineStepDistance = ( totalLineLength - labelWidth ); // distance to move along line with each candidate
1091 : 0 : double currentDistanceAlongLine = 0;
1092 : :
1093 : 0 : const std::size_t candidateTargetCount = maximumLineCandidates();
1094 : :
1095 : 0 : if ( totalLineLength > labelWidth )
1096 : : {
1097 : 0 : lineStepDistance = std::min( std::min( labelHeight, labelWidth ), lineStepDistance / candidateTargetCount );
1098 : 0 : }
1099 : 0 : else if ( !line->isClosed() ) // line length < label width => centering label position
1100 : : {
1101 : 0 : currentDistanceAlongLine = - ( labelWidth - totalLineLength ) / 2.0;
1102 : 0 : lineStepDistance = -1;
1103 : 0 : totalLineLength = labelWidth;
1104 : 0 : }
1105 : : else
1106 : : {
1107 : : // closed line, not long enough for label => no candidates!
1108 : 0 : currentDistanceAlongLine = std::numeric_limits< double >::max();
1109 : : }
1110 : :
1111 : 0 : const double lineAnchorPoint = totalLineLength * std::min( 0.99, mLF->lineAnchorPercent() ); // don't actually go **all** the way to end of line, just very close to!
1112 : :
1113 : 0 : switch ( mLF->lineAnchorType() )
1114 : : {
1115 : : case QgsLabelLineSettings::AnchorType::HintOnly:
1116 : 0 : break;
1117 : :
1118 : : case QgsLabelLineSettings::AnchorType::Strict:
1119 : 0 : currentDistanceAlongLine = std::min( lineAnchorPoint, totalLineLength * 0.99 - labelWidth );
1120 : 0 : lineStepDistance = -1;
1121 : 0 : break;
1122 : : }
1123 : :
1124 : : double candidateLength;
1125 : : double beta;
1126 : : double candidateStartX, candidateStartY, candidateEndX, candidateEndY;
1127 : 0 : int i = 0;
1128 : 0 : while ( currentDistanceAlongLine <= totalLineLength - labelWidth || mLF->lineAnchorType() == QgsLabelLineSettings::AnchorType::Strict )
1129 : : {
1130 : 0 : if ( pal->isCanceled() )
1131 : : {
1132 : 0 : return lPos.size();
1133 : : }
1134 : :
1135 : : // calculate positions along linestring corresponding to start and end of current label candidate
1136 : 0 : line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine, &candidateStartX, &candidateStartY );
1137 : 0 : line->getPointByDistance( segmentLengths.data(), distanceToSegment.data(), currentDistanceAlongLine + labelWidth, &candidateEndX, &candidateEndY );
1138 : :
1139 : 0 : if ( currentDistanceAlongLine < 0 )
1140 : : {
1141 : : // label is bigger than line, use whole available line
1142 : 0 : candidateLength = std::sqrt( ( x[nbPoints - 1] - x[0] ) * ( x[nbPoints - 1] - x[0] )
1143 : 0 : + ( y[nbPoints - 1] - y[0] ) * ( y[nbPoints - 1] - y[0] ) );
1144 : 0 : }
1145 : : else
1146 : : {
1147 : 0 : candidateLength = std::sqrt( ( candidateEndX - candidateStartX ) * ( candidateEndX - candidateStartX ) + ( candidateEndY - candidateStartY ) * ( candidateEndY - candidateStartY ) );
1148 : : }
1149 : :
1150 : 0 : cost = candidateLength / labelWidth;
1151 : 0 : if ( cost > 0.98 )
1152 : 0 : cost = 0.0001;
1153 : : else
1154 : : {
1155 : : // jaggy line has a greater cost
1156 : 0 : cost = ( 1 - cost ) / 100; // ranges from 0.0001 to 0.01 (however a cost 0.005 is already a lot!)
1157 : : }
1158 : :
1159 : : // penalize positions which are further from the line's anchor point
1160 : 0 : double costCenter = std::fabs( lineAnchorPoint - ( currentDistanceAlongLine + labelWidth / 2 ) ) / totalLineLength; // <0, 0.5>
1161 : 0 : cost += costCenter / 1000; // < 0, 0.0005 >
1162 : 0 : cost += initialCost;
1163 : :
1164 : 0 : if ( qgsDoubleNear( candidateEndY, candidateStartY ) && qgsDoubleNear( candidateEndX, candidateStartX ) )
1165 : : {
1166 : 0 : angle = 0.0;
1167 : 0 : }
1168 : : else
1169 : 0 : angle = std::atan2( candidateEndY - candidateStartY, candidateEndX - candidateStartX );
1170 : :
1171 : 0 : labelWidth = getLabelWidth( angle );
1172 : 0 : labelHeight = getLabelHeight( angle );
1173 : 0 : beta = angle + M_PI_2;
1174 : :
1175 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Line )
1176 : : {
1177 : : // find out whether the line direction for this candidate is from right to left
1178 : 0 : bool isRightToLeft = ( angle > M_PI_2 || angle <= -M_PI_2 );
1179 : : // meaning of above/below may be reversed if using map orientation and the line has right-to-left direction
1180 : 0 : bool reversed = ( ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? isRightToLeft : false );
1181 : 0 : bool aboveLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) );
1182 : 0 : bool belowLine = ( !reversed && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( reversed && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) );
1183 : :
1184 : 0 : if ( aboveLine )
1185 : : {
1186 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle ) )
1187 : : {
1188 : 0 : const double candidateCost = cost + ( !reversed ? 0 : 0.001 ); // no extra cost for above line placements
1189 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX + std::cos( beta ) *distanceLineToLabel, candidateStartY + std::sin( beta ) *distanceLineToLabel, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1190 : 0 : }
1191 : 0 : }
1192 : 0 : if ( belowLine )
1193 : : {
1194 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle ) )
1195 : : {
1196 : 0 : const double candidateCost = cost + ( !reversed ? 0.001 : 0 );
1197 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - std::cos( beta ) * ( distanceLineToLabel + labelHeight ), candidateStartY - std::sin( beta ) * ( distanceLineToLabel + labelHeight ), labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1198 : 0 : }
1199 : 0 : }
1200 : 0 : if ( flags & QgsLabeling::LinePlacementFlag::OnLine )
1201 : : {
1202 : 0 : if ( !mLF->permissibleZonePrepared() || GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle ) )
1203 : : {
1204 : 0 : const double candidateCost = cost + 0.002;
1205 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelHeight * std::cos( beta ) / 2, candidateStartY - labelHeight * std::sin( beta ) / 2, labelWidth, labelHeight, angle, candidateCost, this, isRightToLeft, LabelPosition::QuadrantOver ) ); // Line
1206 : 0 : }
1207 : 0 : }
1208 : 0 : }
1209 : 0 : else if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal )
1210 : : {
1211 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( i, candidateStartX - labelWidth / 2, candidateStartY - labelHeight / 2, labelWidth, labelHeight, 0, cost, this, false, LabelPosition::QuadrantOver ) ); // Line
1212 : 0 : }
1213 : : else
1214 : : {
1215 : : // an invalid arrangement?
1216 : : }
1217 : :
1218 : 0 : currentDistanceAlongLine += lineStepDistance;
1219 : :
1220 : 0 : i++;
1221 : :
1222 : 0 : if ( lineStepDistance < 0 )
1223 : 0 : break;
1224 : : }
1225 : :
1226 : 0 : return lPos.size();
1227 : 0 : }
1228 : :
1229 : 0 : std::unique_ptr< LabelPosition > FeaturePart::curvedPlacementAtOffset( PointSet *mapShape, const std::vector< double> &pathDistances, QgsTextRendererUtils::LabelLineDirection direction, const double offsetAlongLine, bool &labeledLineSegmentIsRightToLeft, bool applyAngleConstraints )
1230 : : {
1231 : 0 : const QgsPrecalculatedTextMetrics *metrics = qgis::down_cast< QgsTextLabelFeature * >( mLF )->textMetrics();
1232 : : Q_ASSERT( metrics );
1233 : :
1234 : 0 : const bool uprightOnly = onlyShowUprightLabels();
1235 : 0 : const double maximumCharacterAngleInside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleInside() ) : -1;
1236 : 0 : const double maximumCharacterAngleOutside = applyAngleConstraints ? std::fabs( qgis::down_cast< QgsTextLabelFeature *>( mLF )->maximumCharacterAngleOutside() ) : -1;
1237 : :
1238 : 0 : std::unique_ptr< QgsTextRendererUtils::CurvePlacementProperties > placement(
1239 : 0 : QgsTextRendererUtils::generateCurvedTextPlacement( *metrics, mapShape->x.data(), mapShape->y.data(), mapShape->nbPoints, pathDistances, offsetAlongLine, direction, maximumCharacterAngleInside, maximumCharacterAngleOutside, uprightOnly )
1240 : : );
1241 : :
1242 : 0 : labeledLineSegmentIsRightToLeft = placement->labeledLineSegmentIsRightToLeft;
1243 : :
1244 : 0 : if ( placement->graphemePlacement.empty() )
1245 : 0 : return nullptr;
1246 : :
1247 : 0 : auto it = placement->graphemePlacement.constBegin();
1248 : 0 : std::unique_ptr< LabelPosition > firstPosition = std::make_unique< LabelPosition >( 0, it->x, it->y, it->width, it->height, it->angle, 0.0001, this, false, LabelPosition::QuadrantOver );
1249 : 0 : firstPosition->setUpsideDownCharCount( placement->upsideDownCharCount );
1250 : 0 : firstPosition->setPartId( it->graphemeIndex );
1251 : 0 : LabelPosition *previousPosition = firstPosition.get();
1252 : 0 : it++;
1253 : 0 : while ( it != placement->graphemePlacement.constEnd() )
1254 : : {
1255 : 0 : std::unique_ptr< LabelPosition > position = std::make_unique< LabelPosition >( 0, it->x, it->y, it->width, it->height, it->angle, 0.0001, this, false, LabelPosition::QuadrantOver );
1256 : 0 : position->setPartId( it->graphemeIndex );
1257 : :
1258 : 0 : LabelPosition *nextPosition = position.get();
1259 : 0 : previousPosition->setNextPart( std::move( position ) );
1260 : 0 : previousPosition = nextPosition;
1261 : 0 : it++;
1262 : 0 : }
1263 : :
1264 : 0 : return firstPosition;
1265 : 0 : }
1266 : :
1267 : 0 : static std::unique_ptr< LabelPosition > _createCurvedCandidate( LabelPosition *lp, double angle, double dist )
1268 : : {
1269 : 0 : std::unique_ptr< LabelPosition > newLp = std::make_unique< LabelPosition >( *lp );
1270 : 0 : newLp->offsetPosition( dist * std::cos( angle + M_PI_2 ), dist * std::sin( angle + M_PI_2 ) );
1271 : 0 : return newLp;
1272 : 0 : }
1273 : :
1274 : 0 : std::size_t FeaturePart::createCurvedCandidatesAlongLine( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, bool allowOverrun, Pal *pal )
1275 : : {
1276 : 0 : const QgsPrecalculatedTextMetrics *li = qgis::down_cast< QgsTextLabelFeature *>( mLF )->textMetrics();
1277 : : Q_ASSERT( li );
1278 : :
1279 : : // label info must be present
1280 : 0 : if ( !li )
1281 : 0 : return 0;
1282 : :
1283 : 0 : const int characterCount = li->count();
1284 : 0 : if ( characterCount == 0 )
1285 : 0 : return 0;
1286 : :
1287 : : // TODO - we may need an explicit penalty for overhanging labels. Currently, they are penalized just because they
1288 : : // are further from the line center, so non-overhanding placements are picked where possible.
1289 : :
1290 : 0 : double totalCharacterWidth = 0;
1291 : 0 : for ( int i = 0; i < characterCount; ++i )
1292 : 0 : totalCharacterWidth += li->characterWidth( i );
1293 : :
1294 : 0 : std::unique_ptr< PointSet > expanded;
1295 : 0 : double shapeLength = mapShape->length();
1296 : :
1297 : 0 : if ( totalRepeats() > 1 )
1298 : 0 : allowOverrun = false;
1299 : :
1300 : : // label overrun should NEVER exceed the label length (or labels would sit off in space).
1301 : : // in fact, let's require that a minimum of 5% of the label text has to sit on the feature,
1302 : : // as we don't want a label sitting right at the start or end corner of a line
1303 : 0 : double overrun = std::min( mLF->overrunDistance(), totalCharacterWidth * 0.95 );
1304 : 0 : if ( totalCharacterWidth > shapeLength )
1305 : : {
1306 : 0 : if ( !allowOverrun || shapeLength < totalCharacterWidth - 2 * overrun )
1307 : : {
1308 : : // label doesn't fit on this line, don't waste time trying to make candidates
1309 : 0 : return 0;
1310 : : }
1311 : 0 : }
1312 : :
1313 : 0 : if ( allowOverrun && overrun > 0 )
1314 : : {
1315 : : // expand out line on either side to fit label
1316 : 0 : expanded = mapShape->clone();
1317 : 0 : expanded->extendLineByDistance( overrun, overrun, mLF->overrunSmoothDistance() );
1318 : 0 : mapShape = expanded.get();
1319 : 0 : shapeLength = mapShape->length();
1320 : 0 : }
1321 : :
1322 : : // distance calculation
1323 : 0 : std::vector< double > path_distances( mapShape->nbPoints );
1324 : 0 : double total_distance = 0;
1325 : 0 : double old_x = -1.0, old_y = -1.0;
1326 : 0 : for ( int i = 0; i < mapShape->nbPoints; i++ )
1327 : : {
1328 : 0 : if ( i == 0 )
1329 : 0 : path_distances[i] = 0;
1330 : : else
1331 : 0 : path_distances[i] = std::sqrt( std::pow( old_x - mapShape->x[i], 2 ) + std::pow( old_y - mapShape->y[i], 2 ) );
1332 : 0 : old_x = mapShape->x[i];
1333 : 0 : old_y = mapShape->y[i];
1334 : :
1335 : 0 : total_distance += path_distances[i];
1336 : 0 : }
1337 : :
1338 : 0 : if ( qgsDoubleNear( total_distance, 0.0 ) )
1339 : : {
1340 : 0 : return 0;
1341 : : }
1342 : :
1343 : 0 : const double lineAnchorPoint = total_distance * mLF->lineAnchorPercent();
1344 : :
1345 : 0 : if ( pal->isCanceled() )
1346 : 0 : return 0;
1347 : :
1348 : 0 : std::vector< std::unique_ptr< LabelPosition >> positions;
1349 : 0 : const std::size_t candidateTargetCount = maximumLineCandidates();
1350 : 0 : double delta = std::max( li->characterHeight() / 6, total_distance / candidateTargetCount );
1351 : :
1352 : 0 : QgsLabeling::LinePlacementFlags flags = mLF->arrangementFlags();
1353 : 0 : if ( flags == 0 )
1354 : 0 : flags = QgsLabeling::LinePlacementFlag::OnLine; // default flag
1355 : :
1356 : : // generate curved labels
1357 : 0 : double distanceAlongLineToStartCandidate = 0;
1358 : 0 : bool singleCandidateOnly = false;
1359 : 0 : switch ( mLF->lineAnchorType() )
1360 : : {
1361 : : case QgsLabelLineSettings::AnchorType::HintOnly:
1362 : 0 : break;
1363 : :
1364 : : case QgsLabelLineSettings::AnchorType::Strict:
1365 : 0 : distanceAlongLineToStartCandidate = std::min( lineAnchorPoint, total_distance * 0.99 - getLabelWidth() );
1366 : 0 : singleCandidateOnly = true;
1367 : 0 : break;
1368 : : }
1369 : :
1370 : 0 : for ( ; distanceAlongLineToStartCandidate <= total_distance; distanceAlongLineToStartCandidate += delta )
1371 : : {
1372 : :
1373 : 0 : if ( pal->isCanceled() )
1374 : 0 : return 0;
1375 : :
1376 : : // placements may need to be reversed if using map orientation and the line has right-to-left direction
1377 : 0 : bool labeledLineSegmentIsRightToLeft = false;
1378 : 0 : const QgsTextRendererUtils::LabelLineDirection direction = ( flags & QgsLabeling::LinePlacementFlag::MapOrientation ) ? QgsTextRendererUtils::RespectPainterOrientation : QgsTextRendererUtils::FollowLineDirection;
1379 : :
1380 : 0 : std::unique_ptr< LabelPosition > slp = curvedPlacementAtOffset( mapShape, path_distances, direction, distanceAlongLineToStartCandidate, labeledLineSegmentIsRightToLeft, !singleCandidateOnly );
1381 : 0 : if ( !slp )
1382 : 0 : continue;
1383 : :
1384 : : // evaluate cost
1385 : 0 : double angle_diff = 0.0, angle_last = 0.0, diff;
1386 : 0 : LabelPosition *tmp = slp.get();
1387 : 0 : double sin_avg = 0, cos_avg = 0;
1388 : 0 : while ( tmp )
1389 : : {
1390 : 0 : if ( tmp != slp.get() ) // not first?
1391 : : {
1392 : 0 : diff = std::fabs( tmp->getAlpha() - angle_last );
1393 : 0 : if ( diff > 2 * M_PI ) diff -= 2 * M_PI;
1394 : 0 : diff = std::min( diff, 2 * M_PI - diff ); // difference 350 deg is actually just 10 deg...
1395 : 0 : angle_diff += diff;
1396 : 0 : }
1397 : :
1398 : 0 : sin_avg += std::sin( tmp->getAlpha() );
1399 : 0 : cos_avg += std::cos( tmp->getAlpha() );
1400 : 0 : angle_last = tmp->getAlpha();
1401 : 0 : tmp = tmp->nextPart();
1402 : : }
1403 : :
1404 : : // if anchor placement is towards start or end of line, we need to slightly tweak the costs to ensure that the
1405 : : // anchor weighting is sufficient to push labels towards start/end
1406 : 0 : const bool anchorIsFlexiblePlacement = !singleCandidateOnly && mLF->lineAnchorPercent() > 0.1 && mLF->lineAnchorPercent() < 0.9;
1407 : 0 : double angle_diff_avg = characterCount > 1 ? ( angle_diff / ( characterCount - 1 ) ) : 0; // <0, pi> but pi/8 is much already
1408 : 0 : double cost = angle_diff_avg / 100; // <0, 0.031 > but usually <0, 0.003 >
1409 : 0 : if ( cost < 0.0001 )
1410 : 0 : cost = 0.0001;
1411 : :
1412 : : // penalize positions which are further from the line's anchor point
1413 : 0 : double labelCenter = distanceAlongLineToStartCandidate + getLabelWidth() / 2;
1414 : 0 : double costCenter = std::fabs( lineAnchorPoint - labelCenter ) / total_distance; // <0, 0.5>
1415 : 0 : cost += costCenter / ( anchorIsFlexiblePlacement ? 100 : 10 ); // < 0, 0.005 >, or <0, 0.05> if preferring placement close to start/end of line
1416 : 0 : slp->setCost( cost );
1417 : :
1418 : : // average angle is calculated with respect to periodicity of angles
1419 : 0 : double angle_avg = std::atan2( sin_avg / characterCount, cos_avg / characterCount );
1420 : : // displacement - we loop through 3 times, generating above, online then below line placements successively
1421 : 0 : for ( int i = 0; i <= 2; ++i )
1422 : : {
1423 : 0 : std::unique_ptr< LabelPosition > p;
1424 : 0 : if ( i == 0 && ( ( !labeledLineSegmentIsRightToLeft && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) || ( labeledLineSegmentIsRightToLeft && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) ) )
1425 : : {
1426 : : // labels "above" line
1427 : 0 : p = _createCurvedCandidate( slp.get(), angle_avg, mLF->distLabel() + li->characterHeight() / 2 );
1428 : 0 : }
1429 : 0 : if ( i == 1 && flags & QgsLabeling::LinePlacementFlag::OnLine )
1430 : : {
1431 : : // labels on line
1432 : 0 : p = _createCurvedCandidate( slp.get(), angle_avg, 0 );
1433 : 0 : p->setCost( p->cost() + 0.002 );
1434 : 0 : }
1435 : 0 : if ( i == 2 && ( ( !labeledLineSegmentIsRightToLeft && ( flags & QgsLabeling::LinePlacementFlag::BelowLine ) ) || ( labeledLineSegmentIsRightToLeft && ( flags & QgsLabeling::LinePlacementFlag::AboveLine ) ) ) )
1436 : : {
1437 : : // labels "below" line
1438 : 0 : p = _createCurvedCandidate( slp.get(), angle_avg, -li->characterHeight() / 2 - mLF->distLabel() );
1439 : 0 : p->setCost( p->cost() + 0.001 );
1440 : 0 : }
1441 : :
1442 : 0 : if ( p && mLF->permissibleZonePrepared() )
1443 : : {
1444 : 0 : bool within = true;
1445 : 0 : LabelPosition *currentPos = p.get();
1446 : 0 : while ( within && currentPos )
1447 : : {
1448 : 0 : within = GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), currentPos->getX(), currentPos->getY(), currentPos->getWidth(), currentPos->getHeight(), currentPos->getAlpha() );
1449 : 0 : currentPos = currentPos->nextPart();
1450 : : }
1451 : 0 : if ( !within )
1452 : : {
1453 : 0 : p.reset();
1454 : 0 : }
1455 : 0 : }
1456 : :
1457 : 0 : if ( p )
1458 : 0 : positions.emplace_back( std::move( p ) );
1459 : 0 : }
1460 : 0 : if ( singleCandidateOnly )
1461 : 0 : break;
1462 : 0 : }
1463 : :
1464 : 0 : for ( std::unique_ptr< LabelPosition > &pos : positions )
1465 : : {
1466 : 0 : lPos.emplace_back( std::move( pos ) );
1467 : : }
1468 : :
1469 : 0 : return positions.size();
1470 : 0 : }
1471 : :
1472 : : /*
1473 : : * seg 2
1474 : : * pt3 ____________pt2
1475 : : * ¦ ¦
1476 : : * ¦ ¦
1477 : : * seg 3 ¦ BBOX ¦ seg 1
1478 : : * ¦ ¦
1479 : : * ¦____________¦
1480 : : * pt0 seg 0 pt1
1481 : : *
1482 : : */
1483 : :
1484 : 0 : std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_ptr< LabelPosition > > &lPos, PointSet *mapShape, Pal *pal )
1485 : : {
1486 : 0 : double labelWidth = getLabelWidth();
1487 : 0 : double labelHeight = getLabelHeight();
1488 : :
1489 : 0 : const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1490 : 0 : const std::size_t targetPolygonCandidates = maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * area() ) ) )
1491 : : : 0;
1492 : :
1493 : 0 : const double totalArea = area();
1494 : :
1495 : 0 : mapShape->parent = nullptr;
1496 : :
1497 : 0 : if ( pal->isCanceled() )
1498 : 0 : return 0;
1499 : :
1500 : 0 : QLinkedList<PointSet *> shapes_final = splitPolygons( mapShape, labelWidth, labelHeight );
1501 : : #if 0
1502 : : QgsDebugMsg( QStringLiteral( "PAL split polygons resulted in:" ) );
1503 : : for ( PointSet *ps : shapes_final )
1504 : : {
1505 : : QgsDebugMsg( ps->toWkt() );
1506 : : }
1507 : : #endif
1508 : :
1509 : 0 : std::size_t nbp = 0;
1510 : :
1511 : 0 : if ( !shapes_final.isEmpty() )
1512 : : {
1513 : 0 : int id = 0; // ids for candidates
1514 : : double dlx, dly; // delta from label center and bottom-left corner
1515 : 0 : double alpha = 0.0; // rotation for the label
1516 : : double px, py;
1517 : :
1518 : : double beta;
1519 : 0 : double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
1520 : : double rx, ry;
1521 : 0 : std::vector< OrientedConvexHullBoundingBox > boxes;
1522 : 0 : boxes.reserve( shapes_final.size() );
1523 : :
1524 : : // Compute bounding box for each finalShape
1525 : 0 : while ( !shapes_final.isEmpty() )
1526 : : {
1527 : 0 : PointSet *shape = shapes_final.takeFirst();
1528 : 0 : bool ok = false;
1529 : 0 : OrientedConvexHullBoundingBox box = shape->computeConvexHullOrientedBoundingBox( ok );
1530 : 0 : if ( ok )
1531 : 0 : boxes.emplace_back( box );
1532 : :
1533 : 0 : if ( shape->parent )
1534 : 0 : delete shape;
1535 : : }
1536 : :
1537 : 0 : if ( pal->isCanceled() )
1538 : 0 : return 0;
1539 : :
1540 : 0 : double densityX = 1.0 / std::sqrt( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() );
1541 : 0 : double densityY = densityX;
1542 : 0 : int numTry = 0;
1543 : :
1544 : : //fit in polygon only mode slows down calculation a lot, so if it's enabled
1545 : : //then use a smaller limit for number of iterations
1546 : 0 : int maxTry = mLF->permissibleZonePrepared() ? 7 : 10;
1547 : :
1548 : 0 : std::size_t numberCandidatesGenerated = 0;
1549 : :
1550 : 0 : do
1551 : : {
1552 : 0 : for ( OrientedConvexHullBoundingBox &box : boxes )
1553 : : {
1554 : : // there is two possibilities here:
1555 : : // 1. no maximum candidates for polygon setting is in effect (i.e. maxPolygonCandidates == 0). In that case,
1556 : : // we base our dx/dy on the current maximumPolygonCandidatesPerMapUnitSquared value. That should give us the desired
1557 : : // density of candidates straight up. Easy!
1558 : : // 2. a maximum candidate setting IS in effect. In that case, we want to generate a good initial estimate for dx/dy
1559 : : // which gives us a good spatial coverage of the polygon while roughly matching the desired maximum number of candidates.
1560 : : // If dx/dy is too small, then too many candidates will be generated, which is both slow AND results in poor coverage of the
1561 : : // polygon (after culling candidates to the max number, only those clustered around the polygon's pole of inaccessibility
1562 : : // will remain).
1563 : 0 : double dx = densityX;
1564 : 0 : double dy = densityY;
1565 : 0 : if ( numTry == 0 && maxPolygonCandidates > 0 )
1566 : : {
1567 : : // scale maxPolygonCandidates for just this convex hull
1568 : 0 : const double boxArea = box.width * box.length;
1569 : 0 : double maxThisBox = targetPolygonCandidates * boxArea / totalArea;
1570 : 0 : dx = std::max( dx, std::sqrt( boxArea / maxThisBox ) * 0.8 );
1571 : 0 : dy = dx;
1572 : 0 : }
1573 : :
1574 : 0 : if ( pal->isCanceled() )
1575 : 0 : return numberCandidatesGenerated;
1576 : :
1577 : 0 : if ( ( box.length * box.width ) > ( xmax - xmin ) * ( ymax - ymin ) * 5 )
1578 : : {
1579 : : // Very Large BBOX (should never occur)
1580 : 0 : continue;
1581 : : }
1582 : :
1583 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal && mLF->permissibleZonePrepared() )
1584 : : {
1585 : : //check width/height of bbox is sufficient for label
1586 : 0 : if ( mLF->permissibleZone().boundingBox().width() < labelWidth ||
1587 : 0 : mLF->permissibleZone().boundingBox().height() < labelHeight )
1588 : : {
1589 : : //no way label can fit in this box, skip it
1590 : 0 : continue;
1591 : : }
1592 : 0 : }
1593 : :
1594 : 0 : bool enoughPlace = false;
1595 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Free )
1596 : : {
1597 : 0 : enoughPlace = true;
1598 : 0 : px = ( box.x[0] + box.x[2] ) / 2 - labelWidth;
1599 : 0 : py = ( box.y[0] + box.y[2] ) / 2 - labelHeight;
1600 : : int i, j;
1601 : :
1602 : : // Virtual label: center on bbox center, label size = 2x original size
1603 : : // alpha = 0.
1604 : : // If all corner are in bbox then place candidates horizontaly
1605 : 0 : for ( rx = px, i = 0; i < 2; rx = rx + 2 * labelWidth, i++ )
1606 : : {
1607 : 0 : for ( ry = py, j = 0; j < 2; ry = ry + 2 * labelHeight, j++ )
1608 : : {
1609 : 0 : if ( !mapShape->containsPoint( rx, ry ) )
1610 : : {
1611 : 0 : enoughPlace = false;
1612 : 0 : break;
1613 : : }
1614 : 0 : }
1615 : 0 : if ( !enoughPlace )
1616 : : {
1617 : 0 : break;
1618 : : }
1619 : 0 : }
1620 : :
1621 : 0 : } // arrangement== FREE ?
1622 : :
1623 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal || enoughPlace )
1624 : : {
1625 : 0 : alpha = 0.0; // HORIZ
1626 : 0 : }
1627 : 0 : else if ( box.length > 1.5 * labelWidth && box.width > 1.5 * labelWidth )
1628 : : {
1629 : 0 : if ( box.alpha <= M_PI_4 )
1630 : : {
1631 : 0 : alpha = box.alpha;
1632 : 0 : }
1633 : : else
1634 : : {
1635 : 0 : alpha = box.alpha - M_PI_2;
1636 : : }
1637 : 0 : }
1638 : 0 : else if ( box.length > box.width )
1639 : : {
1640 : 0 : alpha = box.alpha - M_PI_2;
1641 : 0 : }
1642 : : else
1643 : : {
1644 : 0 : alpha = box.alpha;
1645 : : }
1646 : :
1647 : 0 : beta = std::atan2( labelHeight, labelWidth ) + alpha;
1648 : :
1649 : :
1650 : : //alpha = box->alpha;
1651 : :
1652 : : // delta from label center and down-left corner
1653 : 0 : dlx = std::cos( beta ) * diago;
1654 : 0 : dly = std::sin( beta ) * diago;
1655 : :
1656 : 0 : double px0 = box.width / 2.0;
1657 : 0 : double py0 = box.length / 2.0;
1658 : :
1659 : 0 : px0 -= std::ceil( px0 / dx ) * dx;
1660 : 0 : py0 -= std::ceil( py0 / dy ) * dy;
1661 : :
1662 : 0 : for ( px = px0; px <= box.width; px += dx )
1663 : : {
1664 : 0 : if ( pal->isCanceled() )
1665 : 0 : break;
1666 : :
1667 : 0 : for ( py = py0; py <= box.length; py += dy )
1668 : : {
1669 : :
1670 : 0 : rx = std::cos( box.alpha ) * px + std::cos( box.alpha - M_PI_2 ) * py;
1671 : 0 : ry = std::sin( box.alpha ) * px + std::sin( box.alpha - M_PI_2 ) * py;
1672 : :
1673 : 0 : rx += box.x[0];
1674 : 0 : ry += box.y[0];
1675 : :
1676 : 0 : if ( mLF->permissibleZonePrepared() )
1677 : : {
1678 : 0 : if ( GeomFunction::containsCandidate( mLF->permissibleZonePrepared(), rx - dlx, ry - dly, labelWidth, labelHeight, alpha ) )
1679 : : {
1680 : : // cost is set to minimal value, evaluated later
1681 : 0 : lPos.emplace_back( std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver ) );
1682 : 0 : numberCandidatesGenerated++;
1683 : 0 : }
1684 : 0 : }
1685 : : else
1686 : : {
1687 : : // TODO - this should be an intersection test, not just a contains test of the candidate centroid
1688 : : // because in some cases we would want to allow candidates which mostly overlap the polygon even though
1689 : : // their centroid doesn't overlap (e.g. a "U" shaped polygon)
1690 : : // but the bugs noted in CostCalculator currently prevent this
1691 : 0 : if ( mapShape->containsPoint( rx, ry ) )
1692 : : {
1693 : 0 : std::unique_ptr< LabelPosition > potentialCandidate = std::make_unique< LabelPosition >( id++, rx - dlx, ry - dly, labelWidth, labelHeight, alpha, 0.0001, this, false, LabelPosition::QuadrantOver );
1694 : : // cost is set to minimal value, evaluated later
1695 : 0 : lPos.emplace_back( std::move( potentialCandidate ) );
1696 : 0 : numberCandidatesGenerated++;
1697 : 0 : }
1698 : : }
1699 : 0 : }
1700 : 0 : }
1701 : : } // forall box
1702 : :
1703 : 0 : nbp = numberCandidatesGenerated;
1704 : 0 : if ( maxPolygonCandidates > 0 && nbp < targetPolygonCandidates )
1705 : : {
1706 : 0 : densityX /= 2;
1707 : 0 : densityY /= 2;
1708 : 0 : numTry++;
1709 : 0 : }
1710 : : else
1711 : : {
1712 : 0 : break;
1713 : : }
1714 : 0 : }
1715 : 0 : while ( numTry < maxTry );
1716 : :
1717 : 0 : nbp = numberCandidatesGenerated;
1718 : 0 : }
1719 : : else
1720 : : {
1721 : 0 : nbp = 0;
1722 : : }
1723 : :
1724 : 0 : return nbp;
1725 : 0 : }
1726 : :
1727 : 0 : std::size_t FeaturePart::createCandidatesOutsidePolygon( std::vector<std::unique_ptr<LabelPosition> > &lPos, Pal *pal )
1728 : : {
1729 : : // calculate distance between horizontal lines
1730 : 0 : const std::size_t maxPolygonCandidates = mLF->layer()->maximumPolygonLabelCandidates();
1731 : 0 : std::size_t candidatesCreated = 0;
1732 : :
1733 : 0 : double labelWidth = getLabelWidth();
1734 : 0 : double labelHeight = getLabelHeight();
1735 : 0 : double distanceToLabel = getLabelDistance();
1736 : 0 : const QgsMargins &visualMargin = mLF->visualMargin();
1737 : :
1738 : : /*
1739 : : * From Rylov & Reimer (2016) "A practical algorithm for the external annotation of area features":
1740 : : *
1741 : : * The list of rules adapted to the
1742 : : * needs of externally labelling areal features is as follows:
1743 : : * R1. Labels should be placed horizontally.
1744 : : * R2. Label should be placed entirely outside at some
1745 : : * distance from the area feature.
1746 : : * R3. Name should not cross the boundary of its area
1747 : : * feature.
1748 : : * R4. The name should be placed in way that takes into
1749 : : * account the shape of the feature by achieving a
1750 : : * balance between the feature and its name, emphasizing their relationship.
1751 : : * R5. The lettering to the right and slightly above the
1752 : : * symbol is prioritized.
1753 : : *
1754 : : * In the following subsections we utilize four of the five rules
1755 : : * for two subtasks of label placement, namely, for candidate
1756 : : * positions generation (R1, R2, and R3) and for measuring their
1757 : : * ‘goodness’ (R4). The rule R5 is applicable only in the case when
1758 : : * the area of a polygonal feature is small and the feature can be
1759 : : * treated and labelled as a point-feature
1760 : : */
1761 : :
1762 : : /*
1763 : : * QGIS approach (cite Dawson (2020) if you want ;) )
1764 : : *
1765 : : * We differ from the horizontal sweep line approach described by Rylov & Reimer and instead
1766 : : * rely on just generating a set of points at regular intervals along the boundary of the polygon (exterior ring).
1767 : : *
1768 : : * In practice, this generates similar results as Rylov & Reimer, but has the additional benefits that:
1769 : : * 1. It avoids the need to calculate intersections between the sweep line and the polygon
1770 : : * 2. For horizontal or near horizontal segments, Rylov & Reimer propose generating evenly spaced points along
1771 : : * these segments-- i.e. the same approach as we do for the whole polygon
1772 : : * 3. It's easier to determine in advance exactly how many candidate positions we'll be generating, and accordingly
1773 : : * we can easily pick the distance between points along the exterior ring so that the number of positions generated
1774 : : * matches our target number (targetPolygonCandidates)
1775 : : */
1776 : :
1777 : : // TO consider -- for very small polygons (wrt label size), treat them just like a point feature?
1778 : :
1779 : : double cx, cy;
1780 : 0 : getCentroid( cx, cy, false );
1781 : :
1782 : 0 : GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
1783 : :
1784 : : // be a bit sneaky and only buffer out 50% here, and then do the remaining 50% when we make the label candidate itself.
1785 : : // this avoids candidates being created immediately over the buffered ring and always intersecting with it...
1786 : 0 : geos::unique_ptr buffer( GEOSBuffer_r( ctxt, geos(), distanceToLabel * 0.5, 1 ) );
1787 : 0 : std::unique_ptr< QgsAbstractGeometry> gg( QgsGeos::fromGeos( buffer.get() ) );
1788 : :
1789 : 0 : geos::prepared_unique_ptr preparedBuffer( GEOSPrepare_r( ctxt, buffer.get() ) );
1790 : :
1791 : 0 : const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( gg.get() );
1792 : 0 : if ( !poly )
1793 : 0 : return candidatesCreated;
1794 : :
1795 : 0 : const QgsLineString *ring = qgsgeometry_cast< const QgsLineString *>( poly->exteriorRing() );
1796 : 0 : if ( !ring )
1797 : 0 : return candidatesCreated;
1798 : :
1799 : : // we cheat here -- we don't use the polygon area when calculating the number of candidates, and rather use the perimeter (because that's more relevant,
1800 : : // i.e a loooooong skinny polygon with small area should still generate a large number of candidates)
1801 : 0 : const double ringLength = ring->length();
1802 : 0 : const double circleArea = std::pow( ringLength, 2 ) / ( 4 * M_PI );
1803 : 0 : const std::size_t candidatesForArea = static_cast< std::size_t>( std::ceil( mLF->layer()->mPal->maximumPolygonCandidatesPerMapUnitSquared() * circleArea ) );
1804 : 0 : const std::size_t targetPolygonCandidates = std::max( static_cast< std::size_t >( 16 ), maxPolygonCandidates > 0 ? std::min( maxPolygonCandidates, candidatesForArea ) : candidatesForArea );
1805 : :
1806 : : // assume each position generates one candidate
1807 : 0 : const double delta = ringLength / targetPolygonCandidates;
1808 : 0 : geos::unique_ptr geosPoint;
1809 : :
1810 : 0 : const double maxDistCentroidToLabelX = std::max( xmax - cx, cx - xmin ) + distanceToLabel;
1811 : 0 : const double maxDistCentroidToLabelY = std::max( ymax - cy, cy - ymin ) + distanceToLabel;
1812 : 0 : const double estimateOfMaxPossibleDistanceCentroidToLabel = std::sqrt( maxDistCentroidToLabelX * maxDistCentroidToLabelX + maxDistCentroidToLabelY * maxDistCentroidToLabelY );
1813 : :
1814 : : // Satisfy R1: Labels should be placed horizontally.
1815 : 0 : const double labelAngle = 0;
1816 : :
1817 : 0 : std::size_t i = lPos.size();
1818 : 0 : auto addCandidate = [&]( double x, double y, QgsPalLayerSettings::PredefinedPointPosition position )
1819 : : {
1820 : 0 : double labelX = 0;
1821 : 0 : double labelY = 0;
1822 : 0 : LabelPosition::Quadrant quadrant = LabelPosition::QuadrantAboveLeft;
1823 : :
1824 : : // Satisfy R2: Label should be placed entirely outside at some distance from the area feature.
1825 : 0 : createCandidateAtOrderedPositionOverPoint( labelX, labelY, quadrant, x, y, labelWidth, labelHeight, position, distanceToLabel * 0.5, visualMargin, 0, 0 );
1826 : :
1827 : 0 : std::unique_ptr< LabelPosition > candidate = std::make_unique< LabelPosition >( i, labelX, labelY, labelWidth, labelHeight, labelAngle, 0, this, false, quadrant );
1828 : 0 : if ( candidate->intersects( preparedBuffer.get() ) )
1829 : : {
1830 : : // satisfy R3. Name should not cross the boundary of its area feature.
1831 : :
1832 : : // actually, we use the buffered geometry here, because a label shouldn't be closer to the polygon then the minimum distance value
1833 : 0 : return;
1834 : : }
1835 : :
1836 : : // cost candidates by their distance to the feature's centroid (following Rylov & Reimer)
1837 : :
1838 : : // Satisfy R4. The name should be placed in way that takes into
1839 : : // account the shape of the feature by achieving a
1840 : : // balance between the feature and its name, emphasizing their relationship.
1841 : :
1842 : :
1843 : : // here we deviate a little from R&R, and instead of just calculating the centroid distance
1844 : : // to centroid of label, we calculate the distance from the centroid to the nearest point on the label
1845 : :
1846 : 0 : const double centroidDistance = candidate->getDistanceToPoint( cx, cy );
1847 : 0 : const double centroidCost = centroidDistance / estimateOfMaxPossibleDistanceCentroidToLabel;
1848 : 0 : candidate->setCost( centroidCost );
1849 : :
1850 : 0 : lPos.emplace_back( std::move( candidate ) );
1851 : 0 : candidatesCreated++;
1852 : 0 : ++i;
1853 : 0 : };
1854 : :
1855 : 0 : ring->visitPointsByRegularDistance( delta, [&]( double x, double y, double, double,
1856 : : double startSegmentX, double startSegmentY, double, double,
1857 : : double endSegmentX, double endSegmentY, double, double )
1858 : : {
1859 : : // get normal angle for segment
1860 : 0 : float angle = atan2( static_cast< float >( endSegmentY - startSegmentY ), static_cast< float >( endSegmentX - startSegmentX ) ) * 180 / M_PI;
1861 : 0 : if ( angle < 0 )
1862 : 0 : angle += 360;
1863 : :
1864 : : // adapted fom Rylov & Reimer figure 9
1865 : 0 : if ( angle >= 0 && angle <= 5 )
1866 : : {
1867 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopMiddle );
1868 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1869 : 0 : }
1870 : 0 : else if ( angle <= 85 )
1871 : : {
1872 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1873 : 0 : }
1874 : 0 : else if ( angle <= 90 )
1875 : : {
1876 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopLeft );
1877 : 0 : addCandidate( x, y, QgsPalLayerSettings::MiddleLeft );
1878 : 0 : }
1879 : :
1880 : 0 : else if ( angle <= 95 )
1881 : : {
1882 : 0 : addCandidate( x, y, QgsPalLayerSettings::MiddleLeft );
1883 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1884 : 0 : }
1885 : 0 : else if ( angle <= 175 )
1886 : : {
1887 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1888 : 0 : }
1889 : 0 : else if ( angle <= 180 )
1890 : : {
1891 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomLeft );
1892 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomMiddle );
1893 : 0 : }
1894 : :
1895 : 0 : else if ( angle <= 185 )
1896 : : {
1897 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomMiddle );
1898 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1899 : 0 : }
1900 : 0 : else if ( angle <= 265 )
1901 : : {
1902 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1903 : 0 : }
1904 : 0 : else if ( angle <= 270 )
1905 : : {
1906 : 0 : addCandidate( x, y, QgsPalLayerSettings::BottomRight );
1907 : 0 : addCandidate( x, y, QgsPalLayerSettings::MiddleRight );
1908 : 0 : }
1909 : 0 : else if ( angle <= 275 )
1910 : : {
1911 : 0 : addCandidate( x, y, QgsPalLayerSettings::MiddleRight );
1912 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopRight );
1913 : 0 : }
1914 : 0 : else if ( angle <= 355 )
1915 : : {
1916 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopRight );
1917 : 0 : }
1918 : : else
1919 : : {
1920 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopRight );
1921 : 0 : addCandidate( x, y, QgsPalLayerSettings::TopMiddle );
1922 : : }
1923 : :
1924 : 0 : return !pal->isCanceled();
1925 : : } );
1926 : :
1927 : 0 : return candidatesCreated;
1928 : 0 : }
1929 : :
1930 : 0 : std::vector< std::unique_ptr< LabelPosition > > FeaturePart::createCandidates( Pal *pal )
1931 : : {
1932 : 0 : std::vector< std::unique_ptr< LabelPosition > > lPos;
1933 : 0 : double angle = mLF->hasFixedAngle() ? mLF->fixedAngle() : 0.0;
1934 : :
1935 : 0 : if ( mLF->hasFixedPosition() )
1936 : : {
1937 : 0 : lPos.emplace_back( std::make_unique< LabelPosition> ( 0, mLF->fixedPosition().x(), mLF->fixedPosition().y(), getLabelWidth( angle ), getLabelHeight( angle ), angle, 0.0, this, false, LabelPosition::Quadrant::QuadrantOver ) );
1938 : 0 : }
1939 : : else
1940 : : {
1941 : 0 : switch ( type )
1942 : : {
1943 : : case GEOS_POINT:
1944 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::OrderedPositionsAroundPoint )
1945 : 0 : createCandidatesAtOrderedPositionsOverPoint( x[0], y[0], lPos, angle );
1946 : 0 : else if ( mLF->layer()->arrangement() == QgsPalLayerSettings::OverPoint || mLF->hasFixedQuadrant() )
1947 : 0 : createCandidatesOverPoint( x[0], y[0], lPos, angle );
1948 : : else
1949 : 0 : createCandidatesAroundPoint( x[0], y[0], lPos, angle );
1950 : 0 : break;
1951 : :
1952 : : case GEOS_LINESTRING:
1953 : 0 : if ( mLF->layer()->arrangement() == QgsPalLayerSettings::Horizontal )
1954 : 0 : createHorizontalCandidatesAlongLine( lPos, this, pal );
1955 : 0 : else if ( mLF->layer()->isCurved() )
1956 : 0 : createCurvedCandidatesAlongLine( lPos, this, true, pal );
1957 : : else
1958 : 0 : createCandidatesAlongLine( lPos, this, true, pal );
1959 : 0 : break;
1960 : :
1961 : : case GEOS_POLYGON:
1962 : : {
1963 : 0 : const double labelWidth = getLabelWidth();
1964 : 0 : const double labelHeight = getLabelHeight();
1965 : :
1966 : 0 : const bool allowOutside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementOutsideOfPolygon;
1967 : 0 : const bool allowInside = mLF->polygonPlacementFlags() & QgsLabeling::PolygonPlacementFlag::AllowPlacementInsideOfPolygon;
1968 : : //check width/height of bbox is sufficient for label
1969 : :
1970 : 0 : if ( ( allowOutside && !allowInside ) || ( mLF->layer()->arrangement() == QgsPalLayerSettings::OutsidePolygons ) )
1971 : : {
1972 : : // only allowed to place outside of polygon
1973 : 0 : createCandidatesOutsidePolygon( lPos, pal );
1974 : 0 : }
1975 : 0 : else if ( allowOutside && ( std::fabs( xmax - xmin ) < labelWidth ||
1976 : 0 : std::fabs( ymax - ymin ) < labelHeight ) )
1977 : : {
1978 : : //no way label can fit in this polygon -- shortcut and only place label outside
1979 : 0 : createCandidatesOutsidePolygon( lPos, pal );
1980 : 0 : }
1981 : : else
1982 : : {
1983 : 0 : std::size_t created = 0;
1984 : 0 : if ( allowInside )
1985 : : {
1986 : 0 : switch ( mLF->layer()->arrangement() )
1987 : : {
1988 : : case QgsPalLayerSettings::AroundPoint:
1989 : : {
1990 : : double cx, cy;
1991 : 0 : getCentroid( cx, cy, mLF->layer()->centroidInside() );
1992 : 0 : if ( qgsDoubleNear( mLF->distLabel(), 0.0 ) )
1993 : 0 : created += createCandidateCenteredOverPoint( cx, cy, lPos, angle );
1994 : 0 : created += createCandidatesAroundPoint( cx, cy, lPos, angle );
1995 : 0 : break;
1996 : : }
1997 : : case QgsPalLayerSettings::OverPoint:
1998 : : {
1999 : : double cx, cy;
2000 : 0 : getCentroid( cx, cy, mLF->layer()->centroidInside() );
2001 : 0 : created += createCandidatesOverPoint( cx, cy, lPos, angle );
2002 : 0 : break;
2003 : : }
2004 : : case QgsPalLayerSettings::Line:
2005 : 0 : created += createCandidatesAlongLine( lPos, this, false, pal );
2006 : 0 : break;
2007 : : case QgsPalLayerSettings::PerimeterCurved:
2008 : 0 : created += createCurvedCandidatesAlongLine( lPos, this, false, pal );
2009 : 0 : break;
2010 : : default:
2011 : 0 : created += createCandidatesForPolygon( lPos, this, pal );
2012 : 0 : break;
2013 : : }
2014 : 0 : }
2015 : :
2016 : 0 : if ( allowOutside )
2017 : : {
2018 : : // add fallback for labels outside the polygon
2019 : 0 : createCandidatesOutsidePolygon( lPos, pal );
2020 : :
2021 : 0 : if ( created > 0 )
2022 : : {
2023 : : // TODO (maybe) increase cost for outside placements (i.e. positions at indices >= created)?
2024 : : // From my initial testing this doesn't seem necessary
2025 : 0 : }
2026 : 0 : }
2027 : : }
2028 : : }
2029 : 0 : }
2030 : : }
2031 : :
2032 : 0 : return lPos;
2033 : 0 : }
2034 : :
2035 : 0 : void FeaturePart::addSizePenalty( std::vector< std::unique_ptr< LabelPosition > > &lPos, double bbx[4], double bby[4] )
2036 : : {
2037 : 0 : if ( !mGeos )
2038 : 0 : createGeosGeom();
2039 : :
2040 : 0 : GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2041 : 0 : int geomType = GEOSGeomTypeId_r( ctxt, mGeos );
2042 : :
2043 : 0 : double sizeCost = 0;
2044 : 0 : if ( geomType == GEOS_LINESTRING )
2045 : : {
2046 : 0 : const double l = length();
2047 : 0 : if ( l <= 0 )
2048 : 0 : return; // failed to calculate length
2049 : 0 : double bbox_length = std::max( bbx[2] - bbx[0], bby[2] - bby[0] );
2050 : 0 : if ( l >= bbox_length / 4 )
2051 : 0 : return; // the line is longer than quarter of height or width - don't penalize it
2052 : :
2053 : 0 : sizeCost = 1 - ( l / ( bbox_length / 4 ) ); // < 0,1 >
2054 : 0 : }
2055 : 0 : else if ( geomType == GEOS_POLYGON )
2056 : : {
2057 : 0 : const double a = area();
2058 : 0 : if ( a <= 0 )
2059 : 0 : return;
2060 : 0 : double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
2061 : 0 : if ( a >= bbox_area / 16 )
2062 : 0 : return; // covers more than 1/16 of our view - don't penalize it
2063 : :
2064 : 0 : sizeCost = 1 - ( a / ( bbox_area / 16 ) ); // < 0, 1 >
2065 : 0 : }
2066 : : else
2067 : 0 : return; // no size penalty for points
2068 : :
2069 : : // apply the penalty
2070 : 0 : for ( std::unique_ptr< LabelPosition > &pos : lPos )
2071 : : {
2072 : 0 : pos->setCost( pos->cost() + sizeCost / 100 );
2073 : : }
2074 : 0 : }
2075 : :
2076 : 0 : bool FeaturePart::isConnected( FeaturePart *p2 )
2077 : : {
2078 : 0 : if ( !p2->mGeos )
2079 : 0 : p2->createGeosGeom();
2080 : :
2081 : : try
2082 : : {
2083 : 0 : return ( GEOSPreparedTouches_r( QgsGeos::getGEOSHandler(), preparedGeom(), p2->mGeos ) == 1 );
2084 : 0 : }
2085 : : catch ( GEOSException &e )
2086 : : {
2087 : 0 : qWarning( "GEOS exception: %s", e.what() );
2088 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2089 : 0 : return false;
2090 : 0 : }
2091 : 0 : }
2092 : :
2093 : 0 : bool FeaturePart::mergeWithFeaturePart( FeaturePart *other )
2094 : : {
2095 : 0 : if ( !mGeos )
2096 : 0 : createGeosGeom();
2097 : 0 : if ( !other->mGeos )
2098 : 0 : other->createGeosGeom();
2099 : :
2100 : 0 : GEOSContextHandle_t ctxt = QgsGeos::getGEOSHandler();
2101 : : try
2102 : : {
2103 : 0 : GEOSGeometry *g1 = GEOSGeom_clone_r( ctxt, mGeos );
2104 : 0 : GEOSGeometry *g2 = GEOSGeom_clone_r( ctxt, other->mGeos );
2105 : 0 : GEOSGeometry *geoms[2] = { g1, g2 };
2106 : 0 : geos::unique_ptr g( GEOSGeom_createCollection_r( ctxt, GEOS_MULTILINESTRING, geoms, 2 ) );
2107 : 0 : geos::unique_ptr gTmp( GEOSLineMerge_r( ctxt, g.get() ) );
2108 : :
2109 : 0 : if ( GEOSGeomTypeId_r( ctxt, gTmp.get() ) != GEOS_LINESTRING )
2110 : : {
2111 : : // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
2112 : 0 : return false;
2113 : : }
2114 : 0 : invalidateGeos();
2115 : :
2116 : : // set up new geometry
2117 : 0 : mGeos = gTmp.release();
2118 : 0 : mOwnsGeom = true;
2119 : :
2120 : 0 : deleteCoords();
2121 : 0 : qDeleteAll( mHoles );
2122 : 0 : mHoles.clear();
2123 : 0 : extractCoords( mGeos );
2124 : 0 : return true;
2125 : 0 : }
2126 : : catch ( GEOSException &e )
2127 : : {
2128 : 0 : qWarning( "GEOS exception: %s", e.what() );
2129 : 0 : QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
2130 : 0 : return false;
2131 : 0 : }
2132 : 0 : }
2133 : :
2134 : 0 : double FeaturePart::calculatePriority() const
2135 : : {
2136 : 0 : if ( mLF->alwaysShow() )
2137 : : {
2138 : : //if feature is set to always show, bump the priority up by orders of magnitude
2139 : : //so that other feature's labels are unlikely to be placed over the label for this feature
2140 : : //(negative numbers due to how pal::extract calculates inactive cost)
2141 : 0 : return -0.2;
2142 : : }
2143 : :
2144 : 0 : return mLF->priority() >= 0 ? mLF->priority() : mLF->layer()->priority();
2145 : 0 : }
2146 : :
2147 : 0 : bool FeaturePart::onlyShowUprightLabels() const
2148 : : {
2149 : 0 : bool uprightLabel = false;
2150 : :
2151 : 0 : switch ( mLF->layer()->upsidedownLabels() )
2152 : : {
2153 : : case Layer::Upright:
2154 : 0 : uprightLabel = true;
2155 : 0 : break;
2156 : : case Layer::ShowDefined:
2157 : : // upright only dynamic labels
2158 : 0 : if ( !hasFixedRotation() || ( !hasFixedPosition() && fixedAngle() == 0.0 ) )
2159 : : {
2160 : 0 : uprightLabel = true;
2161 : 0 : }
2162 : 0 : break;
2163 : : case Layer::ShowAll:
2164 : 0 : break;
2165 : : default:
2166 : 0 : uprightLabel = true;
2167 : 0 : }
2168 : 0 : return uprightLabel;
2169 : : }
2170 : :
|
