41void heapsort( std::vector< int > &sid,
int *
id,
const std::vector< double > &x, std::size_t N )
44 std::size_t i = n / 2;
66 if ( child + 1 < n && x[
id[sid[child + 1]]] > x[
id[sid[child]]] )
70 if ( x[
id[sid[child]]] > x[
id[tx]] )
72 sid[parent] = sid[child];
74 child = parent * 2 + 1;
86void heapsort2(
int *x,
double *heap, std::size_t N )
89 std::size_t i = n / 2;
105 if ( n == 0 )
return;
115 if ( child + 1 < n && heap[child + 1] > heap[child] )
119 if ( heap[child] > t )
121 heap[parent] = heap[child];
122 x[parent] = x[child];
124 child = parent * 2 + 1;
137 double x3,
double y3,
double x4,
double y4 )
139 return (
cross_product( x1, y1, x2, y2, x3, y3 ) *
cross_product( x1, y1, x2, y2, x4, y4 ) < 0
140 &&
cross_product( x3, y3, x4, y4, x1, y1 ) *
cross_product( x3, y3, x4, y4, x2, y2 ) < 0 );
144 double x3,
double y3,
double x4,
double y4,
145 double *x,
double *y )
148 double a1, a2, b1, b2, c1, c2;
153 c1 = x2 * y1 - x1 * y2;
157 c2 = x4 * y3 - x3 * y4;
159 denom = a1 * b2 - a2 * b1;
166 *x = ( b1 * c2 - b2 * c1 ) / denom;
167 *y = ( a2 * c1 - a1 * c2 ) / denom;
175 std::vector< int > convexHull( x.size() );
176 for ( std::size_t i = 0; i < x.size(); i++ )
178 convexHull[i] =
static_cast< int >( i );
184 std::vector< int > stack( x.size() );
185 std::vector< double > tan( x.size() );
188 heapsort( convexHull,
id.data(), y, y.size() );
192 while ( ref < x.size() &&
qgsDoubleNear( y[
id[convexHull[ref]]], y[
id[convexHull[0]]] ) )
195 heapsort( convexHull,
id.data(), x, ref );
198 for ( std::size_t i = ref; i < x.size(); i++ )
200 if (
qgsDoubleNear( y[
id[convexHull[i]]], y[
id[convexHull[0]]] ) )
203 tan[i] = ( x[
id[convexHull[0]]] - x[
id[convexHull[i]]] ) / ( y[
id[convexHull[i]]] - y[
id[convexHull[0]]] );
206 if ( ref < x.size() )
207 heapsort2( convexHull.data() + ref, tan.data() + ref, x.size() - ref );
210 stack[0] = convexHull[0];
213 stack[1] = convexHull[1];
217 stack[1] = convexHull[ref - 1];
220 std::size_t second = 0;
222 for ( std::size_t i = ref; i < x.size(); i++ )
224 double result =
cross_product( x[
id[stack[second]]], y[
id[stack[second]]],
225 x[
id[stack[top]]], y[
id[stack[top]]], x[
id[convexHull[i]]], y[
id[convexHull[i]]] );
232 stack[top] = convexHull[i];
235 else if ( result > 0 )
239 stack[top] = convexHull[i];
243 while ( result < 0 && top > 1 )
248 y[
id[stack[second]]], x[
id[stack[top]]],
249 y[
id[stack[top]]], x[
id[convexHull[i]]], y[
id[convexHull[i]]] );
253 stack[top] = convexHull[i];
257 for ( std::size_t i = 0; i <= top; i++ )
259 convexHull[i] = stack[i];
262 convexHull.resize( top + 1 );
268 std::vector< int > pts( x.size() );
269 for ( std::size_t i = 0; i < x.size(); i++ )
270 pts[i] =
static_cast< int >( i );
272 std::vector< int > convexHull =
convexHullId( pts, x, y );
275 if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] )
277 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] )
279 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] && pts[convexHull[2]] < pts[convexHull[0]] )
281 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] && pts[convexHull[2]] > pts[convexHull[0]] )
283 else if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] && pts[convexHull[2]] > pts[convexHull[0]] )
285 else if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] && pts[convexHull[2]] < pts[convexHull[0]] )
295 for ( std::size_t i = 0, j = x.size() - 1; i <= j; i++, j-- )
297 std::swap( x[i], x[j] );
298 std::swap( y[i], y[j] );
312 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 5, 2 );
314 GEOSCoordSeq_setXY_r( geosctxt, coord, 0, x, y );
317 const double beta = alpha + M_PI_2;
318 const double dx1 = std::cos( alpha ) * width;
319 const double dy1 = std::sin( alpha ) * width;
320 const double dx2 = std::cos( beta ) * height;
321 const double dy2 = std::sin( beta ) * height;
322 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + dx1, y + dy1 );
323 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + dx1 + dx2, y + dy1 + dy2 );
324 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x + dx2, y + dy2 );
328 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + width, y );
329 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + width, y + height );
330 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x, y + height );
333 GEOSCoordSeq_setXY_r( geosctxt, coord, 4, x, y );
335 geos::unique_ptr bboxGeos( GEOSGeom_createLinearRing_r( geosctxt, coord ) );
336 const bool result = ( GEOSPreparedContainsProperly_r( geosctxt, geom, bboxGeos.get() ) == 1 );
339 catch ( GEOSException &e )
341 qWarning(
"GEOS exception: %s", e.what() );
351 double x1,
double y1,
double x2,
double y2,
352 double &xRes,
double &yRes )
354 double multiplier = 1;
366 radius *= multiplier;
369 const double dx = x2 - x1;
370 const double dy = y2 - y1;
372 const double A = dx * dx + dy * dy;
373 const double B = 2 * ( dx * ( x1 - cx ) + dy * ( y1 - cy ) );
374 const double C = ( x1 - cx ) * ( x1 - cx ) + ( y1 - cy ) * ( y1 - cy ) - radius * radius;
376 const double det = B * B - 4 * A * C;
377 if ( A <= 0.000000000001 || det < 0 )
384 const double t = -B / ( 2 * A );
393 const double t = ( -B + std::sqrt( det ) ) / ( 2 * A );
398 if ( multiplier != 1 )
static double sqrDistance2D(double x1, double y1, double x2, double y2)
Returns the squared 2D distance between (x1, y1) and (x2, y2).
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).
static bool reorderPolygon(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.
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.
static void findLineCircleIntersection(double cx, double cy, double radius, double x1, double y1, double x2, double y2, double &xRes, double &yRes)
void heapsort(std::vector< int > &sid, int *id, const std::vector< double > &x, std::size_t N)
void heapsort2(int *x, double *heap, std::size_t N)
#define Q_NOWARN_UNREACHABLE_PUSH
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
#define Q_NOWARN_UNREACHABLE_POP