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 GEOSCoordSeq_setX_r( geosctxt, coord, i,
x[i] );
131 GEOSCoordSeq_setY_r( geosctxt, coord, i,
y[i] );
137 GEOSCoordSeq_setX_r( geosctxt, coord, nbPoints,
x[0] );
138 GEOSCoordSeq_setY_r( geosctxt, coord, nbPoints,
y[0] );
144 mGeos = GEOSGeom_createPolygon_r( geosctxt, GEOSGeom_createLinearRing_r( geosctxt, coord ),
nullptr, 0 );
147 case GEOS_LINESTRING:
148 mGeos = GEOSGeom_createLineString_r( geosctxt, coord );
152 mGeos = GEOSGeom_createPoint_r( geosctxt, coord );
164 if ( !mPreparedGeom )
168 return mPreparedGeom;
175 GEOSGeom_destroy_r( geosctxt,
mGeos );
176 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
179 mPreparedGeom =
nullptr;
188 GEOSGeom_destroy_r( geosctxt,
mGeos );
191 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
210 newShape->
type = GEOS_POLYGON;
212 newShape->
x.resize( newShape->
nbPoints );
213 newShape->
y.resize( newShape->
nbPoints );
216 for ( j = 0, i = imin; i != ( imax + 1 ) %
nbPoints; i = ( i + 1 ) %
nbPoints, j++ )
218 newShape->
x[j] =
x[i];
219 newShape->
y[j] =
y[i];
225 newShape->
x[j] = fptx;
226 newShape->
y[j] = fpty;
234 return std::unique_ptr< PointSet>(
new PointSet( *
this ) );
242 GEOSCoordSequence *seq = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
243 GEOSCoordSeq_setX_r( geosctxt, seq, 0, x );
244 GEOSCoordSeq_setY_r( geosctxt, seq, 0, y );
246 bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), point.get() ) == 1 );
250 catch ( GEOSException &e )
264 QLinkedList<PointSet *> &shapes_final,
265 double xrm,
double yrm )
270 std::vector< double >
x;
271 std::vector< double >
y;
275 int *
cHull =
nullptr;
300 double labelArea = xrm * yrm;
304 while ( !shapes_toProcess.isEmpty() )
306 shape = shapes_toProcess.takeFirst();
313 for ( i = 0; i < nbp; i++ )
321 cHull = shape->
cHull;
331 ihn = ( ihs + 1 ) % cHullSize;
334 ipn = ( ips + 1 ) % nbp;
335 if ( ipn != cHull[ihn] )
340 for ( i = ips; i != cHull[ihn]; i = ( i + 1 ) % nbp )
343 x[cHull[ihn]], y[cHull[ihn]],
356 x[cHull[ihn]], y[cHull[ihn]] );
364 s = ( base + b +
c ) / 2;
365 area = s * ( s - base ) * ( s - b ) * ( s -
c );
370 if ( area - bestArea >
EPSILON )
387 bestArea = std::sqrt( bestArea );
388 double cx, cy, dx, dy, ex, ey, fx, fy, seg_length, ptx = 0, pty = 0, fptx = 0, fpty = 0;
389 int ps = -1, pe = -1, fps = -1, fpe = -1;
390 if ( retainedPt >= 0 && bestArea > labelArea )
392 c = std::numeric_limits<double>::max();
397 for ( i = ( cHull[holeE] + 1 ) % nbp; i != ( cHull[holeS] - 1 + nbp ) % nbp; i = j )
405 cx = ( x[i] + x[j] ) / 2.0;
406 cy = ( y[i] + y[j] ) / 2.0;
444 double pointX, pointY;
456 for ( k = cHull[holeS]; k != cHull[holeE]; k = ( k + 1 ) % nbp )
467 if ( isValid && b < c )
478 int imin = retainedPt;
479 int imax = ( ( ( fps < retainedPt && fpe < retainedPt ) || ( fps > retainedPt && fpe > retainedPt ) ) ? std::min( fps, fpe ) : std::max( fps, fpe ) );
481 int nbPtSh1, nbPtSh2;
483 nbPtSh1 = imax - imin + 1 + ( fpe != fps );
485 nbPtSh1 = imax + nbp - imin + 1 + ( fpe != fps );
487 if ( ( imax == fps ? fpe : fps ) < imin )
488 nbPtSh2 = imin - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
490 nbPtSh2 = imin + nbp - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
492 if ( retainedPt == -1 || fps == -1 || fpe == -1 )
498 else if ( imax == imin || nbPtSh1 <= 2 || nbPtSh2 <= 2 || nbPtSh1 == nbp || nbPtSh2 == nbp )
500 shapes_final.append( shape );
512 shapes_toProcess.append( newShape );
519 newShape = shape->
extractShape( nbPtSh2, imax, imin, fps, fpe, fptx, fpty );
526 shapes_toProcess.append( newShape );
534 shapes_final.append( shape );
547 if ( startDistance > 0 )
553 double distanceConsumed = 0;
556 for (
int i = 1; i <
nbPoints; ++i )
560 const double thisSegmentLength = std::sqrt( ( thisX - lastX ) * ( thisX - lastX ) + ( thisY - lastY ) * ( thisY - lastY ) );
561 distanceConsumed += thisSegmentLength;
562 if ( distanceConsumed >= smoothDistance )
564 double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
565 x1 = lastX + c * ( thisX - lastX );
566 y1 = lastY + c * ( thisY - lastY );
573 const double distance = std::sqrt( ( x1 - x0 ) * ( x1 - x0 ) + ( y1 - y0 ) * ( y1 - y0 ) );
574 const double extensionFactor = ( startDistance + distance ) / distance;
581 if ( endDistance > 0 )
589 double distanceConsumed = 0;
592 for (
int i =
nbPoints - 2; i >= 0; --i )
596 const double thisSegmentLength = std::sqrt( ( thisX - lastX ) * ( thisX - lastX ) + ( thisY - lastY ) * ( thisY - lastY ) );
597 distanceConsumed += thisSegmentLength;
598 if ( distanceConsumed >= smoothDistance )
600 double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
601 xend1 = lastX + c * ( thisX - lastX );
602 yend1 = lastY + c * ( thisY - lastY );
609 const double distance = std::sqrt( ( xend1 - xend0 ) * ( xend1 - xend0 ) + ( yend1 - yend0 ) * ( yend1 - yend0 ) );
610 const double extensionFactor = ( endDistance + distance ) / distance;
612 x.emplace_back( newEnd.
x() );
613 y.emplace_back( newEnd.
y() );
617 if ( startDistance > 0 )
619 x.insert(
x.begin(), x0 );
620 y.insert(
y.begin(), y0 );
646 double distNearestPoint;
652 double best_area = std::numeric_limits<double>::max();
653 double best_alpha = -1;
655 double best_length = 0;
656 double best_width = 0;
659 bbox[0] = std::numeric_limits<double>::max();
660 bbox[1] = std::numeric_limits<double>::max();
661 bbox[2] = std::numeric_limits<double>::lowest();
662 bbox[3] = std::numeric_limits<double>::lowest();
666 if (
x[
cHull[i]] < bbox[0] )
669 if (
x[cHull[i]] > bbox[2] )
670 bbox[2] =
x[cHull[i]];
672 if (
y[cHull[i]] < bbox[1] )
673 bbox[1] =
y[cHull[i]];
675 if (
y[cHull[i]] > bbox[3] )
676 bbox[3] =
y[cHull[i]];
680 dref = bbox[2] - bbox[0];
682 for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
684 alpha = alpha_d * M_PI / 180.0;
685 d1 = std::cos( alpha ) * dref;
686 d2 = std::sin( alpha ) * dref;
707 bb[14] = bb[12] + d2;
708 bb[15] = bb[13] - d1;
711 for ( i = 0; i < 16; i += 4 )
714 alpha_seg = ( ( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) * M_PI_2 + alpha;
716 best_cp = std::numeric_limits<double>::max();
726 distNearestPoint = best_cp / dref;
728 d1 = std::cos( alpha_seg ) * distNearestPoint;
729 d2 = std::sin( alpha_seg ) * distNearestPoint;
747 if ( best_area - area >
EPSILON )
753 memcpy( best_bb, bb,
sizeof(
double ) * 16 );
761 for ( i = 0; i < 16; i = i + 4 )
764 best_bb[( i + 4 ) % 16], best_bb[( i + 5 ) % 16], best_bb[( i + 6 ) % 16], best_bb[( i + 7 ) % 16],
765 &finalBb->
x[int ( i / 4 )], &finalBb->
y[int ( i / 4 )] );
768 finalBb->
alpha = best_alpha;
769 finalBb->
width = best_width;
770 finalBb->
length = best_length;
786 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
787 GEOSCoordSeq_setX_r( geosctxt, coord, 0, px );
788 GEOSCoordSeq_setY_r( geosctxt, coord, 0, py );
791 int type = GEOSGeomTypeId_r( geosctxt,
mGeos );
792 const GEOSGeometry *extRing =
nullptr;
793 if ( type != GEOS_POLYGON )
800 extRing = GEOSGetExteriorRing_r( geosctxt,
mGeos );
805 ( void )GEOSCoordSeq_getX_r( geosctxt, nearestCoord.get(), 0, &nx );
806 ( void )GEOSCoordSeq_getY_r( geosctxt, nearestCoord.get(), 0, &ny );
815 catch ( GEOSException &e )
836 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, centroidGeom.get() );
837 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
838 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
848 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
849 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
850 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
854 catch ( GEOSException &e )
881 while ( i <
nbPoints && ad[i] <= dl ) i++;
891 di = std::sqrt( dx * dx + dy * dy );
895 dx =
x[i + 1] -
x[i];
896 dy =
y[i + 1] -
y[i];
901 *px =
x[i] + dx * distr / di;
902 *py =
y[i] + dy * distr / di;
932 ( void )GEOSLength_r( geosctxt,
mGeos, &len );
935 catch ( GEOSException &e )
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.
PointSet * extractShape(int nbPtSh, int imin, int imax, int fps, int fpe, double fptx, double fpty)
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.
struct pal::_cHullBox CHullBox
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))
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.
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).
CHullBox * compute_chull_bbox()
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
static void splitPolygons(QLinkedList< PointSet *> &shapes_toProcess, QLinkedList< PointSet *> &shapes_final, double xrm, double yrm)
Split a concave shape into several convex shapes.
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.