49 : nbPoints( nbPoints )
50 ,
type( GEOS_POLYGON )
52 this->x.resize( nbPoints );
53 this->y.resize( nbPoints );
121 bool needClose =
false;
127 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt,
nbPoints + ( needClose ? 1 : 0 ), 2 );
128 for (
int i = 0; i <
nbPoints; ++i )
130 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 131 GEOSCoordSeq_setXY_r( geosctxt, coord, i,
x[i],
y[i] );
133 GEOSCoordSeq_setX_r( geosctxt, coord, i,
x[i] );
134 GEOSCoordSeq_setY_r( geosctxt, coord, i,
y[i] );
141 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 142 GEOSCoordSeq_setXY_r( geosctxt, coord, nbPoints,
x[0],
y[0] );
144 GEOSCoordSeq_setX_r( geosctxt, coord, nbPoints,
x[0] );
145 GEOSCoordSeq_setY_r( geosctxt, coord, nbPoints,
y[0] );
152 mGeos = GEOSGeom_createPolygon_r( geosctxt, GEOSGeom_createLinearRing_r( geosctxt, coord ),
nullptr, 0 );
155 case GEOS_LINESTRING:
156 mGeos = GEOSGeom_createLineString_r( geosctxt, coord );
160 mGeos = GEOSGeom_createPoint_r( geosctxt, coord );
172 if ( !mPreparedGeom )
176 return mPreparedGeom;
183 GEOSGeom_destroy_r( geosctxt,
mGeos );
184 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
187 mPreparedGeom =
nullptr;
198 GEOSGeom_destroy_r( geosctxt,
mGeos );
201 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
214 std::unique_ptr<PointSet>
PointSet::extractShape(
int nbPtSh,
int imin,
int imax,
int fps,
int fpe,
double fptx,
double fpty )
218 std::unique_ptr<PointSet> newShape = qgis::make_unique< PointSet >();
219 newShape->type = GEOS_POLYGON;
220 newShape->nbPoints = nbPtSh;
221 newShape->x.resize( newShape->nbPoints );
222 newShape->y.resize( newShape->nbPoints );
225 for ( j = 0, i = imin; i != ( imax + 1 ) %
nbPoints; i = ( i + 1 ) %
nbPoints, j++ )
227 newShape->x[j] =
x[i];
228 newShape->y[j] =
y[i];
234 newShape->x[j] = fptx;
235 newShape->y[j] = fpty;
243 return std::unique_ptr< PointSet>(
new PointSet( *
this ) );
251 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 254 GEOSCoordSequence *seq = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
255 GEOSCoordSeq_setX_r( geosctxt, seq, 0, x );
256 GEOSCoordSeq_setY_r( geosctxt, seq, 0, y );
259 bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), point.get() ) == 1 );
263 catch ( GEOSException &e )
277 QLinkedList<PointSet *> &outputShapes,
278 double xrm,
double yrm )
283 std::vector< double >
x;
284 std::vector< double >
y;
288 int *
cHull =
nullptr;
313 double labelArea = xrm * yrm;
317 while ( !inputShapes.isEmpty() )
319 shape = inputShapes.takeFirst();
326 for ( i = 0; i < nbp; i++ )
334 cHull = shape->
cHull;
344 ihn = ( ihs + 1 ) % cHullSize;
347 ipn = ( ips + 1 ) % nbp;
348 if ( ipn != cHull[ihn] )
353 for ( i = ips; i != cHull[ihn]; i = ( i + 1 ) % nbp )
356 x[cHull[ihn]], y[cHull[ihn]],
369 x[cHull[ihn]], y[cHull[ihn]] );
377 s = ( base + b +
c ) / 2;
378 area = s * ( s - base ) * ( s - b ) * ( s -
c );
383 if ( area - bestArea >
EPSILON )
400 bestArea = std::sqrt( bestArea );
401 double cx, cy, dx, dy, ex, ey, fx, fy, seg_length, ptx = 0, pty = 0, fptx = 0, fpty = 0;
402 int ps = -1, pe = -1, fps = -1, fpe = -1;
403 if ( retainedPt >= 0 && bestArea > labelArea )
405 c = std::numeric_limits<double>::max();
410 for ( i = ( cHull[holeE] + 1 ) % nbp; i != ( cHull[holeS] - 1 + nbp ) % nbp; i = j )
418 cx = ( x[i] + x[j] ) / 2.0;
419 cy = ( y[i] + y[j] ) / 2.0;
457 double pointX, pointY;
469 for ( k = cHull[holeS]; k != cHull[holeE]; k = ( k + 1 ) % nbp )
480 if ( isValid && b < c )
491 int imin = retainedPt;
492 int imax = ( ( ( fps < retainedPt && fpe < retainedPt ) || ( fps > retainedPt && fpe > retainedPt ) ) ? std::min( fps, fpe ) : std::max( fps, fpe ) );
494 int nbPtSh1, nbPtSh2;
496 nbPtSh1 = imax - imin + 1 + ( fpe != fps );
498 nbPtSh1 = imax + nbp - imin + 1 + ( fpe != fps );
500 if ( ( imax == fps ? fpe : fps ) < imin )
501 nbPtSh2 = imin - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
503 nbPtSh2 = imin + nbp - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
505 if ( retainedPt == -1 || fps == -1 || fpe == -1 )
511 else if ( imax == imin || nbPtSh1 <= 2 || nbPtSh2 <= 2 || nbPtSh1 == nbp || nbPtSh2 == nbp )
513 outputShapes.append( shape );
518 PointSet *newShape = shape->
extractShape( nbPtSh1, imin, imax, fps, fpe, fptx, fpty ).release();
525 inputShapes.append( newShape );
532 newShape = shape->
extractShape( nbPtSh2, imax, imin, fps, fpe, fptx, fpty ).release();
539 inputShapes.append( newShape );
547 outputShapes.append( shape );
560 if ( startDistance > 0 )
566 double distanceConsumed = 0;
569 for (
int i = 1; i <
nbPoints; ++i )
573 const double thisSegmentLength = std::sqrt( ( thisX - lastX ) * ( thisX - lastX ) + ( thisY - lastY ) * ( thisY - lastY ) );
574 distanceConsumed += thisSegmentLength;
575 if ( distanceConsumed >= smoothDistance )
577 double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
578 x1 = lastX + c * ( thisX - lastX );
579 y1 = lastY + c * ( thisY - lastY );
586 const double distance = std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
587 const double extensionFactor = ( startDistance + distance ) / distance;
594 if ( endDistance > 0 )
602 double distanceConsumed = 0;
605 for (
int i =
nbPoints - 2; i >= 0; --i )
609 const double thisSegmentLength = std::sqrt( ( thisX - lastX ) * ( thisX - lastX ) + ( thisY - lastY ) * ( thisY - lastY ) );
610 distanceConsumed += thisSegmentLength;
611 if ( distanceConsumed >= smoothDistance )
613 double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
614 xend1 = lastX + c * ( thisX - lastX );
615 yend1 = lastY + c * ( thisY - lastY );
622 const double distance = std::sqrt( ( xend1 - xend0 ) * ( xend1 - xend0 ) + ( yend1 - yend0 ) * ( yend1 - yend0 ) );
623 const double extensionFactor = ( endDistance + distance ) / distance;
625 x.emplace_back( newEnd.
x() );
626 y.emplace_back( newEnd.
y() );
630 if ( startDistance > 0 )
632 x.insert(
x.begin(), x0 );
633 y.insert(
y.begin(), y0 );
659 double distNearestPoint;
665 double best_area = std::numeric_limits<double>::max();
666 double best_alpha = -1;
668 double best_length = 0;
669 double best_width = 0;
672 bbox[0] = std::numeric_limits<double>::max();
673 bbox[1] = std::numeric_limits<double>::max();
674 bbox[2] = std::numeric_limits<double>::lowest();
675 bbox[3] = std::numeric_limits<double>::lowest();
679 if (
x[
cHull[i]] < bbox[0] )
682 if (
x[cHull[i]] > bbox[2] )
683 bbox[2] =
x[cHull[i]];
685 if (
y[cHull[i]] < bbox[1] )
686 bbox[1] =
y[cHull[i]];
688 if (
y[cHull[i]] > bbox[3] )
689 bbox[3] =
y[cHull[i]];
693 dref = bbox[2] - bbox[0];
695 for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
697 alpha = alpha_d * M_PI / 180.0;
698 d1 = std::cos( alpha ) * dref;
699 d2 = std::sin( alpha ) * dref;
720 bb[14] = bb[12] + d2;
721 bb[15] = bb[13] - d1;
724 for ( i = 0; i < 16; i += 4 )
727 alpha_seg = ( ( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) * M_PI_2 + alpha;
729 best_cp = std::numeric_limits<double>::max();
739 distNearestPoint = best_cp / dref;
741 d1 = std::cos( alpha_seg ) * distNearestPoint;
742 d2 = std::sin( alpha_seg ) * distNearestPoint;
760 if ( best_area - area >
EPSILON )
766 memcpy( best_bb, bb,
sizeof(
double ) * 16 );
774 for ( i = 0; i < 16; i = i + 4 )
777 best_bb[( i + 4 ) % 16], best_bb[( i + 5 ) % 16], best_bb[( i + 6 ) % 16], best_bb[( i + 7 ) % 16],
778 &finalBb.
x[int ( i / 4 )], &finalBb.
y[int ( i / 4 )] );
781 finalBb.
alpha = best_alpha;
782 finalBb.
width = best_width;
783 finalBb.
length = best_length;
799 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 800 geos::unique_ptr geosPt( GEOSGeom_createPointFromXY_r( geosctxt, px, py ) );
802 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
803 GEOSCoordSeq_setX_r( geosctxt, coord, 0, px );
804 GEOSCoordSeq_setY_r( geosctxt, coord, 0, py );
807 int type = GEOSGeomTypeId_r( geosctxt,
mGeos );
808 const GEOSGeometry *extRing =
nullptr;
809 if ( type != GEOS_POLYGON )
816 extRing = GEOSGetExteriorRing_r( geosctxt,
mGeos );
821 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 822 ( void )GEOSCoordSeq_getXY_r( geosctxt, nearestCoord.get(), 0, &nx, &ny );
824 ( void )GEOSCoordSeq_getX_r( geosctxt, nearestCoord.get(), 0, &nx );
825 ( void )GEOSCoordSeq_getY_r( geosctxt, nearestCoord.get(), 0, &ny );
835 catch ( GEOSException &e )
856 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, centroidGeom.get() );
857 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 858 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
860 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
861 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
872 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
873 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 874 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
876 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
877 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
882 catch ( GEOSException &e )
909 while ( i <
nbPoints && ad[i] <= dl ) i++;
919 di = std::sqrt( dx * dx + dy * dy );
923 dx =
x[i + 1] -
x[i];
924 dy =
y[i + 1] -
y[i];
929 *px =
x[i] + dx * distr / di;
930 *py =
y[i] + dy * distr / di;
965 catch ( GEOSException &e )
987 ( void )GEOSArea_r( geosctxt,
mGeos, &
mArea );
991 catch ( GEOSException &e )
CHullBox compute_chull_bbox()
Computes a con???? hull.
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
static bool computeLineIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double *x, double *y)
Compute the point where two lines intersect.
A class to represent a 2D point.
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
void createGeosGeom() const
static bool isSegIntersects(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
Returns true if the two segments intersect.
bool isClosed() const
Returns true if pointset is closed.
static int convexHullId(int *id, const std::vector< double > &x, const std::vector< double > &y, int n, int *&cHull)
Compute the convex hull in O(n·log(n))
std::unique_ptr< PointSet > extractShape(int nbPtSh, int imin, int imax, int fps, int fpe, double fptx, double fpty)
Does...
static GEOSContextHandle_t getGEOSHandler()
static double cross_product(double x1, double y1, double x2, double y2, double x3, double y3)
bool boundingBoxIntersects(const PointSet *other) const
Returns true if the bounding box of this pointset intersects the bounding box of another pointset...
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
static bool containsCandidate(const GEOSPreparedGeometry *geom, double x, double y, double width, double height, double alpha)
Returns true if a GEOS prepared geometry totally contains a label candidate.
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py)
Gets a point a set distance along a line geometry.
static void splitPolygons(QLinkedList< PointSet *> &inputShapes, QLinkedList< PointSet *> &outputShapes, double xrm, double yrm)
Split a concave shape into several convex shapes.
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
static double dist_euc2d(double x1, double y1, double x2, double y2)
static QgsPointXY interpolatePointOnLine(double x1, double y1, double x2, double y2, double fraction)
Interpolates the position of a point a fraction of the way along the line from (x1, y1) to (x2, y2).
double area() const
Returns area of polygon geometry.
std::unique_ptr< PointSet > clone() const
Returns a copy of the point set.
double length() const
Returns length of line geometry.
void extendLineByDistance(double startDistance, double endDistance, double smoothDistance)
Extends linestrings by the specified amount at the start and end of the line, by extending the existi...
const GEOSPreparedGeometry * preparedGeom() const
std::unique_ptr< GEOSCoordSequence, GeosDeleter > coord_sequence_unique_ptr
Scoped GEOS coordinate sequence pointer.
static double dist_euc2d_sq(double x1, double y1, double x2, double y2)
void getCentroid(double &px, double &py, bool forceInside=false) const
const GEOSGeometry * geos() const
Returns the point set's GEOS geometry.
double minDistanceToPoint(double px, double py, double *rx=nullptr, double *ry=nullptr) const
Returns the squared minimum distance between the point set geometry and the point (px...
bool containsLabelCandidate(double x, double y, double width, double height, double alpha=0) const
Tests whether a possible label candidate will fit completely within the shape.