37 void heapsort(
int *sid,
int *
id,
const double*
const x,
int N )
39 unsigned int n = N, i = n / 2, parent, child;
59 if ( child + 1 < n && x[
id[sid[child + 1]]] > x[
id[sid[child]]] )
63 if ( x[
id[sid[child]]] > x[
id[tx]] )
65 sid[parent] = sid[child];
67 child = parent * 2 + 1;
81 unsigned int n = N, i = n / 2, parent, child;
105 if ( child + 1 < n && heap[child + 1] > heap[child] )
109 if ( heap[child] > t )
111 heap[parent] = heap[child];
112 x[parent] = x[child];
114 child = parent * 2 + 1;
127 double x3,
double y3,
double x4,
double y4 )
129 return (
cross_product( x1, y1, x2, y2, x3, y3 ) *
cross_product( x1, y1, x2, y2, x4, y4 ) < 0
130 &&
cross_product( x3, y3, x4, y4, x1, y1 ) *
cross_product( x3, y3, x4, y4, x2, y2 ) < 0 );
134 double x3,
double y3,
double x4,
double y4,
135 double *x,
double *y )
138 double a1, a2, b1, b2, c1, c2;
143 c1 = x2 * y1 - x1 * y2;
147 c2 = x4 * y3 - x3 * y4;
149 denom = a1 * b2 - a2 * b1;
156 *x = ( b1 * c2 - b2 * c1 ) / denom;
157 *y = ( a2 * c1 - a1 * c2 ) / denom;
168 for ( i = 0; i < n; i++ )
174 if ( n <= 3 )
return n;
176 int* stack =
new int[n];
177 double* tan =
new double [n];
188 while ( ref < n &&
qgsDoubleNear( y[
id[cHull[ref]]], y[
id[cHull[0]]] ) ) ref++;
193 for ( i = ref; i < n; i++ )
198 tan[i] = ( x[
id[cHull[0]]] - x[
id[cHull[i]]] ) / ( y[
id[cHull[i]]] - y[
id[cHull[0]]] );
202 heapsort2( cHull + ref, tan + ref, n - ref );
212 stack[1] = cHull[ref-1];
218 for ( i = ref; i < n; i++ )
220 result =
cross_product( x[
id[stack[second]]], y[
id[stack[second]]],
221 x[
id[stack[top]]], y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
225 if (
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[cHull[i]]], y[
id[cHull[i]]] )
226 >
dist_euc2d_sq( x[
id[stack[second]]], y[
id[stack[second]]], x[
id[stack[top]]], y[
id[stack[top]]] ) )
228 stack[top] = cHull[i];
231 else if ( result > 0 )
235 stack[top] = cHull[i];
239 while ( result < 0 && top > 1 )
244 y[
id[stack[second]]], x[
id[stack[top]]],
245 y[
id[stack[top]]], x[
id[cHull[i]]], y[
id[cHull[i]]] );
249 stack[top] = cHull[i];
253 for ( i = 0; i <= top; i++ )
270 int *pts =
new int[nbPoints];
271 for ( i = 0; i < nbPoints; i++ )
276 if ( pts[cHull[0]] < pts[cHull[1]] && pts[cHull[1]] < pts[cHull[2]] )
278 else 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]] && pts[cHull[2]] < pts[cHull[0]] )
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]] )
300 for ( i = 0, j = nbPoints - 1; i <= j; i++, j-- )
319 double x1,
double y1,
double x2,
double y2,
320 double& xRes,
double& yRes )
325 double A = dx * dx + dy * dy;
326 double B = 2 * ( dx * ( x1 - cx ) + dy * ( y1 - cy ) );
327 double C = ( x1 - cx ) * ( x1 - cx ) + ( y1 - cy ) * ( y1 - cy ) - radius * radius;
329 double det = B * B - 4 * A * C;
330 if ( A <= 0.0000001 || det < 0 )
337 double t = -B / ( 2 * A );
346 double t = ( -B + 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)
static double cross_product(double x1, double y1, double x2, double y2, double x3, double y3)
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))
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...
static double dist_euc2d_sq(double x1, double y1, double x2, double y2)