39 void heapsort(
int *sid,
int *
id,
const double *
const x,
int N )
41 unsigned int n = N, i = n / 2, parent, child;
61 if ( child + 1 < n && x[
id[sid[child + 1]]] > x[
id[sid[child]]] )
65 if ( x[
id[sid[child]]] > x[
id[tx]] )
67 sid[parent] = sid[child];
69 child = parent * 2 + 1;
83 unsigned int n = N, i = n / 2, parent, child;
107 if ( child + 1 < n && heap[child + 1] > heap[child] )
111 if ( heap[child] > t )
113 heap[parent] = heap[child];
114 x[parent] = x[child];
116 child = parent * 2 + 1;
129 double x3,
double y3,
double x4,
double y4 )
131 return (
cross_product( x1, y1, x2, y2, x3, y3 ) *
cross_product( x1, y1, x2, y2, x4, y4 ) < 0
132 &&
cross_product( x3, y3, x4, y4, x1, y1 ) *
cross_product( x3, y3, x4, y4, x2, y2 ) < 0 );
136 double x3,
double y3,
double x4,
double y4,
137 double *x,
double *y )
140 double a1, a2, b1, b2, c1, c2;
145 c1 = x2 * y1 - x1 * y2;
149 c2 = x4 * y3 - x3 * y4;
151 denom = a1 * b2 - a2 * b1;
158 *x = ( b1 * c2 - b2 * c1 ) / denom;
159 *y = ( a2 * c1 - a1 * c2 ) / denom;
170 for ( i = 0; i < n; i++ )
176 if ( n <= 3 )
return n;
178 int *stack =
new int[n];
179 double *tan =
new double [n];
190 while ( ref < n &&
qgsDoubleNear( y[
id[cHull[ref]]], y[
id[cHull[0]]] ) ) ref++;
195 for ( i = ref; i < n; i++ )
200 tan[i] = ( x[
id[cHull[0]]] - x[
id[cHull[i]]] ) / ( y[
id[cHull[i]]] - y[
id[cHull[0]]] );
204 heapsort2( cHull + ref, tan + ref, n - ref );
214 stack[1] = cHull[ref - 1];
220 for ( i = ref; i < n; i++ )
222 result =
cross_product( x[
id[stack[second]]], y[
id[stack[second]]],
223 x[
id[stack[top]]], y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
227 if (
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[cHull[i]]], y[
id[cHull[i]]] )
228 >
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[stack[top]]], y[
id[stack[top]]] ) )
230 stack[top] = cHull[i];
233 else if ( result > 0 )
237 stack[top] = cHull[i];
241 while ( result < 0 && top > 1 )
246 y[
id[stack[second]]], x[
id[stack[top]]],
247 y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
251 stack[top] = cHull[i];
255 for ( i = 0; i <= top; i++ )
269 int *cHull =
nullptr;
272 int *pts =
new int[nbPoints];
273 for ( i = 0; i < nbPoints; i++ )
278 if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] )
280 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] )
282 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] && pts[cHull[2]] < pts[cHull[0]] )
284 else if ( pts[cHull[0]] > pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] && pts[cHull[2]] > pts[cHull[0]] )
286 else if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] && pts[cHull[2]] > pts[cHull[0]] )
288 else if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] > pts[cHull[2]] && pts[cHull[2]] < pts[cHull[0]] )
302 for ( i = 0, j = nbPoints - 1; i <= j; i++, j-- )
326 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 5, 2 );
328 GEOSCoordSeq_setX_r( geosctxt, coord, 0, x );
329 GEOSCoordSeq_setY_r( geosctxt, coord, 0, y );
332 double beta = alpha + M_PI_2;
333 double dx1 = std::cos( alpha ) * width;
334 double dy1 = std::sin( alpha ) * width;
335 double dx2 = std::cos( beta ) * height;
336 double dy2 = std::sin( beta ) * height;
337 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + dx1 );
338 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y + dy1 );
339 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + dx1 + dx2 );
340 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + dy1 + dy2 );
341 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x + dx2 );
342 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + dy2 );
346 GEOSCoordSeq_setX_r( geosctxt, coord, 1, x + width );
347 GEOSCoordSeq_setY_r( geosctxt, coord, 1, y );
348 GEOSCoordSeq_setX_r( geosctxt, coord, 2, x + width );
349 GEOSCoordSeq_setY_r( geosctxt, coord, 2, y + height );
350 GEOSCoordSeq_setX_r( geosctxt, coord, 3, x );
351 GEOSCoordSeq_setY_r( geosctxt, coord, 3, y + height );
354 GEOSCoordSeq_setX_r( geosctxt, coord, 4, x );
355 GEOSCoordSeq_setY_r( geosctxt, coord, 4, y );
359 geos::unique_ptr bboxGeos( GEOSGeom_createLinearRing_r( geosctxt, coord ) );
360 bool result = ( GEOSPreparedContainsProperly_r( geosctxt, geom, bboxGeos.get() ) == 1 );
363 catch ( GEOSException &e )
373 double x1,
double y1,
double x2,
double y2,
374 double &xRes,
double &yRes )
379 double A = dx * dx + dy * dy;
380 double B = 2 * ( dx * ( x1 - cx ) + dy * ( y1 - cy ) );
381 double C = ( x1 - cx ) * ( x1 - cx ) + ( y1 - cy ) * ( y1 - cy ) - radius * radius;
383 double det = B * B - 4 * A * C;
384 if ( A <= 0.0000001 || det < 0 )
391 double t = -B / ( 2 * A );
400 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.
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)
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.
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))
GEOSContextHandle_t geosContext()
Get GEOS context handle to be used in all GEOS library calls with reentrant API.
#define Q_NOWARN_UNREACHABLE_POP
void heapsort(int *sid, int *id, const double *const x, int N)
void heapsort2(int *x, double *heap, int N)
static int reorderPolygon(int nbPoints, double *x, double *y)
Reorder points to have cross prod ((x,y)[i], (x,y)[i+1), point) > 0 when point is outside...
#define Q_NOWARN_UNREACHABLE_PUSH
static double dist_euc2d_sq(double x1, double y1, double x2, double y2)