40 void heapsort(
int *sid,
int *
id,
const std::vector< double > &x,
int N )
42 unsigned int n = N, i = n / 2, parent, child;
62 if ( child + 1 < n && x[
id[sid[child + 1]]] > x[
id[sid[child]]] )
66 if ( x[
id[sid[child]]] > x[
id[tx]] )
68 sid[parent] = sid[child];
70 child = parent * 2 + 1;
84 unsigned int n = N, i = n / 2, parent, child;
108 if ( child + 1 < n && heap[child + 1] > heap[child] )
112 if ( heap[child] > t )
114 heap[parent] = heap[child];
115 x[parent] = x[child];
117 child = parent * 2 + 1;
130 double x3,
double y3,
double x4,
double y4 )
132 return (
cross_product( x1, y1, x2, y2, x3, y3 ) *
cross_product( x1, y1, x2, y2, x4, y4 ) < 0
133 &&
cross_product( x3, y3, x4, y4, x1, y1 ) *
cross_product( x3, y3, x4, y4, x2, y2 ) < 0 );
137 double x3,
double y3,
double x4,
double y4,
138 double *x,
double *y )
141 double a1, a2, b1, b2, c1, c2;
146 c1 = x2 * y1 - x1 * y2;
150 c2 = x4 * y3 - x3 * y4;
152 denom = a1 * b2 - a2 * b1;
159 *x = ( b1 * c2 - b2 * c1 ) / denom;
160 *y = ( a2 * c1 - a1 * c2 ) / denom;
171 for ( i = 0; i < n; i++ )
177 if ( n <= 3 )
return n;
179 int *stack =
new int[n];
180 double *tan =
new double [n];
191 while ( ref < n &&
qgsDoubleNear( y[
id[cHull[ref]]], y[
id[cHull[0]]] ) ) ref++;
196 for ( i = ref; i < n; i++ )
201 tan[i] = ( x[
id[cHull[0]]] - x[
id[cHull[i]]] ) / ( y[
id[cHull[i]]] - y[
id[cHull[0]]] );
205 heapsort2( cHull + ref, tan + ref, n - ref );
215 stack[1] = cHull[ref - 1];
221 for ( i = ref; i < n; i++ )
223 result =
cross_product( x[
id[stack[second]]], y[
id[stack[second]]],
224 x[
id[stack[top]]], y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
228 if (
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[cHull[i]]], y[
id[cHull[i]]] )
229 >
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[stack[top]]], y[
id[stack[top]]] ) )
231 stack[top] = cHull[i];
234 else if ( result > 0 )
238 stack[top] = cHull[i];
242 while ( result < 0 && top > 1 )
247 y[
id[stack[second]]], x[
id[stack[top]]],
248 y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
252 stack[top] = cHull[i];
256 for ( i = 0; i <= top; i++ )
270 int *cHull =
nullptr;
273 int *pts =
new int[nbPoints];
274 for ( i = 0; i < nbPoints; i++ )
279 if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] )
281 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] )
283 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] && pts[cHull[2]] < pts[cHull[0]] )
285 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] && pts[cHull[2]] > pts[cHull[0]] )
287 else if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] && pts[cHull[2]] > pts[cHull[0]] )
289 else if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] && pts[cHull[2]] < pts[cHull[0]] )
303 for ( i = 0, j = nbPoints - 1; i <= j; i++, j-- )
327 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 5, 2 );
329 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 330 GEOSCoordSeq_setXY_r( geosctxt, coord, 0, x, y );
332 GEOSCoordSeq_setX_r( geosctxt, coord, 0, x );
333 GEOSCoordSeq_setY_r( geosctxt, coord, 0, y );
337 double beta = alpha + M_PI_2;
338 double dx1 = std::cos( alpha ) * width;
339 double dy1 = std::sin( alpha ) * width;
340 double dx2 = std::cos( beta ) * height;
341 double dy2 = std::sin( beta ) * height;
342 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 343 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + dx1, y + dy1 );
344 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + dx1 + dx2, y + dy1 + dy2 );
345 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x + dx2, y + dy2 );
347 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + dx1 );
348 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y + dy1 );
349 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + dx1 + dx2 );
350 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + dy1 + dy2 );
351 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x + dx2 );
352 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + dy2 );
357 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 358 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + width, y );
359 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + width, y + height );
360 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x, y + height );
362 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + width );
363 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y );
364 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + width );
365 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + height );
366 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x );
367 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + height );
371 #if GEOS_VERSION_MAJOR>3 || GEOS_VERSION_MINOR>=8 372 GEOSCoordSeq_setXY_r( geosctxt, coord, 4, x, y );
374 GEOSCoordSeq_setX_r( geosctxt, coord, 4, x );
375 GEOSCoordSeq_setY_r( geosctxt, coord, 4, y );
380 geos::unique_ptr bboxGeos( GEOSGeom_createLinearRing_r( geosctxt, coord ) );
381 bool result = ( GEOSPreparedContainsProperly_r( geosctxt, geom, bboxGeos.get() ) == 1 );
384 catch ( GEOSException &e )
394 double x1,
double y1,
double x2,
double y2,
395 double &xRes,
double &yRes )
400 double A = dx * dx + dy * dy;
401 double B = 2 * ( dx * ( x1 - cx ) + dy * ( y1 - cy ) );
402 double C = ( x1 - cx ) * ( x1 - cx ) + ( y1 - cy ) * ( y1 - cy ) - radius * radius;
404 double det = B * B - 4 * A * C;
405 if ( A <= 0.000000000001 || det < 0 )
412 double t = -B / ( 2 * A );
421 double t = ( -B + std::sqrt( det ) ) / ( 2 * A );
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.
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
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 void findLineCircleIntersection(double cx, double cy, double radius, double x1, double y1, double x2, double y2, double &xRes, double &yRes)
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)
void heapsort(int *sid, int *id, const std::vector< double > &x, int N)
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.
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).
#define Q_NOWARN_UNREACHABLE_POP
static int reorderPolygon(int nbPoints, std::vector< double > &x, std::vector< double > &y)
Reorder points to have cross prod ((x,y)[i], (x,y)[i+1), point) > 0 when point is outside...
void heapsort2(int *x, double *heap, int N)
#define Q_NOWARN_UNREACHABLE_PUSH
static double dist_euc2d_sq(double x1, double y1, double x2, double y2)