48 : nbPoints( nbPoints )
49 , type( GEOS_POLYGON )
104 bool needClose =
false;
110 GEOSCoordSequence *coord =
nullptr;
111#if GEOS_VERSION_MAJOR>3 || ( GEOS_VERSION_MAJOR == 3 && GEOS_VERSION_MINOR>=10 )
115 coord = GEOSCoordSeq_copyFromArrays_r( geosctxt,
x.data(),
y.data(),
nullptr,
nullptr,
nbPoints );
124 coord = GEOSCoordSeq_create_r( geosctxt,
nbPoints + ( needClose ? 1 : 0 ), 2 );
125 for (
int i = 0; i <
nbPoints; ++i )
127 GEOSCoordSeq_setXY_r( geosctxt, coord, i,
x[i],
y[i] );
133 GEOSCoordSeq_setXY_r( geosctxt, coord,
nbPoints,
x[0],
y[0] );
140 mGeos = GEOSGeom_createPolygon_r( geosctxt, GEOSGeom_createLinearRing_r( geosctxt, coord ),
nullptr, 0 );
143 case GEOS_LINESTRING:
144 mGeos = GEOSGeom_createLineString_r( geosctxt, coord );
148 mGeos = GEOSGeom_createPoint_r( geosctxt, coord );
160 if ( !mPreparedGeom )
164 return mPreparedGeom;
171 GEOSGeom_destroy_r( geosctxt,
mGeos );
177 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
178 mPreparedGeom =
nullptr;
181 if ( mGeosPreparedBoundary )
183 GEOSPreparedGeom_destroy_r( geosctxt, mGeosPreparedBoundary );
184 mGeosPreparedBoundary =
nullptr;
187 if ( mMultipartPreparedGeos )
189 GEOSPreparedGeom_destroy_r( geosctxt, mMultipartPreparedGeos );
190 mMultipartPreparedGeos =
nullptr;
192 if ( mMultipartGeos )
194 GEOSGeom_destroy_r( geosctxt, mMultipartGeos );
195 mMultipartGeos =
nullptr;
208 GEOSGeom_destroy_r( geosctxt,
mGeos );
211 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
213 if ( mGeosPreparedBoundary )
215 GEOSPreparedGeom_destroy_r( geosctxt, mGeosPreparedBoundary );
216 mGeosPreparedBoundary =
nullptr;
219 if ( mMultipartPreparedGeos )
221 GEOSPreparedGeom_destroy_r( geosctxt, mMultipartPreparedGeos );
222 mMultipartPreparedGeos =
nullptr;
224 if ( mMultipartGeos )
226 GEOSGeom_destroy_r( geosctxt, mMultipartGeos );
227 mMultipartGeos =
nullptr;
239std::unique_ptr<PointSet>
PointSet::extractShape(
int nbPtSh,
int imin,
int imax,
int fps,
int fpe,
double fptx,
double fpty )
243 std::unique_ptr<PointSet> newShape = std::make_unique< PointSet >();
244 newShape->type = GEOS_POLYGON;
245 newShape->nbPoints = nbPtSh;
246 newShape->x.resize( newShape->nbPoints );
247 newShape->y.resize( newShape->nbPoints );
250 for ( j = 0, i = imin; i != ( imax + 1 ) %
nbPoints; i = ( i + 1 ) %
nbPoints, j++ )
252 newShape->x[j] =
x[i];
253 newShape->y[j] =
y[i];
259 newShape->x[j] = fptx;
260 newShape->y[j] = fpty;
268 return std::unique_ptr< PointSet>(
new PointSet( *
this ) );
276 geos::unique_ptr point( GEOSGeom_createPointFromXY_r( geosctxt,
x,
y ) );
277 const bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), point.get() ) == 1 );
281 catch ( GEOSException &e )
283 qWarning(
"GEOS exception: %s", e.what() );
308 const double labelArea = labelWidth * labelHeight;
310 QLinkedList<PointSet *> inputShapes;
311 inputShapes.push_back( inputShape );
312 QLinkedList<PointSet *> outputShapes;
314 while ( !inputShapes.isEmpty() )
316 PointSet *shape = inputShapes.takeFirst();
318 const std::vector< double > &
x = shape->
x;
319 const std::vector< double > &
y = shape->
y;
321 std::vector< int > pts( nbp );
322 for (
int i = 0; i < nbp; i++ )
334 for ( std::size_t ihs = 0; ihs < shape->
convexHull.size(); ihs++ )
337 const std::size_t ihn = ( ihs + 1 ) % shape->
convexHull.size();
340 const int ipn = ( ips + 1 ) % nbp;
346 for (
int i = ips; i != shape->
convexHull[ihn]; i = ( i + 1 ) % nbp )
370 const double s = ( base + b +
c ) / 2;
371 double area = s * ( s - base ) * ( s - b ) * ( s -
c );
393 bestArea = std::sqrt( bestArea );
394 double cx, cy, dx, dy, ex, ey, fx, fy, seg_length, ptx = 0, pty = 0, fptx = 0, fpty = 0;
395 int ps = -1, pe = -1, fps = -1, fpe = -1;
396 if ( retainedPt >= 0 && bestArea > labelArea )
398 double c = std::numeric_limits<double>::max();
403 for (
int i = ( shape->
convexHull[holeE] + 1 ) % nbp; i != ( shape->
convexHull[holeS] - 1 + nbp ) % nbp; i = j )
411 cx = (
x[i] +
x[j] ) / 2.0;
412 cy = (
y[i] +
y[j] ) / 2.0;
450 double pointX, pointY;
473 if ( isValid && b <
c )
484 const int imin = retainedPt;
485 int imax = ( ( ( fps < retainedPt && fpe < retainedPt ) || ( fps > retainedPt && fpe > retainedPt ) ) ? std::min( fps, fpe ) : std::max( fps, fpe ) );
487 int nbPtSh1, nbPtSh2;
489 nbPtSh1 = imax - imin + 1 + ( fpe != fps );
491 nbPtSh1 = imax + nbp - imin + 1 + ( fpe != fps );
493 if ( ( imax == fps ? fpe : fps ) < imin )
494 nbPtSh2 = imin - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
496 nbPtSh2 = imin + nbp - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
498 if ( retainedPt == -1 || fps == -1 || fpe == -1 )
504 else if ( imax == imin || nbPtSh1 <= 2 || nbPtSh2 <= 2 || nbPtSh1 == nbp || nbPtSh2 == nbp )
506 outputShapes.append( shape );
511 PointSet *newShape = shape->
extractShape( nbPtSh1, imin, imax, fps, fpe, fptx, fpty ).release();
518 inputShapes.append( newShape );
525 newShape = shape->
extractShape( nbPtSh2, imax, imin, fps, fpe, fptx, fpty ).release();
532 inputShapes.append( newShape );
540 outputShapes.append( shape );
555 geos::unique_ptr newGeos =
nullptr;
558 newGeos.reset( GEOSOffsetCurve_r( geosctxt,
mGeos, distance, 0, GEOSBUF_JOIN_MITRE, 2 ) );
563 if ( GEOSGeomTypeId_r( geosctxt, newGeos.get() ) == GEOS_MULTILINESTRING )
566 const int nParts = GEOSGetNumGeometries_r( geosctxt, newGeos.get() );
567 double maximumLength = -1;
569 for (
int i = 0; i < nParts; ++i )
571 const GEOSGeometry *part = GEOSGetGeometryN_r( geosctxt, newGeos.get(), i );
572 double partLength = -1;
573 if ( GEOSLength_r( geosctxt, part, &partLength ) == 1 )
575 if ( partLength > maximumLength )
577 maximumLength = partLength;
589 geos::unique_ptr longestPartClone( GEOSGeom_clone_r( geosctxt, longestPart ) );
590 newGeos = std::move( longestPartClone );
593#if GEOS_VERSION_MAJOR==3 && GEOS_VERSION_MINOR<11
597 geos::unique_ptr reversed( GEOSReverse_r( geosctxt, newGeos.get() ) );
601 newGeos = std::move( reversed );
605 const int newNbPoints = GEOSGeomGetNumPoints_r( geosctxt, newGeos.get() );
606 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, newGeos.get() );
607 std::vector< double > newX;
608 std::vector< double > newY;
609 newX.resize( newNbPoints );
610 newY.resize( newNbPoints );
611 for (
int i = 0; i < newNbPoints; i++ )
613 GEOSCoordSeq_getX_r( geosctxt, coordSeq, i, &newX[i] );
614 GEOSCoordSeq_getY_r( geosctxt, coordSeq, i, &newY[i] );
620 catch ( GEOSException &e )
622 qWarning(
"GEOS exception: %s", e.what() );
628 mGeos = newGeos.release();
639 if ( startDistance > 0 )
645 double distanceConsumed = 0;
648 for (
int i = 1; i <
nbPoints; ++i )
650 const double thisX =
x[i];
651 const double thisY =
y[i];
653 distanceConsumed += thisSegmentLength;
654 if ( distanceConsumed >= smoothDistance )
656 const double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
657 x1 = lastX +
c * ( thisX - lastX );
658 y1 = lastY +
c * ( thisY - lastY );
666 const double extensionFactor = ( startDistance + distance ) / distance;
673 if ( endDistance > 0 )
681 double distanceConsumed = 0;
684 for (
int i =
nbPoints - 2; i >= 0; --i )
686 const double thisX =
x[i];
687 const double thisY =
y[i];
689 distanceConsumed += thisSegmentLength;
690 if ( distanceConsumed >= smoothDistance )
692 const double c = ( distanceConsumed - smoothDistance ) / thisSegmentLength;
693 xend1 = lastX +
c * ( thisX - lastX );
694 yend1 = lastY +
c * ( thisY - lastY );
702 const double extensionFactor = ( endDistance + distance ) / distance;
704 x.emplace_back( newEnd.
x() );
705 y.emplace_back( newEnd.
y() );
709 if ( startDistance > 0 )
711 x.insert(
x.begin(), x0 );
712 y.insert(
y.begin(), y0 );
733 double best_area = std::numeric_limits<double>::max();
734 double best_alpha = -1;
736 double best_length = 0;
737 double best_width = 0;
740 bbox[0] = std::numeric_limits<double>::max();
741 bbox[1] = std::numeric_limits<double>::max();
742 bbox[2] = std::numeric_limits<double>::lowest();
743 bbox[3] = std::numeric_limits<double>::lowest();
745 for ( std::size_t i = 0; i <
convexHull.size(); i++ )
762 const double dref = bbox[2] - bbox[0];
769 for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
771 alpha = alpha_d * M_PI / 180.0;
772 d1 = std::cos( alpha ) * dref;
773 d2 = std::sin( alpha ) * dref;
794 bb[14] = bb[12] + d2;
795 bb[15] = bb[13] - d1;
798 for (
int i = 0; i < 16; i += 4 )
801 alpha_seg = ( ( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) * M_PI_2 + alpha;
803 double best_cp = std::numeric_limits<double>::max();
805 for ( std::size_t j = 0; j <
convexHull.size(); j++ )
814 const double distNearestPoint = best_cp / dref;
816 d1 = std::cos( alpha_seg ) * distNearestPoint;
817 d2 = std::sin( alpha_seg ) * distNearestPoint;
841 memcpy( best_bb, bb,
sizeof(
double ) * 16 );
846 for (
int i = 0; i < 16; i = i + 4 )
849 best_bb[( i + 4 ) % 16], best_bb[( i + 5 ) % 16], best_bb[( i + 6 ) % 16], best_bb[( i + 7 ) % 16],
850 &finalBb.
x[int ( i / 4 )], &finalBb.
y[int ( i / 4 )] );
853 finalBb.
alpha = best_alpha;
854 finalBb.
width = best_width;
855 finalBb.
length = best_length;
872 geos::unique_ptr geosPt( GEOSGeom_createPointFromXY_r( geosctxt, px, py ) );
873 const int type = GEOSGeomTypeId_r( geosctxt,
mGeos );
875 const GEOSPreparedGeometry *preparedExtRing =
nullptr;
877 if (
type != GEOS_POLYGON )
885 extRing = GEOSGetExteriorRing_r( geosctxt,
mGeos );
886 if ( ! mGeosPreparedBoundary )
888 mGeosPreparedBoundary = GEOSPrepare_r( geosctxt, extRing );
890 preparedExtRing = mGeosPreparedBoundary;
893 const geos::coord_sequence_unique_ptr nearestCoord( GEOSPreparedNearestPoints_r( geosctxt, preparedExtRing, geosPt.get() ) );
896 unsigned int nPoints = 0;
897 GEOSCoordSeq_getSize_r( geosctxt, nearestCoord.get(), &nPoints );
901 ( void )GEOSCoordSeq_getXY_r( geosctxt, nearestCoord.get(), 0, &nx, &ny );
910 catch ( GEOSException &e )
912 qWarning(
"GEOS exception: %s", e.what() );
929 geos::unique_ptr centroidGeom( GEOSGetCentroid_r( geosctxt,
mGeos ) );
932 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, centroidGeom.get() );
933 unsigned int nPoints = 0;
934 GEOSCoordSeq_getSize_r( geosctxt, coordSeq, &nPoints );
937 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
943 geos::unique_ptr pointGeom( GEOSPointOnSurface_r( geosctxt,
mGeos ) );
947 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
948 unsigned int nPoints = 0;
949 GEOSCoordSeq_getSize_r( geosctxt, coordSeq, &nPoints );
953 GEOSCoordSeq_getXY_r( geosctxt, coordSeq, 0, &px, &py );
957 catch ( GEOSException &e )
959 qWarning(
"GEOS exception: %s", e.what() );
985 while ( i <
nbPoints && ad[i] <= dl ) i++;
995 di = std::sqrt( dx * dx + dy * dy );
999 dx =
x[i + 1] -
x[i];
1000 dy =
y[i + 1] -
y[i];
1005 *px =
x[i] + dx * distr / di;
1006 *py =
y[i] + dy * distr / di;
1026 catch ( GEOSException &e )
1028 qWarning(
"GEOS exception: %s", e.what() );
1039 double distance = -1;
1044 catch ( GEOSException &e )
1046 qWarning(
"GEOS exception: %s", e.what() );
1079 catch ( GEOSException &e )
1081 qWarning(
"GEOS exception: %s", e.what() );
1102 ( void )GEOSArea_r( geosctxt,
mGeos, &
mArea );
1106 catch ( GEOSException &e )
1108 qWarning(
"GEOS exception: %s", e.what() );
1128 GEOSWKTWriter *writer = GEOSWKTWriter_create_r( geosctxt );
1130 char *wkt = GEOSWKTWriter_write_r( geosctxt, writer,
mGeos );
1131 const QString res( wkt );
1133 GEOSFree_r( geosctxt, wkt );
1135 GEOSWKTWriter_destroy_r( geosctxt, writer );
1140 catch ( GEOSException &e )
1142 qWarning(
"GEOS exception: %s", e.what() );
1150 std::vector< double > distances(
nbPoints );
1151 double totalDistance = 0;
1152 double oldX = -1.0, oldY = -1.0;
1153 for (
int i = 0; i <
nbPoints; i++ )
1158 distances[i] = std::sqrt( std::pow( oldX -
x[i], 2 ) + std::pow( oldY -
y[i], 2 ) );
1162 totalDistance += distances[i];
1164 return std::make_tuple( std::move( distances ), totalDistance );
static double sqrDistance2D(double x1, double y1, double x2, double y2)
Returns the squared 2D distance between (x1, y1) and (x2, y2).
static double distance2D(double x1, double y1, double x2, double y2)
Returns the 2D distance between (x1, y1) and (x2, 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,...
static GEOSContextHandle_t get()
Returns a thread local instance of a GEOS context, safe for use in the current thread.
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::MessageLevel::Warning, bool notifyUser=true)
Adds a message to the log instance (and creates it if necessary).
A class to represent a 2D point.
static std::vector< int > convexHullId(std::vector< int > &id, const std::vector< double > &x, const std::vector< double > &y)
Compute the convex hull in O(n·log(n))
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.
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.
static double cross_product(double x1, double y1, double x2, double y2, double x3, double y3)
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.
The underlying raw pal geometry class.
geos::unique_ptr interpolatePoint(double distance) const
Returns a GEOS geometry representing the point interpolated on the shape by distance.
std::unique_ptr< PointSet > clone() const
Returns a copy of the point set.
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.
double lineLocatePoint(const GEOSGeometry *point) const
Returns the distance along the geometry closest to the specified GEOS point.
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...
double area() const
Returns area of polygon geometry.
bool isClosed() const
Returns true if pointset is closed.
void createGeosGeom() const
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py) const
Gets a point a set distance along a line geometry.
bool boundingBoxIntersects(const PointSet *other) const
Returns true if the bounding box of this pointset intersects the bounding box of another pointset.
void getCentroid(double &px, double &py, bool forceInside=false) const
OrientedConvexHullBoundingBox computeConvexHullOrientedBoundingBox(bool &ok) const
Computes an oriented bounding box for the shape's convex hull.
void offsetCurveByDistance(double distance)
Offsets linestrings by the specified distance.
std::vector< int > convexHull
const GEOSPreparedGeometry * preparedGeom() const
QString toWkt() const
Returns a WKT representation of the point set.
const GEOSGeometry * geos() const
Returns the point set's GEOS geometry.
void invalidateGeos() const
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,...
std::unique_ptr< PointSet > extractShape(int nbPtSh, int imin, int imax, int fps, int fpe, double fptx, double fpty)
Does... something completely inscrutable.
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
std::tuple< std::vector< double >, double > edgeDistances() const
Returns a vector of edge distances as well as its total length.
static QLinkedList< PointSet * > splitPolygons(PointSet *inputShape, double labelWidth, double labelHeight)
Split a polygon using some random logic into some other polygons.
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
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Represents the minimum area, oriented bounding box surrounding a convex hull.
struct GEOSGeom_t GEOSGeometry