97 memcpy(
y, ps.
y,
sizeof(
double )* nbPoints );
129 bool needClose =
false;
135 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt,
nbPoints + ( needClose ? 1 : 0 ), 2 );
136 for (
int i = 0; i <
nbPoints; ++i )
138 GEOSCoordSeq_setX_r( geosctxt, coord, i,
x[i] );
139 GEOSCoordSeq_setY_r( geosctxt, coord, i,
y[i] );
145 GEOSCoordSeq_setX_r( geosctxt, coord, nbPoints,
x[0] );
146 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;
196 GEOSGeom_destroy_r( geosctxt,
mGeos );
199 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
221 newShape->
type = GEOS_POLYGON;
223 newShape->
x =
new double[newShape->
nbPoints];
224 newShape->
y =
new double[newShape->
nbPoints];
227 for ( j = 0, i = imin; i != ( imax + 1 ) %
nbPoints; i = ( i + 1 ) %
nbPoints, j++ )
229 newShape->
x[j] =
x[i];
230 newShape->
y[j] =
y[i];
236 newShape->
x[j] = fptx;
237 newShape->
y[j] = fpty;
248 GEOSCoordSequence *seq = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
249 GEOSCoordSeq_setX_r( geosctxt, seq, 0, x );
250 GEOSCoordSeq_setY_r( geosctxt, seq, 0, y );
252 bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), point.get() ) == 1 );
256 catch ( GEOSException &e )
270 QLinkedList<PointSet *> &shapes_final,
271 double xrm,
double yrm )
281 int *
cHull =
nullptr;
306 double labelArea = xrm * yrm;
310 while ( !shapes_toProcess.isEmpty() )
312 shape = shapes_toProcess.takeFirst();
319 for ( i = 0; i < nbp; i++ )
327 cHull = shape->
cHull;
337 ihn = ( ihs + 1 ) % cHullSize;
340 ipn = ( ips + 1 ) % nbp;
341 if ( ipn != cHull[ihn] )
346 for ( i = ips; i != cHull[ihn]; i = ( i + 1 ) % nbp )
349 x[cHull[ihn]], y[cHull[ihn]],
362 x[cHull[ihn]], y[cHull[ihn]] );
370 s = ( base + b + c ) / 2;
371 area = s * ( s - base ) * ( s - b ) * ( s - c );
376 if ( area - bestArea >
EPSILON )
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 )
403 for ( i = ( cHull[holeE] + 1 ) % nbp; i != ( cHull[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;
462 for ( k = cHull[holeS]; k != cHull[holeE]; k = ( k + 1 ) % nbp )
473 if ( isValid && b < c )
484 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 shapes_final.append( shape );
518 shapes_toProcess.append( newShape );
525 newShape = shape->
extractShape( nbPtSh2, imax, imin, fps, fpe, fptx, fpty );
532 shapes_toProcess.append( newShape );
540 shapes_final.append( shape );
565 double distNearestPoint;
571 double best_area = DBL_MAX;
572 double best_alpha = -1;
574 double best_length = 0;
575 double best_width = 0;
585 if (
x[
cHull[i]] < bbox[0] )
588 if (
x[cHull[i]] > bbox[2] )
589 bbox[2] =
x[cHull[i]];
591 if (
y[cHull[i]] < bbox[1] )
592 bbox[1] =
y[cHull[i]];
594 if (
y[cHull[i]] > bbox[3] )
595 bbox[3] =
y[cHull[i]];
599 dref = bbox[2] - bbox[0];
601 for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
603 alpha = alpha_d * M_PI / 180.0;
604 d1 = std::cos( alpha ) * dref;
605 d2 = std::sin( alpha ) * dref;
626 bb[14] = bb[12] + d2;
627 bb[15] = bb[13] - d1;
630 for ( i = 0; i < 16; i += 4 )
633 alpha_seg = ( ( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) * M_PI_2 + alpha;
645 distNearestPoint = best_cp / dref;
647 d1 = std::cos( alpha_seg ) * distNearestPoint;
648 d2 = std::sin( alpha_seg ) * distNearestPoint;
666 if ( best_area - area >
EPSILON )
672 memcpy( best_bb, bb,
sizeof(
double ) * 16 );
680 for ( i = 0; i < 16; i = i + 4 )
683 best_bb[( i + 4 ) % 16], best_bb[( i + 5 ) % 16], best_bb[( i + 6 ) % 16], best_bb[( i + 7 ) % 16],
684 &finalBb->
x[int ( i / 4 )], &finalBb->
y[int ( i / 4 )] );
687 finalBb->
alpha = best_alpha;
688 finalBb->
width = best_width;
689 finalBb->
length = best_length;
705 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
706 GEOSCoordSeq_setX_r( geosctxt, coord, 0, px );
707 GEOSCoordSeq_setY_r( geosctxt, coord, 0, py );
710 int type = GEOSGeomTypeId_r( geosctxt,
mGeos );
711 const GEOSGeometry *extRing =
nullptr;
712 if ( type != GEOS_POLYGON )
719 extRing = GEOSGetExteriorRing_r( geosctxt,
mGeos );
724 ( void )GEOSCoordSeq_getX_r( geosctxt, nearestCoord.get(), 0, &nx );
725 ( void )GEOSCoordSeq_getY_r( geosctxt, nearestCoord.get(), 0, &ny );
734 catch ( GEOSException &e )
755 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, centroidGeom.get() );
756 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
757 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
767 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom.get() );
768 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
769 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
773 catch ( GEOSException &e )
789 while ( i <
nbPoints && ad[i] <= dl ) i++;
799 di = std::sqrt( dx * dx + dy * dy );
803 dx =
x[i + 1] -
x[i];
804 dy =
y[i + 1] -
y[i];
809 *px =
x[i] + dx * distr / di;
810 *py =
y[i] + dy * distr / di;
840 ( void )GEOSLength_r( geosctxt,
mGeos, &len );
843 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)
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
bool qgsDoubleNear(double a, double b, double epsilon=4 *DBL_EPSILON)
Compare two doubles (but allow some difference)
static void logMessage(const QString &message, const QString &tag=QString(), Qgis::MessageLevel level=Qgis::Warning)
add a message to the instance (and create it if necessary)
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.
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py)
Get a point a set distance along a line geometry.
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
static int convexHullId(int *id, const double *const x, const double *const y, int n, int *&cHull)
Compute the convex hull in O(n·log(n))
static double dist_euc2d(double x1, double y1, double x2, double y2)
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
CHullBox * compute_chull_bbox()
double length() const
Returns length of line geometry.
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.