49 , mPreparedGeom( nullptr )
68 , mPreparedGeom( nullptr )
91 , mPreparedGeom( nullptr )
114 , mPreparedGeom( nullptr )
121 memcpy(
x, ps.
x,
sizeof(
double )*
nbPoints );
122 memcpy(
y, ps.
y,
sizeof(
double )* nbPoints );
154 bool needClose =
false;
160 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt,
nbPoints + ( needClose ? 1 : 0 ), 2 );
161 for (
int i = 0; i <
nbPoints; ++i )
163 GEOSCoordSeq_setX_r( geosctxt, coord, i,
x[i] );
164 GEOSCoordSeq_setY_r( geosctxt, coord, i,
y[i] );
170 GEOSCoordSeq_setX_r( geosctxt, coord, nbPoints,
x[0] );
171 GEOSCoordSeq_setY_r( geosctxt, coord, nbPoints,
y[0] );
177 mGeos = GEOSGeom_createPolygon_r( geosctxt, GEOSGeom_createLinearRing_r( geosctxt, coord ),
nullptr, 0 );
180 case GEOS_LINESTRING:
181 mGeos = GEOSGeom_createLineString_r( geosctxt, coord );
185 mGeos = GEOSGeom_createPoint_r( geosctxt, coord );
197 if ( !mPreparedGeom )
201 return mPreparedGeom;
208 GEOSGeom_destroy_r( geosctxt,
mGeos );
209 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
212 mPreparedGeom =
nullptr;
221 GEOSGeom_destroy_r( geosctxt,
mGeos );
224 GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
246 newShape->
type = GEOS_POLYGON;
248 newShape->
x =
new double[newShape->
nbPoints];
249 newShape->
y =
new double[newShape->
nbPoints];
252 for ( j = 0, i = imin; i != ( imax + 1 ) %
nbPoints; i = ( i + 1 ) %
nbPoints, j++ )
254 newShape->
x[j] =
x[i];
255 newShape->
y[j] =
y[i];
261 newShape->
x[j] = fptx;
262 newShape->
y[j] = fpty;
273 GEOSCoordSequence* seq = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
274 GEOSCoordSeq_setX_r( geosctxt, seq, 0, x );
275 GEOSCoordSeq_setY_r( geosctxt, seq, 0, y );
276 GEOSGeometry* point = GEOSGeom_createPoint_r( geosctxt, seq );
277 bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), point ) == 1 );
278 GEOSGeom_destroy_r( geosctxt, point );
282 catch ( GEOSException &e )
293 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 5, 2 );
295 GEOSCoordSeq_setX_r( geosctxt, coord, 0, x );
296 GEOSCoordSeq_setY_r( geosctxt, coord, 0, y );
299 double beta = alpha + (
M_PI / 2 );
300 double dx1 = cos( alpha ) * width;
301 double dy1 = sin( alpha ) * width;
302 double dx2 = cos( beta ) * height;
303 double dy2 = sin( beta ) * height;
304 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + dx1 );
305 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y + dy1 );
306 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + dx1 + dx2 );
307 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + dy1 + dy2 );
308 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x + dx2 );
309 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + dy2 );
313 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + width );
314 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y );
315 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + width );
316 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + height );
317 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x );
318 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + height );
321 GEOSCoordSeq_setX_r( geosctxt, coord, 4, x );
322 GEOSCoordSeq_setY_r( geosctxt, coord, 4, y );
326 GEOSGeometry* bboxGeos = GEOSGeom_createLinearRing_r( geosctxt, coord );
327 bool result = ( GEOSPreparedContainsProperly_r( geosctxt,
preparedGeom(), bboxGeos ) == 1 );
328 GEOSGeom_destroy_r( geosctxt, bboxGeos );
331 catch ( GEOSException &e )
340 double xrm,
double yrm )
375 double labelArea = xrm * yrm;
379 while ( !shapes_toProcess.
isEmpty() )
388 for ( i = 0; i < nbp; i++ )
396 cHull = shape->
cHull;
406 ihn = ( ihs + 1 ) % cHullSize;
409 ipn = ( ips + 1 ) % nbp;
410 if ( ipn != cHull[ihn] )
415 for ( i = ips; i != cHull[ihn]; i = ( i + 1 ) % nbp )
418 x[cHull[ihn]], y[cHull[ihn]],
431 x[cHull[ihn]], y[cHull[ihn]] );
439 s = ( base + b + c ) / 2;
440 area = s * ( s - base ) * ( s - b ) * ( s - c );
445 if ( area - bestArea >
EPSILON )
462 bestArea = sqrt( bestArea );
463 double cx, cy, dx, dy, ex, ey, fx, fy, seg_length, ptx = 0, pty = 0, fptx = 0, fpty = 0;
464 int ps = -1, pe = -1, fps = -1, fpe = -1;
465 if ( retainedPt >= 0 && bestArea > labelArea )
472 for ( i = ( cHull[holeE] + 1 ) % nbp; i != ( cHull[holeS] - 1 + nbp ) % nbp; i = j )
480 cx = ( x[i] + x[j] ) / 2.0;
481 cy = ( y[i] + y[j] ) / 2.0;
519 double pointX, pointY;
531 for ( k = cHull[holeS]; k != cHull[holeE]; k = ( k + 1 ) % nbp )
542 if ( isValid && b < c )
553 int imin = retainedPt;
554 int imax = ((( fps < retainedPt && fpe < retainedPt ) || ( fps > retainedPt && fpe > retainedPt ) ) ? qMin( fps, fpe ) : qMax( fps, fpe ) );
556 int nbPtSh1, nbPtSh2;
558 nbPtSh1 = imax - imin + 1 + ( fpe != fps );
560 nbPtSh1 = imax + nbp - imin + 1 + ( fpe != fps );
562 if (( imax == fps ? fpe : fps ) < imin )
563 nbPtSh2 = imin - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
565 nbPtSh2 = imin + nbp - ( imax == fps ? fpe : fps ) + 1 + ( fpe != fps );
567 if ( retainedPt == -1 || fps == -1 || fpe == -1 )
573 else if ( imax == imin || nbPtSh1 <= 2 || nbPtSh2 <= 2 || nbPtSh1 == nbp || nbPtSh2 == nbp )
575 shapes_final.
append( shape );
587 shapes_toProcess.
append( newShape );
594 newShape = shape->
extractShape( nbPtSh2, imax, imin, fps, fpe, fptx, fpty );
601 shapes_toProcess.
append( newShape );
609 shapes_final.
append( shape );
634 double distNearestPoint;
640 double best_area = DBL_MAX;
641 double best_alpha = -1;
643 double best_length = 0;
644 double best_width = 0;
654 if (
x[
cHull[i]] < bbox[0] )
657 if (
x[cHull[i]] > bbox[2] )
658 bbox[2] =
x[cHull[i]];
660 if (
y[cHull[i]] < bbox[1] )
661 bbox[1] =
y[cHull[i]];
663 if (
y[cHull[i]] > bbox[3] )
664 bbox[3] =
y[cHull[i]];
668 dref = bbox[2] - bbox[0];
670 for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
672 alpha = alpha_d *
M_PI / 180.0;
673 d1 = cos( alpha ) * dref;
674 d2 = sin( alpha ) * dref;
695 bb[14] = bb[12] + d2;
696 bb[15] = bb[13] - d1;
699 for ( i = 0; i < 16; i += 4 )
702 alpha_seg = (( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) *
M_PI / 2 + alpha;
714 distNearestPoint = best_cp / dref;
716 d1 = cos( alpha_seg ) * distNearestPoint;
717 d2 = sin( alpha_seg ) * distNearestPoint;
735 if ( best_area - area >
EPSILON )
741 memcpy( best_bb, bb,
sizeof(
double ) *16 );
749 for ( i = 0; i < 16; i = i + 4 )
752 best_bb[( i+4 ) %16], best_bb[( i+5 ) %16], best_bb[( i+6 ) %16], best_bb[( i+7 ) %16],
753 &finalBb->
x[int ( i/4 )], &finalBb->
y[int ( i/4 )] );
756 finalBb->
alpha = best_alpha;
757 finalBb->
width = best_width;
758 finalBb->
length = best_length;
774 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 1, 2 );
775 GEOSCoordSeq_setX_r( geosctxt, coord, 0, px );
776 GEOSCoordSeq_setY_r( geosctxt, coord, 0, py );
777 GEOSGeometry* geosPt = GEOSGeom_createPoint_r( geosctxt, coord );
779 int type = GEOSGeomTypeId_r( geosctxt,
mGeos );
780 const GEOSGeometry* extRing =
nullptr;
781 if ( type != GEOS_POLYGON )
788 extRing = GEOSGetExteriorRing_r( geosctxt,
mGeos );
790 GEOSCoordSequence *nearestCoord = GEOSNearestPoints_r( geosctxt, extRing, geosPt );
793 ( void )GEOSCoordSeq_getX_r( geosctxt, nearestCoord, 0, &nx );
794 ( void )GEOSCoordSeq_getY_r( geosctxt, nearestCoord, 0, &ny );
795 GEOSCoordSeq_destroy_r( geosctxt, nearestCoord );
796 GEOSGeom_destroy_r( geosctxt, geosPt );
805 catch ( GEOSException &e )
823 GEOSGeometry *centroidGeom = GEOSGetCentroid_r( geosctxt,
mGeos );
826 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, centroidGeom );
827 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
828 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
834 GEOSGeometry *pointGeom = GEOSPointOnSurface_r( geosctxt,
mGeos );
838 const GEOSCoordSequence *coordSeq = GEOSGeom_getCoordSeq_r( geosctxt, pointGeom );
839 GEOSCoordSeq_getX_r( geosctxt, coordSeq, 0, &px );
840 GEOSCoordSeq_getY_r( geosctxt, coordSeq, 0, &py );
841 GEOSGeom_destroy_r( geosctxt, pointGeom );
845 GEOSGeom_destroy_r( geosctxt, centroidGeom );
847 catch ( GEOSException &e )
863 while ( i <
nbPoints && ad[i] <= dl ) i++;
873 di = sqrt( dx * dx + dy * dy );
883 *px =
x[i] + dx * distr / di;
884 *py =
y[i] + dy * distr / di;
914 ( void )GEOSLength_r( geosctxt,
mGeos, &len );
917 catch ( GEOSException &e )
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)
const GEOSGeometry * geos() const
Returns the point set's GEOS geometry.
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.
void createGeosGeom() const
struct pal::_cHullBox CHullBox
void getCentroid(double &px, double &py, bool forceInside=false) const
QString tr(const char *sourceText, const char *disambiguation, int n)
bool qgsDoubleNear(double a, double b, double epsilon=4 *DBL_EPSILON)
static double cross_product(double x1, double y1, double x2, double y2, double x3, double y3)
const GEOSPreparedGeometry * preparedGeom() const
void getPointByDistance(double *d, double *ad, double dl, double *px, double *py)
Get a point a set distance along a line geometry.
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 void logMessage(const QString &message, const QString &tag=QString::null, MessageLevel level=WARNING)
add a message to the instance (and create it if necessary)
double length() const
Returns length of line geometry.
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.
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.
bool containsPoint(double x, double y) const
Tests whether point set contains a specified point.
static void splitPolygons(QLinkedList< PointSet * > &shapes_toProcess, QLinkedList< PointSet * > &shapes_final, double xrm, double yrm)
Split a concave shape into several convex shapes.
CHullBox * compute_chull_bbox()
static double dist_euc2d_sq(double x1, double y1, double x2, double y2)
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...
void append(const T &value)