40void heapsort( std::vector< int > &sid,
int *
id,
const std::vector< double > &x, std::size_t N )
43 std::size_t i = n / 2;
65 if ( child + 1 < n && x[
id[sid[child + 1]]] > x[
id[sid[child]]] )
69 if ( x[
id[sid[child]]] > x[
id[tx]] )
71 sid[parent] = sid[child];
73 child = parent * 2 + 1;
85void heapsort2(
int *x,
double *heap, std::size_t N )
88 std::size_t i = n / 2;
104 if ( n == 0 )
return;
114 if ( child + 1 < n && heap[child + 1] > heap[child] )
118 if ( heap[child] > t )
120 heap[parent] = heap[child];
121 x[parent] = x[child];
123 child = parent * 2 + 1;
135bool GeomFunction::isSegIntersects(
double x1,
double y1,
double x2,
double y2,
136 double x3,
double y3,
double x4,
double y4 )
138 return (
cross_product( x1, y1, x2, y2, x3, y3 ) *
cross_product( x1, y1, x2, y2, x4, y4 ) < 0
139 &&
cross_product( x3, y3, x4, y4, x1, y1 ) *
cross_product( x3, y3, x4, y4, x2, y2 ) < 0 );
143 double x3,
double y3,
double x4,
double y4,
144 double *x,
double *y )
147 double a1, a2, b1, b2, c1, c2;
152 c1 = x2 * y1 - x1 * y2;
156 c2 = x4 * y3 - x3 * y4;
158 denom = a1 * b2 - a2 * b1;
165 *x = ( b1 * c2 - b2 * c1 ) / denom;
166 *y = ( a2 * c1 - a1 * c2 ) / denom;
174 std::vector< int > convexHull( x.size() );
175 for ( std::size_t i = 0; i < x.size(); i++ )
177 convexHull[i] =
static_cast< int >( i );
183 std::vector< int > stack( x.size() );
184 std::vector< double > tan( x.size() );
187 heapsort( convexHull,
id.data(), y, y.size() );
191 while ( ref < x.size() &&
qgsDoubleNear( y[
id[convexHull[ref]]], y[
id[convexHull[0]]] ) )
194 heapsort( convexHull,
id.data(), x, ref );
197 for ( std::size_t i = ref; i < x.size(); i++ )
199 if (
qgsDoubleNear( y[
id[convexHull[i]]], y[
id[convexHull[0]]] ) )
202 tan[i] = ( x[
id[convexHull[0]]] - x[
id[convexHull[i]]] ) / ( y[
id[convexHull[i]]] - y[
id[convexHull[0]]] );
205 if ( ref < x.size() )
206 heapsort2( convexHull.data() + ref, tan.data() + ref, x.size() - ref );
209 stack[0] = convexHull[0];
212 stack[1] = convexHull[1];
216 stack[1] = convexHull[ref - 1];
219 std::size_t second = 0;
221 for ( std::size_t i = ref; i < x.size(); i++ )
223 double result =
cross_product( x[
id[stack[second]]], y[
id[stack[second]]],
224 x[
id[stack[top]]], y[
id[stack[top]]], x[
id[convexHull[i]]], y[
id[convexHull[i]]] );
228 if (
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[convexHull[i]]], y[
id[convexHull[i]]] )
229 >
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[stack[top]]], y[
id[stack[top]]] ) )
231 stack[top] = convexHull[i];
234 else if ( result > 0 )
238 stack[top] = convexHull[i];
242 while ( result < 0 && top > 1 )
247 y[
id[stack[second]]], x[
id[stack[top]]],
248 y[
id[stack[top]]], x[
id[convexHull[i]]], y[
id[convexHull[i]]] );
252 stack[top] = convexHull[i];
256 for ( std::size_t i = 0; i <= top; i++ )
258 convexHull[i] = stack[i];
261 convexHull.resize( top + 1 );
267 std::vector< int > pts( x.size() );
268 for ( std::size_t i = 0; i < x.size(); i++ )
269 pts[i] =
static_cast< int >( i );
271 std::vector< int > convexHull =
convexHullId( pts, x, y );
274 if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] )
276 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] )
278 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] && pts[convexHull[2]] < pts[convexHull[0]] )
280 else if ( pts[convexHull[0]] > pts[convexHull[1]] && pts[convexHull[1]] < pts[convexHull[2]] && pts[convexHull[2]] > pts[convexHull[0]] )
282 else if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] && pts[convexHull[2]] > pts[convexHull[0]] )
284 else if ( pts[convexHull[0]] < pts[convexHull[1]] && pts[convexHull[1]] > pts[convexHull[2]] && pts[convexHull[2]] < pts[convexHull[0]] )
294 for ( std::size_t i = 0, j = x.size() - 1; i <= j; i++, j-- )
296 std::swap( x[i], x[j] );
297 std::swap( y[i], y[j] );
311 GEOSCoordSequence *coord = GEOSCoordSeq_create_r( geosctxt, 5, 2 );
313 GEOSCoordSeq_setXY_r( geosctxt, coord, 0, x, y );
316 const double beta = alpha + M_PI_2;
317 const double dx1 = std::cos( alpha ) * width;
318 const double dy1 = std::sin( alpha ) * width;
319 const double dx2 = std::cos( beta ) * height;
320 const double dy2 = std::sin( beta ) * height;
321 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + dx1, y + dy1 );
322 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + dx1 + dx2, y + dy1 + dy2 );
323 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x + dx2, y + dy2 );
327 GEOSCoordSeq_setXY_r( geosctxt, coord, 1, x + width, y );
328 GEOSCoordSeq_setXY_r( geosctxt, coord, 2, x + width, y + height );
329 GEOSCoordSeq_setXY_r( geosctxt, coord, 3, x, y + height );
332 GEOSCoordSeq_setXY_r( geosctxt, coord, 4, x, y );
334 geos::unique_ptr bboxGeos( GEOSGeom_createLinearRing_r( geosctxt, coord ) );
335 const bool result = ( GEOSPreparedContainsProperly_r( geosctxt, geom, bboxGeos.get() ) == 1 );
338 catch ( GEOSException &e )
340 qWarning(
"GEOS exception: %s", e.what() );
350 double x1,
double y1,
double x2,
double y2,
351 double &xRes,
double &yRes )
353 double multiplier = 1;
365 radius *= multiplier;
368 const double dx = x2 - x1;
369 const double dy = y2 - y1;
371 const double A = dx * dx + dy * dy;
372 const double B = 2 * ( dx * ( x1 - cx ) + dy * ( y1 - cy ) );
373 const double C = ( x1 - cx ) * ( x1 - cx ) + ( y1 - cy ) * ( y1 - cy ) - radius * radius;
375 const double det = B * B - 4 * A * C;
376 if ( A <= 0.000000000001 || det < 0 )
383 const double t = -B / ( 2 * A );
392 const double t = ( -B + std::sqrt( det ) ) / ( 2 * A );
397 if ( multiplier != 1 )
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 double dist_euc2d_sq(double x1, double y1, double x2, double y2)
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