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;
136bool GeomFunction::isSegIntersects(
double x1,
double y1,
double x2,
double y2,
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 getGEOSHandler()
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 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)
std::unique_ptr< GEOSGeometry, GeosDeleter > unique_ptr
Scoped GEOS pointer.
#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