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;
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 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 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