QGIS API Documentation  3.10.0-A Coruña (6c816b4204)
qgsinternalgeometryengine.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsinternalgeometryengine.cpp - QgsInternalGeometryEngine
3 
4  ---------------------
5  begin : 13.1.2016
6  copyright : (C) 2016 by Matthias Kuhn
7  email : [email protected]
8  ***************************************************************************
9  * *
10  * This program is free software; you can redistribute it and/or modify *
11  * it under the terms of the GNU General Public License as published by *
12  * the Free Software Foundation; either version 2 of the License, or *
13  * (at your option) any later version. *
14  * *
15  ***************************************************************************/
16 
18 
19 #include "qgslinestring.h"
20 #include "qgsmultipolygon.h"
21 #include "qgspolygon.h"
22 #include "qgsmulticurve.h"
23 #include "qgsgeometry.h"
24 #include "qgsgeometryutils.h"
25 #include "qgslinesegment.h"
26 #include "qgscircle.h"
27 #include "qgslogger.h"
28 #include "qgstessellator.h"
29 #include "qgsfeedback.h"
30 #include <QTransform>
31 #include <functional>
32 #include <memory>
33 #include <queue>
34 #include <random>
35 
37  : mGeometry( geometry.constGet() )
38 {
39 
40 }
41 
42 /***************************************************************************
43  * This class is considered CRITICAL and any change MUST be accompanied with
44  * full unit tests.
45  * See details in QEP #17
46  ****************************************************************************/
47 
49 {
50  QVector<QgsLineString *> linesToProcess;
51 
52  const QgsMultiCurve *multiCurve = qgsgeometry_cast< const QgsMultiCurve * >( mGeometry );
53  if ( multiCurve )
54  {
55  linesToProcess.reserve( multiCurve->partCount() );
56  for ( int i = 0; i < multiCurve->partCount(); ++i )
57  {
58  linesToProcess << static_cast<QgsLineString *>( multiCurve->geometryN( i )->clone() );
59  }
60  }
61 
62  const QgsCurve *curve = qgsgeometry_cast< const QgsCurve * >( mGeometry );
63  if ( curve )
64  {
65  linesToProcess << static_cast<QgsLineString *>( curve->segmentize() );
66  }
67 
68  std::unique_ptr<QgsMultiPolygon> multipolygon( linesToProcess.size() > 1 ? new QgsMultiPolygon() : nullptr );
69  QgsPolygon *polygon = nullptr;
70 
71  if ( !linesToProcess.empty() )
72  {
73  std::unique_ptr< QgsLineString > secondline;
74  for ( QgsLineString *line : qgis::as_const( linesToProcess ) )
75  {
76  QTransform transform = QTransform::fromTranslate( x, y );
77 
78  secondline.reset( line->reversed() );
79  secondline->transform( transform );
80 
81  line->append( secondline.get() );
82  line->addVertex( line->pointN( 0 ) );
83 
84  polygon = new QgsPolygon();
85  polygon->setExteriorRing( line );
86 
87  if ( multipolygon )
88  multipolygon->addGeometry( polygon );
89  }
90 
91  if ( multipolygon )
92  return QgsGeometry( multipolygon.release() );
93  else
94  return QgsGeometry( polygon );
95  }
96 
97  return QgsGeometry();
98 }
99 
100 
101 
102 // polylabel implementation
103 // ported from the original JavaScript implementation developed by Vladimir Agafonkin
104 // originally licensed under the ISC License
105 
107 class Cell
108 {
109  public:
110  Cell( double x, double y, double h, const QgsPolygon *polygon )
111  : x( x )
112  , y( y )
113  , h( h )
114  , d( polygon->pointDistanceToBoundary( x, y ) )
115  , max( d + h * M_SQRT2 )
116  {}
117 
119  double x;
121  double y;
123  double h;
125  double d;
127  double max;
128 };
129 
130 struct GreaterThanByMax
131 {
132  bool operator()( const Cell *lhs, const Cell *rhs )
133  {
134  return rhs->max > lhs->max;
135  }
136 };
137 
138 Cell *getCentroidCell( const QgsPolygon *polygon )
139 {
140  double area = 0;
141  double x = 0;
142  double y = 0;
143 
144  const QgsLineString *exterior = static_cast< const QgsLineString *>( polygon->exteriorRing() );
145  int len = exterior->numPoints() - 1; //assume closed
146  for ( int i = 0, j = len - 1; i < len; j = i++ )
147  {
148  double aX = exterior->xAt( i );
149  double aY = exterior->yAt( i );
150  double bX = exterior->xAt( j );
151  double bY = exterior->yAt( j );
152  double f = aX * bY - bX * aY;
153  x += ( aX + bX ) * f;
154  y += ( aY + bY ) * f;
155  area += f * 3;
156  }
157  if ( area == 0 )
158  return new Cell( exterior->xAt( 0 ), exterior->yAt( 0 ), 0, polygon );
159  else
160  return new Cell( x / area, y / area, 0.0, polygon );
161 }
162 
163 QgsPoint surfacePoleOfInaccessibility( const QgsSurface *surface, double precision, double &distanceFromBoundary )
164 {
165  std::unique_ptr< QgsPolygon > segmentizedPoly;
166  const QgsPolygon *polygon = qgsgeometry_cast< const QgsPolygon * >( surface );
167  if ( !polygon )
168  {
169  segmentizedPoly.reset( static_cast< QgsPolygon *>( surface->segmentize() ) );
170  polygon = segmentizedPoly.get();
171  }
172 
173  // start with the bounding box
174  QgsRectangle bounds = polygon->boundingBox();
175 
176  // initial parameters
177  double cellSize = std::min( bounds.width(), bounds.height() );
178 
179  if ( qgsDoubleNear( cellSize, 0.0 ) )
180  return QgsPoint( bounds.xMinimum(), bounds.yMinimum() );
181 
182  double h = cellSize / 2.0;
183  std::priority_queue< Cell *, std::vector<Cell *>, GreaterThanByMax > cellQueue;
184 
185  // cover polygon with initial cells
186  for ( double x = bounds.xMinimum(); x < bounds.xMaximum(); x += cellSize )
187  {
188  for ( double y = bounds.yMinimum(); y < bounds.yMaximum(); y += cellSize )
189  {
190  cellQueue.push( new Cell( x + h, y + h, h, polygon ) );
191  }
192  }
193 
194  // take centroid as the first best guess
195  std::unique_ptr< Cell > bestCell( getCentroidCell( polygon ) );
196 
197  // special case for rectangular polygons
198  std::unique_ptr< Cell > bboxCell( new Cell( bounds.xMinimum() + bounds.width() / 2.0,
199  bounds.yMinimum() + bounds.height() / 2.0,
200  0, polygon ) );
201  if ( bboxCell->d > bestCell->d )
202  {
203  bestCell = std::move( bboxCell );
204  }
205 
206  while ( !cellQueue.empty() )
207  {
208  // pick the most promising cell from the queue
209  std::unique_ptr< Cell > cell( cellQueue.top() );
210  cellQueue.pop();
211  Cell *currentCell = cell.get();
212 
213  // update the best cell if we found a better one
214  if ( currentCell->d > bestCell->d )
215  {
216  bestCell = std::move( cell );
217  }
218 
219  // do not drill down further if there's no chance of a better solution
220  if ( currentCell->max - bestCell->d <= precision )
221  continue;
222 
223  // split the cell into four cells
224  h = currentCell->h / 2.0;
225  cellQueue.push( new Cell( currentCell->x - h, currentCell->y - h, h, polygon ) );
226  cellQueue.push( new Cell( currentCell->x + h, currentCell->y - h, h, polygon ) );
227  cellQueue.push( new Cell( currentCell->x - h, currentCell->y + h, h, polygon ) );
228  cellQueue.push( new Cell( currentCell->x + h, currentCell->y + h, h, polygon ) );
229  }
230 
231  distanceFromBoundary = bestCell->d;
232 
233  return QgsPoint( bestCell->x, bestCell->y );
234 }
235 
237 
238 QgsGeometry QgsInternalGeometryEngine::poleOfInaccessibility( double precision, double *distanceFromBoundary ) const
239 {
240  if ( distanceFromBoundary )
241  *distanceFromBoundary = std::numeric_limits<double>::max();
242 
243  if ( !mGeometry || mGeometry->isEmpty() )
244  return QgsGeometry();
245 
246  if ( precision <= 0 )
247  return QgsGeometry();
248 
249  if ( const QgsGeometryCollection *gc = qgsgeometry_cast< const QgsGeometryCollection *>( mGeometry ) )
250  {
251  int numGeom = gc->numGeometries();
252  double maxDist = 0;
253  QgsPoint bestPoint;
254  bool found = false;
255  for ( int i = 0; i < numGeom; ++i )
256  {
257  const QgsSurface *surface = qgsgeometry_cast< const QgsSurface * >( gc->geometryN( i ) );
258  if ( !surface )
259  continue;
260 
261  found = true;
262  double dist = std::numeric_limits<double>::max();
263  QgsPoint p = surfacePoleOfInaccessibility( surface, precision, dist );
264  if ( dist > maxDist )
265  {
266  maxDist = dist;
267  bestPoint = p;
268  }
269  }
270 
271  if ( !found )
272  return QgsGeometry();
273 
274  if ( distanceFromBoundary )
275  *distanceFromBoundary = maxDist;
276  return QgsGeometry( new QgsPoint( bestPoint ) );
277  }
278  else
279  {
280  const QgsSurface *surface = qgsgeometry_cast< const QgsSurface * >( mGeometry );
281  if ( !surface )
282  return QgsGeometry();
283 
284  double dist = std::numeric_limits<double>::max();
285  QgsPoint p = surfacePoleOfInaccessibility( surface, precision, dist );
286  if ( distanceFromBoundary )
287  *distanceFromBoundary = dist;
288  return QgsGeometry( new QgsPoint( p ) );
289  }
290 }
291 
292 
293 // helpers for orthogonalize
294 // adapted from original code in potlatch/id osm editor
295 
296 bool dotProductWithinAngleTolerance( double dotProduct, double lowerThreshold, double upperThreshold )
297 {
298  return lowerThreshold > std::fabs( dotProduct ) || std::fabs( dotProduct ) > upperThreshold;
299 }
300 
301 double normalizedDotProduct( const QgsPoint &a, const QgsPoint &b, const QgsPoint &c )
302 {
303  QgsVector p = a - b;
304  QgsVector q = c - b;
305 
306  if ( p.length() > 0 )
307  p = p.normalized();
308  if ( q.length() > 0 )
309  q = q.normalized();
310 
311  return p * q;
312 }
313 
314 double squareness( QgsLineString *ring, double lowerThreshold, double upperThreshold )
315 {
316  double sum = 0.0;
317 
318  bool isClosed = ring->isClosed();
319  int numPoints = ring->numPoints();
320  QgsPoint a;
321  QgsPoint b;
322  QgsPoint c;
323 
324  for ( int i = 0; i < numPoints; ++i )
325  {
326  if ( !isClosed && i == numPoints - 1 )
327  break;
328  else if ( !isClosed && i == 0 )
329  {
330  b = ring->pointN( 0 );
331  c = ring->pointN( 1 );
332  }
333  else
334  {
335  if ( i == 0 )
336  {
337  a = ring->pointN( numPoints - 1 );
338  b = ring->pointN( 0 );
339  }
340  if ( i == numPoints - 1 )
341  c = ring->pointN( 0 );
342  else
343  c = ring->pointN( i + 1 );
344 
345  double dotProduct = normalizedDotProduct( a, b, c );
346  if ( !dotProductWithinAngleTolerance( dotProduct, lowerThreshold, upperThreshold ) )
347  continue;
348 
349  sum += 2.0 * std::min( std::fabs( dotProduct - 1.0 ), std::min( std::fabs( dotProduct ), std::fabs( dotProduct + 1 ) ) );
350  }
351  a = b;
352  b = c;
353  }
354 
355  return sum;
356 }
357 
358 QgsVector calcMotion( const QgsPoint &a, const QgsPoint &b, const QgsPoint &c,
359  double lowerThreshold, double upperThreshold )
360 {
361  QgsVector p = a - b;
362  QgsVector q = c - b;
363 
364  if ( qgsDoubleNear( p.length(), 0.0 ) || qgsDoubleNear( q.length(), 0.0 ) )
365  return QgsVector( 0, 0 );
366 
367  // 2.0 is a magic number from the original JOSM source code
368  double scale = 2.0 * std::min( p.length(), q.length() );
369 
370  p = p.normalized();
371  q = q.normalized();
372  double dotProduct = p * q;
373 
374  if ( !dotProductWithinAngleTolerance( dotProduct, lowerThreshold, upperThreshold ) )
375  {
376  return QgsVector( 0, 0 );
377  }
378 
379  // wonderful nasty hack which has survived through JOSM -> id -> QGIS
380  // to deal with almost-straight segments (angle is closer to 180 than to 90/270).
381  if ( dotProduct < -M_SQRT1_2 )
382  dotProduct += 1.0;
383 
384  QgsVector new_v = p + q;
385  // 0.1 magic number from JOSM implementation - think this is to limit each iterative step
386  return new_v.normalized() * ( 0.1 * dotProduct * scale );
387 }
388 
389 QgsLineString *doOrthogonalize( QgsLineString *ring, int iterations, double tolerance, double lowerThreshold, double upperThreshold )
390 {
391  double minScore = std::numeric_limits<double>::max();
392 
393  bool isClosed = ring->isClosed();
394  int numPoints = ring->numPoints();
395 
396  std::unique_ptr< QgsLineString > best( ring->clone() );
397 
398  QVector< QgsVector > /* yep */ motions;
399  motions.reserve( numPoints );
400 
401  for ( int it = 0; it < iterations; ++it )
402  {
403  motions.resize( 0 ); // avoid re-allocations
404 
405  // first loop through an calculate all motions
406  QgsPoint a;
407  QgsPoint b;
408  QgsPoint c;
409  for ( int i = 0; i < numPoints; ++i )
410  {
411  if ( isClosed && i == numPoints - 1 )
412  motions << motions.at( 0 ); //closed ring, so last point follows first point motion
413  else if ( !isClosed && ( i == 0 || i == numPoints - 1 ) )
414  {
415  b = ring->pointN( 0 );
416  c = ring->pointN( 1 );
417  motions << QgsVector( 0, 0 ); //non closed line, leave first/last vertex untouched
418  }
419  else
420  {
421  if ( i == 0 )
422  {
423  a = ring->pointN( numPoints - 1 );
424  b = ring->pointN( 0 );
425  }
426  if ( i == numPoints - 1 )
427  c = ring->pointN( 0 );
428  else
429  c = ring->pointN( i + 1 );
430 
431  motions << calcMotion( a, b, c, lowerThreshold, upperThreshold );
432  }
433  a = b;
434  b = c;
435  }
436 
437  // then apply them
438  for ( int i = 0; i < numPoints; ++i )
439  {
440  ring->setXAt( i, ring->xAt( i ) + motions.at( i ).x() );
441  ring->setYAt( i, ring->yAt( i ) + motions.at( i ).y() );
442  }
443 
444  double newScore = squareness( ring, lowerThreshold, upperThreshold );
445  if ( newScore < minScore )
446  {
447  best.reset( ring->clone() );
448  minScore = newScore;
449  }
450 
451  if ( minScore < tolerance )
452  break;
453  }
454 
455  delete ring;
456 
457  return best.release();
458 }
459 
460 
461 QgsAbstractGeometry *orthogonalizeGeom( const QgsAbstractGeometry *geom, int maxIterations, double tolerance, double lowerThreshold, double upperThreshold )
462 {
463  std::unique_ptr< QgsAbstractGeometry > segmentizedCopy;
464  if ( QgsWkbTypes::isCurvedType( geom->wkbType() ) )
465  {
466  segmentizedCopy.reset( geom->segmentize() );
467  geom = segmentizedCopy.get();
468  }
469 
471  {
472  return doOrthogonalize( static_cast< QgsLineString * >( geom->clone() ),
473  maxIterations, tolerance, lowerThreshold, upperThreshold );
474  }
475  else
476  {
477  // polygon
478  const QgsPolygon *polygon = static_cast< const QgsPolygon * >( geom );
479  QgsPolygon *result = new QgsPolygon();
480 
481  result->setExteriorRing( doOrthogonalize( static_cast< QgsLineString * >( polygon->exteriorRing()->clone() ),
482  maxIterations, tolerance, lowerThreshold, upperThreshold ) );
483  for ( int i = 0; i < polygon->numInteriorRings(); ++i )
484  {
485  result->addInteriorRing( doOrthogonalize( static_cast< QgsLineString * >( polygon->interiorRing( i )->clone() ),
486  maxIterations, tolerance, lowerThreshold, upperThreshold ) );
487  }
488 
489  return result;
490  }
491 }
492 
493 QgsGeometry QgsInternalGeometryEngine::orthogonalize( double tolerance, int maxIterations, double angleThreshold ) const
494 {
495  if ( !mGeometry || ( QgsWkbTypes::geometryType( mGeometry->wkbType() ) != QgsWkbTypes::LineGeometry
496  && QgsWkbTypes::geometryType( mGeometry->wkbType() ) != QgsWkbTypes::PolygonGeometry ) )
497  {
498  return QgsGeometry();
499  }
500 
501  double lowerThreshold = std::cos( ( 90 - angleThreshold ) * M_PI / 180.00 );
502  double upperThreshold = std::cos( angleThreshold * M_PI / 180.0 );
503 
504  if ( const QgsGeometryCollection *gc = qgsgeometry_cast< const QgsGeometryCollection *>( mGeometry ) )
505  {
506  int numGeom = gc->numGeometries();
507  QVector< QgsAbstractGeometry * > geometryList;
508  geometryList.reserve( numGeom );
509  for ( int i = 0; i < numGeom; ++i )
510  {
511  geometryList << orthogonalizeGeom( gc->geometryN( i ), maxIterations, tolerance, lowerThreshold, upperThreshold );
512  }
513 
514  QgsGeometry first = QgsGeometry( geometryList.takeAt( 0 ) );
515  for ( QgsAbstractGeometry *g : qgis::as_const( geometryList ) )
516  {
517  first.addPart( g );
518  }
519  return first;
520  }
521  else
522  {
523  return QgsGeometry( orthogonalizeGeom( mGeometry, maxIterations, tolerance, lowerThreshold, upperThreshold ) );
524  }
525 }
526 
527 // if extraNodesPerSegment < 0, then use distance based mode
528 QgsLineString *doDensify( const QgsLineString *ring, int extraNodesPerSegment = -1, double distance = 1 )
529 {
530  QVector< double > outX;
531  QVector< double > outY;
532  QVector< double > outZ;
533  QVector< double > outM;
534  double multiplier = 1.0 / double( extraNodesPerSegment + 1 );
535 
536  int nPoints = ring->numPoints();
537  outX.reserve( ( extraNodesPerSegment + 1 ) * nPoints );
538  outY.reserve( ( extraNodesPerSegment + 1 ) * nPoints );
539  bool withZ = ring->is3D();
540  if ( withZ )
541  outZ.reserve( ( extraNodesPerSegment + 1 ) * nPoints );
542  bool withM = ring->isMeasure();
543  if ( withM )
544  outM.reserve( ( extraNodesPerSegment + 1 ) * nPoints );
545  double x1 = 0;
546  double x2 = 0;
547  double y1 = 0;
548  double y2 = 0;
549  double z1 = 0;
550  double z2 = 0;
551  double m1 = 0;
552  double m2 = 0;
553  double xOut = 0;
554  double yOut = 0;
555  double zOut = 0;
556  double mOut = 0;
557  int extraNodesThisSegment = extraNodesPerSegment;
558  for ( int i = 0; i < nPoints - 1; ++i )
559  {
560  x1 = ring->xAt( i );
561  x2 = ring->xAt( i + 1 );
562  y1 = ring->yAt( i );
563  y2 = ring->yAt( i + 1 );
564  if ( withZ )
565  {
566  z1 = ring->zAt( i );
567  z2 = ring->zAt( i + 1 );
568  }
569  if ( withM )
570  {
571  m1 = ring->mAt( i );
572  m2 = ring->mAt( i + 1 );
573  }
574 
575  outX << x1;
576  outY << y1;
577  if ( withZ )
578  outZ << z1;
579  if ( withM )
580  outM << m1;
581 
582  if ( extraNodesPerSegment < 0 )
583  {
584  // distance mode
585  extraNodesThisSegment = std::floor( std::sqrt( ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ) ) / distance );
586  if ( extraNodesThisSegment >= 1 )
587  multiplier = 1.0 / ( extraNodesThisSegment + 1 );
588  }
589 
590  for ( int j = 0; j < extraNodesThisSegment; ++j )
591  {
592  double delta = multiplier * ( j + 1 );
593  xOut = x1 + delta * ( x2 - x1 );
594  yOut = y1 + delta * ( y2 - y1 );
595  if ( withZ )
596  zOut = z1 + delta * ( z2 - z1 );
597  if ( withM )
598  mOut = m1 + delta * ( m2 - m1 );
599 
600  outX << xOut;
601  outY << yOut;
602  if ( withZ )
603  outZ << zOut;
604  if ( withM )
605  outM << mOut;
606  }
607  }
608  outX << ring->xAt( nPoints - 1 );
609  outY << ring->yAt( nPoints - 1 );
610  if ( withZ )
611  outZ << ring->zAt( nPoints - 1 );
612  if ( withM )
613  outM << ring->mAt( nPoints - 1 );
614 
615  QgsLineString *result = new QgsLineString( outX, outY, outZ, outM );
616  return result;
617 }
618 
619 QgsAbstractGeometry *densifyGeometry( const QgsAbstractGeometry *geom, int extraNodesPerSegment = 1, double distance = 1 )
620 {
621  std::unique_ptr< QgsAbstractGeometry > segmentizedCopy;
622  if ( QgsWkbTypes::isCurvedType( geom->wkbType() ) )
623  {
624  segmentizedCopy.reset( geom->segmentize() );
625  geom = segmentizedCopy.get();
626  }
627 
629  {
630  return doDensify( static_cast< const QgsLineString * >( geom ), extraNodesPerSegment, distance );
631  }
632  else
633  {
634  // polygon
635  const QgsPolygon *polygon = static_cast< const QgsPolygon * >( geom );
636  QgsPolygon *result = new QgsPolygon();
637 
638  result->setExteriorRing( doDensify( static_cast< const QgsLineString * >( polygon->exteriorRing() ),
639  extraNodesPerSegment, distance ) );
640  for ( int i = 0; i < polygon->numInteriorRings(); ++i )
641  {
642  result->addInteriorRing( doDensify( static_cast< const QgsLineString * >( polygon->interiorRing( i ) ),
643  extraNodesPerSegment, distance ) );
644  }
645 
646  return result;
647  }
648 }
649 
651 {
652  if ( !mGeometry )
653  {
654  return QgsGeometry();
655  }
656 
657  if ( QgsWkbTypes::geometryType( mGeometry->wkbType() ) == QgsWkbTypes::PointGeometry )
658  {
659  return QgsGeometry( mGeometry->clone() ); // point geometry, nothing to do
660  }
661 
662  if ( const QgsGeometryCollection *gc = qgsgeometry_cast< const QgsGeometryCollection *>( mGeometry ) )
663  {
664  int numGeom = gc->numGeometries();
665  QVector< QgsAbstractGeometry * > geometryList;
666  geometryList.reserve( numGeom );
667  for ( int i = 0; i < numGeom; ++i )
668  {
669  geometryList << densifyGeometry( gc->geometryN( i ), extraNodesPerSegment );
670  }
671 
672  QgsGeometry first = QgsGeometry( geometryList.takeAt( 0 ) );
673  for ( QgsAbstractGeometry *g : qgis::as_const( geometryList ) )
674  {
675  first.addPart( g );
676  }
677  return first;
678  }
679  else
680  {
681  return QgsGeometry( densifyGeometry( mGeometry, extraNodesPerSegment ) );
682  }
683 }
684 
686 {
687  if ( !mGeometry )
688  {
689  return QgsGeometry();
690  }
691 
692  if ( QgsWkbTypes::geometryType( mGeometry->wkbType() ) == QgsWkbTypes::PointGeometry )
693  {
694  return QgsGeometry( mGeometry->clone() ); // point geometry, nothing to do
695  }
696 
697  if ( const QgsGeometryCollection *gc = qgsgeometry_cast< const QgsGeometryCollection *>( mGeometry ) )
698  {
699  int numGeom = gc->numGeometries();
700  QVector< QgsAbstractGeometry * > geometryList;
701  geometryList.reserve( numGeom );
702  for ( int i = 0; i < numGeom; ++i )
703  {
704  geometryList << densifyGeometry( gc->geometryN( i ), -1, distance );
705  }
706 
707  QgsGeometry first = QgsGeometry( geometryList.takeAt( 0 ) );
708  for ( QgsAbstractGeometry *g : qgis::as_const( geometryList ) )
709  {
710  first.addPart( g );
711  }
712  return first;
713  }
714  else
715  {
716  return QgsGeometry( densifyGeometry( mGeometry, -1, distance ) );
717  }
718 }
719 
721 //
722 // QgsLineSegmentDistanceComparer
723 //
724 
725 // adapted for QGIS geometry classes from original work at https://github.com/trylock/visibility by trylock
726 bool QgsLineSegmentDistanceComparer::operator()( QgsLineSegment2D ab, QgsLineSegment2D cd ) const
727 {
728  Q_ASSERT_X( ab.pointLeftOfLine( mOrigin ) != 0,
729  "line_segment_dist_comparer",
730  "AB must not be collinear with the origin." );
731  Q_ASSERT_X( cd.pointLeftOfLine( mOrigin ) != 0,
732  "line_segment_dist_comparer",
733  "CD must not be collinear with the origin." );
734 
735  // flip the segments so that if there are common endpoints,
736  // they will be the segment's start points
737  if ( ab.end() == cd.start() || ab.end() == cd.end() )
738  ab.reverse();
739  if ( ab.start() == cd.end() )
740  cd.reverse();
741 
742  // cases with common endpoints
743  if ( ab.start() == cd.start() )
744  {
745  const int oad = QgsGeometryUtils::leftOfLine( cd.endX(), cd.endY(), mOrigin.x(), mOrigin.y(), ab.startX(), ab.startY() );
746  const int oab = ab.pointLeftOfLine( mOrigin );
747  if ( ab.end() == cd.end() || oad != oab )
748  return false;
749  else
750  return ab.pointLeftOfLine( cd.end() ) != oab;
751  }
752  else
753  {
754  // cases without common endpoints
755  const int cda = cd.pointLeftOfLine( ab.start() );
756  const int cdb = cd.pointLeftOfLine( ab.end() );
757  if ( cdb == 0 && cda == 0 )
758  {
759  return mOrigin.sqrDist( ab.start() ) < mOrigin.sqrDist( cd.start() );
760  }
761  else if ( cda == cdb || cda == 0 || cdb == 0 )
762  {
763  const int cdo = cd.pointLeftOfLine( mOrigin );
764  return cdo == cda || cdo == cdb;
765  }
766  else
767  {
768  const int abo = ab.pointLeftOfLine( mOrigin );
769  return abo != ab.pointLeftOfLine( cd.start() );
770  }
771  }
772 }
773 
774 //
775 // QgsClockwiseAngleComparer
776 //
777 
778 bool QgsClockwiseAngleComparer::operator()( const QgsPointXY &a, const QgsPointXY &b ) const
779 {
780  const bool aIsLeft = a.x() < mVertex.x();
781  const bool bIsLeft = b.x() < mVertex.x();
782  if ( aIsLeft != bIsLeft )
783  return bIsLeft;
784 
785  if ( qgsDoubleNear( a.x(), mVertex.x() ) && qgsDoubleNear( b.x(), mVertex.x() ) )
786  {
787  if ( a.y() >= mVertex.y() || b.y() >= mVertex.y() )
788  {
789  return b.y() < a.y();
790  }
791  else
792  {
793  return a.y() < b.y();
794  }
795  }
796  else
797  {
798  const QgsVector oa = a - mVertex;
799  const QgsVector ob = b - mVertex;
800  const double det = oa.crossProduct( ob );
801  if ( qgsDoubleNear( det, 0.0 ) )
802  {
803  return oa.lengthSquared() < ob.lengthSquared();
804  }
805  else
806  {
807  return det < 0;
808  }
809  }
810 }
811 
813 
814 //
815 // QgsRay2D
816 //
817 
818 bool QgsRay2D::intersects( const QgsLineSegment2D &segment, QgsPointXY &intersectPoint ) const
819 {
820  const QgsVector ao = origin - segment.start();
821  const QgsVector ab = segment.end() - segment.start();
822  const double det = ab.crossProduct( direction );
823  if ( qgsDoubleNear( det, 0.0 ) )
824  {
825  const int abo = segment.pointLeftOfLine( origin );
826  if ( abo != 0 )
827  {
828  return false;
829  }
830  else
831  {
832  const double distA = ao * direction;
833  const double distB = ( origin - segment.end() ) * direction;
834 
835  if ( distA > 0 && distB > 0 )
836  {
837  return false;
838  }
839  else
840  {
841  if ( ( distA > 0 ) != ( distB > 0 ) )
842  intersectPoint = origin;
843  else if ( distA > distB ) // at this point, both distances are negative
844  intersectPoint = segment.start(); // hence the nearest point is A
845  else
846  intersectPoint = segment.end();
847  return true;
848  }
849  }
850  }
851  else
852  {
853  const double u = ao.crossProduct( direction ) / det;
854  if ( u < 0.0 || 1.0 < u )
855  {
856  return false;
857  }
858  else
859  {
860  const double t = -ab.crossProduct( ao ) / det;
861  intersectPoint = origin + direction * t;
862  return qgsDoubleNear( t, 0.0 ) || t > 0;
863  }
864  }
865 }
866 
867 QVector<QgsPointXY> generateSegmentCurve( const QgsPoint &center1, const double radius1, const QgsPoint &center2, const double radius2 )
868 {
869  // ensure that first circle is smaller than second
870  if ( radius1 > radius2 )
871  return generateSegmentCurve( center2, radius2, center1, radius1 );
872 
873  QgsPointXY t1;
874  QgsPointXY t2;
875  QgsPointXY t3;
876  QgsPointXY t4;
877  QVector<QgsPointXY> points;
878  if ( QgsGeometryUtils::circleCircleOuterTangents( center1, radius1, center2, radius2, t1, t2, t3, t4 ) )
879  {
880  points << t1
881  << t2
882  << t4
883  << t3;
884  }
885  return points;
886 }
887 
888 // partially ported from JTS VariableWidthBuffer,
889 // https://github.com/topobyte/jts/blob/master/jts-lab/src/main/java/com/vividsolutions/jts/operation/buffer/VariableWidthBuffer.java
890 
891 QgsGeometry QgsInternalGeometryEngine::variableWidthBuffer( int segments, const std::function< std::unique_ptr< double[] >( const QgsLineString *line ) > &widthFunction ) const
892 {
893  if ( !mGeometry )
894  {
895  return QgsGeometry();
896  }
897 
898  std::vector< std::unique_ptr<QgsLineString > > linesToProcess;
899 
900  const QgsMultiCurve *multiCurve = qgsgeometry_cast< const QgsMultiCurve * >( mGeometry );
901  if ( multiCurve )
902  {
903  for ( int i = 0; i < multiCurve->partCount(); ++i )
904  {
905  if ( static_cast< const QgsCurve * >( multiCurve->geometryN( i ) )->nCoordinates() == 0 )
906  continue; // skip 0 length lines
907 
908  linesToProcess.emplace_back( static_cast<QgsLineString *>( multiCurve->geometryN( i )->clone() ) );
909  }
910  }
911 
912  const QgsCurve *curve = qgsgeometry_cast< const QgsCurve * >( mGeometry );
913  if ( curve )
914  {
915  if ( curve->nCoordinates() > 0 )
916  linesToProcess.emplace_back( static_cast<QgsLineString *>( curve->segmentize() ) );
917  }
918 
919  if ( linesToProcess.empty() )
920  {
921  QgsGeometry g;
922  g.mLastError = QStringLiteral( "Input geometry was not a curve type geometry" );
923  return g;
924  }
925 
926  QVector<QgsGeometry> bufferedLines;
927  bufferedLines.reserve( linesToProcess.size() );
928 
929  for ( std::unique_ptr< QgsLineString > &line : linesToProcess )
930  {
931  QVector<QgsGeometry> parts;
932  QgsPoint prevPoint;
933  double prevRadius = 0;
934  QgsGeometry prevCircle;
935 
936  std::unique_ptr< double[] > widths = widthFunction( line.get() ) ;
937  for ( int i = 0; i < line->nCoordinates(); ++i )
938  {
939  QgsPoint thisPoint = line->pointN( i );
940  QgsGeometry thisCircle;
941  double thisRadius = widths[ i ] / 2.0;
942  if ( thisRadius > 0 )
943  {
944  QgsGeometry p = QgsGeometry( thisPoint.clone() );
945 
946  QgsCircle circ( thisPoint, thisRadius );
947  thisCircle = QgsGeometry( circ.toPolygon( segments * 4 ) );
948  parts << thisCircle;
949  }
950  else
951  {
952  thisCircle = QgsGeometry( thisPoint.clone() );
953  }
954 
955  if ( i > 0 )
956  {
957  if ( prevRadius > 0 || thisRadius > 0 )
958  {
959  QVector< QgsPointXY > points = generateSegmentCurve( prevPoint, prevRadius, thisPoint, thisRadius );
960  if ( !points.empty() )
961  {
962  // snap points to circle vertices
963 
964  int atVertex = 0;
965  int beforeVertex = 0;
966  int afterVertex = 0;
967  double sqrDist = 0;
968  double sqrDistPrev = 0;
969  for ( int j = 0; j < points.count(); ++j )
970  {
971  QgsPointXY pA = prevCircle.closestVertex( points.at( j ), atVertex, beforeVertex, afterVertex, sqrDistPrev );
972  QgsPointXY pB = thisCircle.closestVertex( points.at( j ), atVertex, beforeVertex, afterVertex, sqrDist );
973  points[j] = sqrDistPrev < sqrDist ? pA : pB;
974  }
975  // close ring
976  points.append( points.at( 0 ) );
977 
978  std::unique_ptr< QgsPolygon > poly = qgis::make_unique< QgsPolygon >();
979  poly->setExteriorRing( new QgsLineString( points ) );
980  if ( poly->area() > 0 )
981  parts << QgsGeometry( std::move( poly ) );
982  }
983  }
984  }
985  prevPoint = thisPoint;
986  prevRadius = thisRadius;
987  prevCircle = thisCircle;
988  }
989 
990  bufferedLines << QgsGeometry::unaryUnion( parts );
991  }
992 
993  return QgsGeometry::collectGeometry( bufferedLines );
994 }
995 
996 QgsGeometry QgsInternalGeometryEngine::taperedBuffer( double start, double end, int segments ) const
997 {
998  start = std::fabs( start );
999  end = std::fabs( end );
1000 
1001  auto interpolateWidths = [ start, end ]( const QgsLineString * line )->std::unique_ptr< double [] >
1002  {
1003  // ported from JTS VariableWidthBuffer,
1004  // https://github.com/topobyte/jts/blob/master/jts-lab/src/main/java/com/vividsolutions/jts/operation/buffer/VariableWidthBuffer.java
1005  std::unique_ptr< double [] > widths( new double[ line->nCoordinates() ] );
1006  widths[0] = start;
1007  widths[line->nCoordinates() - 1] = end;
1008 
1009  double lineLength = line->length();
1010  double currentLength = 0;
1011  QgsPoint prevPoint = line->pointN( 0 );
1012  for ( int i = 1; i < line->nCoordinates() - 1; ++i )
1013  {
1014  QgsPoint point = line->pointN( i );
1015  double segmentLength = point.distance( prevPoint );
1016  currentLength += segmentLength;
1017  double lengthFraction = lineLength > 0 ? currentLength / lineLength : 1;
1018  double delta = lengthFraction * ( end - start );
1019  widths[i] = start + delta;
1020  prevPoint = point;
1021  }
1022  return widths;
1023  };
1024 
1025  return variableWidthBuffer( segments, interpolateWidths );
1026 }
1027 
1029 {
1030  auto widthByM = []( const QgsLineString * line )->std::unique_ptr< double [] >
1031  {
1032  std::unique_ptr< double [] > widths( new double[ line->nCoordinates() ] );
1033  for ( int i = 0; i < line->nCoordinates(); ++i )
1034  {
1035  widths[ i ] = line->mAt( i );
1036  }
1037  return widths;
1038  };
1039 
1040  return variableWidthBuffer( segments, widthByM );
1041 }
1042 
1043 QVector<QgsPointXY> QgsInternalGeometryEngine::randomPointsInPolygon( const QgsGeometry &polygon, int count,
1044  const std::function< bool( const QgsPointXY & ) > &acceptPoint, unsigned long seed, QgsFeedback *feedback )
1045 {
1046  if ( polygon.type() != QgsWkbTypes::PolygonGeometry || count == 0 )
1047  return QVector< QgsPointXY >();
1048 
1049  // step 1 - tessellate the polygon to triangles
1050  QgsRectangle bounds = polygon.boundingBox();
1051  QgsTessellator t( bounds, false, false, false, true );
1052 
1053  if ( polygon.isMultipart() )
1054  {
1055  const QgsMultiSurface *ms = qgsgeometry_cast< const QgsMultiSurface * >( polygon.constGet() );
1056  for ( int i = 0; i < ms->numGeometries(); ++i )
1057  {
1058  if ( feedback && feedback->isCanceled() )
1059  return QVector< QgsPointXY >();
1060 
1061  if ( QgsPolygon *poly = qgsgeometry_cast< QgsPolygon * >( ms->geometryN( i ) ) )
1062  {
1063  t.addPolygon( *poly, 0 );
1064  }
1065  else
1066  {
1067  std::unique_ptr< QgsPolygon > p( qgsgeometry_cast< QgsPolygon * >( ms->geometryN( i )->segmentize() ) );
1068  t.addPolygon( *p, 0 );
1069  }
1070  }
1071  }
1072  else
1073  {
1074  if ( const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( polygon.constGet() ) )
1075  {
1076  t.addPolygon( *poly, 0 );
1077  }
1078  else
1079  {
1080  std::unique_ptr< QgsPolygon > p( qgsgeometry_cast< QgsPolygon * >( polygon.constGet()->segmentize() ) );
1081  t.addPolygon( *p, 0 );
1082  }
1083  }
1084 
1085  if ( feedback && feedback->isCanceled() )
1086  return QVector< QgsPointXY >();
1087 
1088  const QVector<float> triangleData = t.data();
1089  if ( triangleData.empty() )
1090  return QVector< QgsPointXY >(); //hm
1091 
1092  // calculate running sum of triangle areas
1093  std::vector< double > cumulativeAreas;
1094  cumulativeAreas.reserve( t.dataVerticesCount() / 3 );
1095  double totalArea = 0;
1096  for ( auto it = triangleData.constBegin(); it != triangleData.constEnd(); )
1097  {
1098  if ( feedback && feedback->isCanceled() )
1099  return QVector< QgsPointXY >();
1100 
1101  const float aX = *it++;
1102  ( void )it++; // z
1103  const float aY = -( *it++ );
1104  const float bX = *it++;
1105  ( void )it++; // z
1106  const float bY = -( *it++ );
1107  const float cX = *it++;
1108  ( void )it++; // z
1109  const float cY = -( *it++ );
1110 
1111  const double area = QgsGeometryUtils::triangleArea( aX, aY, bX, bY, cX, cY );
1112  totalArea += area;
1113  cumulativeAreas.emplace_back( totalArea );
1114  }
1115 
1116  std::random_device rd;
1117  std::mt19937 mt( seed == 0 ? rd() : seed );
1118  std::uniform_real_distribution<> uniformDist( 0, 1 );
1119 
1120  // selects a random triangle, weighted by triangle area
1121  auto selectRandomTriangle = [&cumulativeAreas, totalArea]( double random )->int
1122  {
1123  int triangle = 0;
1124  const double target = random * totalArea;
1125  for ( auto it = cumulativeAreas.begin(); it != cumulativeAreas.end(); ++it, triangle++ )
1126  {
1127  if ( *it > target )
1128  return triangle;
1129  }
1130  Q_ASSERT_X( false, "QgsInternalGeometryEngine::randomPointsInPolygon", "Invalid random triangle index" );
1131  return 0; // no warnings
1132  };
1133 
1134 
1135  QVector<QgsPointXY> result;
1136  result.reserve( count );
1137  for ( int i = 0; i < count; )
1138  {
1139  if ( feedback && feedback->isCanceled() )
1140  return QVector< QgsPointXY >();
1141 
1142  const double triangleIndexRnd = uniformDist( mt );
1143  // pick random triangle, weighted by triangle area
1144  const int triangleIndex = selectRandomTriangle( triangleIndexRnd );
1145 
1146  // generate a random point inside this triangle
1147  const double weightB = uniformDist( mt );
1148  const double weightC = uniformDist( mt );
1149  double x;
1150  double y;
1151 
1152  // get triangle
1153  const double aX = triangleData.at( triangleIndex * 9 ) + bounds.xMinimum();
1154  const double aY = -triangleData.at( triangleIndex * 9 + 2 ) + bounds.yMinimum();
1155  const double bX = triangleData.at( triangleIndex * 9 + 3 ) + bounds.xMinimum();
1156  const double bY = -triangleData.at( triangleIndex * 9 + 5 ) + bounds.yMinimum();
1157  const double cX = triangleData.at( triangleIndex * 9 + 6 ) + bounds.xMinimum();
1158  const double cY = -triangleData.at( triangleIndex * 9 + 8 ) + bounds.yMinimum();
1159  QgsGeometryUtils::weightedPointInTriangle( aX, aY, bX, bY, cX, cY, weightB, weightC, x, y );
1160 
1161  QgsPointXY candidate( x, y );
1162  if ( acceptPoint( candidate ) )
1163  {
1164  result << QgsPointXY( x, y );
1165  i++;
1166  }
1167  }
1168  return result;
1169 }
bool isMeasure() const
Returns true if the geometry contains m values.
QgsGeometry taperedBuffer(double startWidth, double endWidth, int segments) const
Calculates a tapered width buffer for a (multi)curve geometry.
QVector< float > data() const
Returns array of triangle vertex data.
QgsAbstractGeometry * orthogonalizeGeom(const QgsAbstractGeometry *geom, int maxIterations, double tolerance, double lowerThreshold, double upperThreshold)
Circle geometry type.
Definition: qgscircle.h:43
QgsLineString * doDensify(const QgsLineString *ring, int extraNodesPerSegment=-1, double distance=1)
int precision
QgsVector calcMotion(const QgsPoint &a, const QgsPoint &b, const QgsPoint &c, double lowerThreshold, double upperThreshold)
A rectangle specified with double values.
Definition: qgsrectangle.h:41
QgsInternalGeometryEngine(const QgsGeometry &geometry)
The caller is responsible that the geometry is available and unchanged for the whole lifetime of this...
bool isMultipart() const
Returns true if WKB of the geometry is of WKBMulti* type.
QgsGeometry variableWidthBufferByM(int segments) const
Calculates a variable width buffer using the m-values from a (multi)line geometry.
double zAt(int index) const
Returns the z-coordinate of the specified node in the line string.
OperationResult addPart(const QVector< QgsPointXY > &points, QgsWkbTypes::GeometryType geomType=QgsWkbTypes::UnknownGeometry)
Adds a new part to a the geometry.
QgsGeometry variableWidthBuffer(int segments, const std::function< std::unique_ptr< double[] >(const QgsLineString *line) > &widthFunction) const
Calculates a variable width buffer for a (multi)curve geometry.
double normalizedDotProduct(const QgsPoint &a, const QgsPoint &b, const QgsPoint &c)
QVector< QgsPointXY > generateSegmentCurve(const QgsPoint &center1, const double radius1, const QgsPoint &center2, const double radius2)
QgsGeometry poleOfInaccessibility(double precision, double *distanceFromBoundary=nullptr) const
Calculates the approximate pole of inaccessibility for a surface, which is the most distant internal ...
double distance(double x, double y) const
Returns the Cartesian 2D distance between this point and a specified x, y coordinate.
Definition: qgspoint.h:325
double y
Definition: qgspointxy.h:48
A class to represent a 2D point.
Definition: qgspointxy.h:43
double endY() const
Returns the segment&#39;s end y-coordinate.
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:280
const QgsCurve * interiorRing(int i) const
Retrieves an interior ring from the curve polygon.
bool intersects(const QgsLineSegment2D &segment, QgsPointXY &intersectPoint) const
Finds the closest intersection point of the ray and a line segment.
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:122
double crossProduct(QgsVector v) const
Returns the 2D cross product of this vector and another vector v.
Definition: qgsvector.cpp:102
void setYAt(int index, double y)
Sets the y-coordinate of the specified node in the line string.
double squareness(QgsLineString *ring, double lowerThreshold, double upperThreshold)
int dataVerticesCount() const
Returns the number of vertices stored in the output data array.
double pointDistanceToBoundary(double x, double y) const
Returns the distance from a point to the boundary of the polygon (either the exterior ring or any clo...
Definition: qgspolygon.cpp:237
virtual QgsAbstractGeometry * clone() const =0
Clones the geometry by performing a deep copy.
static int circleCircleOuterTangents(const QgsPointXY &center1, double radius1, const QgsPointXY &center2, double radius2, QgsPointXY &line1P1, QgsPointXY &line1P2, QgsPointXY &line2P1, QgsPointXY &line2P2)
Calculates the outer tangent points for two circles, centered at center1 and center2 and with radii o...
Multi surface geometry collection.
void setXAt(int index, double x)
Sets the x-coordinate of the specified node in the line string.
void reverse()
Reverses the line segment, so that the start and end points are flipped.
int numPoints() const override
Returns the number of points in the curve.
QgsPointXY closestVertex(const QgsPointXY &point, int &atVertex, int &beforeVertex, int &afterVertex, double &sqrDist) const
Returns the vertex closest to the given point, the corresponding vertex index, squared distance snap ...
Base class for feedback objects to be used for cancellation of something running in a worker thread...
Definition: qgsfeedback.h:44
As part of the API refactoring and improvements which landed in the Processing API was substantially reworked from the x version This was done in order to allow much of the underlying Processing framework to be ported into c
QgsPointXY end() const
Returns the segment&#39;s end point.
Class that takes care of tessellation of polygons into triangles.
void addInteriorRing(QgsCurve *ring) override
Adds an interior ring to the geometry (takes ownership)
Definition: qgspolygon.cpp:148
int numInteriorRings() const
Returns the number of interior rings contained with the curve polygon.
static double triangleArea(double aX, double aY, double bX, double bY, double cX, double cY)
Returns the area of the triangle denoted by the points (aX, aY), (bX, bY) and (cX, cY).
double startX() const
Returns the segment&#39;s start x-coordinate.
static int leftOfLine(const double x, const double y, const double x1, const double y1, const double x2, const double y2)
Returns a value < 0 if the point (x, y) is left of the line from (x1, y1) -> ( x2, y2).
void addPolygon(const QgsPolygon &polygon, float extrusionHeight)
Tessellates a triangle and adds its vertex entries to the output data array.
Geometry collection.
double width() const
Returns the width of the rectangle.
Definition: qgsrectangle.h:202
double mAt(int index) const
Returns the m value of the specified node in the line string.
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
Definition: qgsgeos.h:79
double yAt(int index) const override
Returns the y-coordinate of the specified node in the line string.
static GeometryType geometryType(Type type)
Returns the geometry type for a WKB type, e.g., both MultiPolygon and CurvePolygon would have a Polyg...
Definition: qgswkbtypes.h:812
T qgsgeometry_cast(const QgsAbstractGeometry *geom)
static QVector< QgsPointXY > randomPointsInPolygon(const QgsGeometry &polygon, int count, const std::function< bool(const QgsPointXY &) > &acceptPoint, unsigned long seed=0, QgsFeedback *feedback=nullptr)
Returns a list of count random points generated inside a polygon geometry.
Multi curve geometry collection.
Definition: qgsmulticurve.h:29
QgsRectangle boundingBox() const override
Returns the minimal bounding box for the geometry.
Definition: qgssurface.h:42
int pointLeftOfLine(const QgsPointXY &point) const
Tests if a point is to the left of the line segment.
QgsPoint * clone() const override
Clones the geometry by performing a deep copy.
Definition: qgspoint.cpp:97
QgsGeometry densifyByDistance(double distance) const
Densifies the geometry by adding regularly placed extra nodes inside each segment so that the maximum...
Abstract base class for curved geometry type.
Definition: qgscurve.h:35
Abstract base class for all geometries.
QgsWkbTypes::Type wkbType() const
Returns the WKB type of the geometry.
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:37
double length() const
Returns the length of the vector.
Definition: qgsvector.cpp:71
QgsAbstractGeometry * densifyGeometry(const QgsAbstractGeometry *geom, int extraNodesPerSegment=1, double distance=1)
Represents a single 2D line segment, consisting of a 2D start and end vertex only.
double x
Definition: qgspointxy.h:47
QgsLineString * clone() const override
Clones the geometry by performing a deep copy.
A class to represent a vector.
Definition: qgsvector.h:29
int numGeometries() const
Returns the number of geometries within the collection.
virtual bool isClosed() const
Returns true if the curve is closed.
Definition: qgscurve.cpp:40
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:177
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:162
QgsCurve * segmentize(double tolerance=M_PI_2/90, SegmentationToleranceType toleranceType=MaximumAngle) const override
Returns a geometry without curves.
Definition: qgscurve.cpp:148
bool dotProductWithinAngleTolerance(double dotProduct, double lowerThreshold, double upperThreshold)
int partCount() const override
Returns count of parts contained in the geometry.
double endX() const
Returns the segment&#39;s end x-coordinate.
void reserve(int size)
Attempts to allocate memory for at least size geometries.
void setExteriorRing(QgsCurve *ring) override
Sets the exterior ring of the polygon.
Definition: qgspolygon.cpp:179
bool isCanceled() const
Tells whether the operation has been canceled already.
Definition: qgsfeedback.h:54
Multi polygon geometry collection.
QgsCurve * clone() const override=0
Clones the geometry by performing a deep copy.
static bool isCurvedType(Type type)
Returns true if the WKB type is a curved type or can contain curved geometries.
Definition: qgswkbtypes.h:755
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:43
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
const QgsAbstractGeometry * geometryN(int n) const
Returns a const reference to a geometry from within the collection.
QgsPoint pointN(int i) const
Returns the specified point from inside the line string.
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:167
double xAt(int index) const override
Returns the x-coordinate of the specified node in the line string.
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:172
QgsWkbTypes::GeometryType type
Definition: qgsgeometry.h:126
QgsGeometry orthogonalize(double tolerance=1.0E-8, int maxIterations=1000, double angleThreshold=15.0) const
Attempts to orthogonalize a line or polygon geometry by shifting vertices to make the geometries angl...
Polygon geometry type.
Definition: qgspolygon.h:31
const QgsCurve * exteriorRing() const
Returns the curve polygon&#39;s exterior ring.
QgsGeometry densifyByCount(int extraNodesPerSegment) const
Densifies the geometry by adding the specified number of extra nodes within each segment of the geome...
double startY() const
Returns the segment&#39;s start y-coordinate.
int nCoordinates() const override
Returns the number of nodes contained in the geometry.
double lengthSquared() const
Returns the length of the vector.
Definition: qgsvector.h:103
virtual int nCoordinates() const
Returns the number of nodes contained in the geometry.
static void weightedPointInTriangle(double aX, double aY, double bX, double bY, double cX, double cY, double weightB, double weightC, double &pointX, double &pointY)
Returns a weighted point inside the triangle denoted by the points (aX, aY), (bX, bY) and (cX...
virtual QgsAbstractGeometry * segmentize(double tolerance=M_PI/180., SegmentationToleranceType toleranceType=MaximumAngle) const
Returns a version of the geometry without curves.
static QgsGeometry unaryUnion(const QVector< QgsGeometry > &geometries)
Compute the unary union on a list of geometries.
static QgsGeometry collectGeometry(const QVector< QgsGeometry > &geometries)
Creates a new multipart geometry from a list of QgsGeometry objects.
bool is3D() const
Returns true if the geometry is 3D and contains a z-value.
QgsGeometry extrude(double x, double y) const
Will extrude a line or (segmentized) curve by a given offset and return a polygon representation of i...
QgsPointXY start() const
Returns the segment&#39;s start point.
QgsVector normalized() const
Returns the vector&#39;s normalized (or "unit") vector (ie same angle but length of 1.0).
Definition: qgsvector.cpp:114
double height() const
Returns the height of the rectangle.
Definition: qgsrectangle.h:209
QgsLineString * doOrthogonalize(QgsLineString *ring, int iterations, double tolerance, double lowerThreshold, double upperThreshold)