Debian Codegraph @

ext/rtree/geopoly.c

raw
1 /*
2 ** 2018-05-25
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
10 **
11 ******************************************************************************
12 **
13 ** This file implements an alternative R-Tree virtual table that
14 ** uses polygons to express the boundaries of 2-dimensional objects.
15 **
16 ** This file is #include-ed onto the end of "rtree.c" so that it has
17 ** access to all of the R-Tree internals.
18 */
19 #include <stdlib.h>
20
21 /* Enable -DGEOPOLY_ENABLE_DEBUG for debugging facilities */
22 #ifdef GEOPOLY_ENABLE_DEBUG
23 static int geo_debug = 0;
24 # define GEODEBUG(X) if(geo_debug)printf X
25 #else
26 # define GEODEBUG(X)
27 #endif
28
29 /* Character class routines */
30 #ifdef sqlite3Isdigit
31 /* Use the SQLite core versions if this routine is part of the
32 ** SQLite amalgamation */
33 # define safe_isdigit(x) sqlite3Isdigit(x)
34 # define safe_isalnum(x) sqlite3Isalnum(x)
35 # define safe_isxdigit(x) sqlite3Isxdigit(x)
36 #else
37 /* Use the standard library for separate compilation */
38 #include <ctype.h> /* amalgamator: keep */
39 # define safe_isdigit(x) isdigit((unsigned char)(x))
40 # define safe_isalnum(x) isalnum((unsigned char)(x))
41 # define safe_isxdigit(x) isxdigit((unsigned char)(x))
42 #endif
43
44 #ifndef JSON_NULL /* The following stuff repeats things found in json1 */
45 /*
46 ** Growing our own isspace() routine this way is twice as fast as
47 ** the library isspace() function.
48 */
49 static const char geopolyIsSpace[] = {
50 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0,
51 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
52 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
53 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
54 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
55 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
56 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
57 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
58 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
59 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
60 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
61 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
62 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
63 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
64 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
65 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66 };
67 #define fast_isspace(x) (geopolyIsSpace[(unsigned char)x])
68 #endif /* JSON NULL - back to original code */
69
70 /* Compiler and version */
71 #ifndef GCC_VERSION
72 #if defined(__GNUC__) && !defined(SQLITE_DISABLE_INTRINSIC)
73 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
74 #else
75 # define GCC_VERSION 0
76 #endif
77 #endif
78 #ifndef MSVC_VERSION
79 #if defined(_MSC_VER) && !defined(SQLITE_DISABLE_INTRINSIC)
80 # define MSVC_VERSION _MSC_VER
81 #else
82 # define MSVC_VERSION 0
83 #endif
84 #endif
85
86 /* Datatype for coordinates
87 */
88 typedef float GeoCoord;
89
90 /*
91 ** Internal representation of a polygon.
92 **
93 ** The polygon consists of a sequence of vertexes. There is a line
94 ** segment between each pair of vertexes, and one final segment from
95 ** the last vertex back to the first. (This differs from the GeoJSON
96 ** standard in which the final vertex is a repeat of the first.)
97 **
98 ** The polygon follows the right-hand rule. The area to the right of
99 ** each segment is "outside" and the area to the left is "inside".
100 **
101 ** The on-disk representation consists of a 4-byte header followed by
102 ** the values. The 4-byte header is:
103 **
104 ** encoding (1 byte) 0=big-endian, 1=little-endian
105 ** nvertex (3 bytes) Number of vertexes as a big-endian integer
106 **
107 ** Enough space is allocated for 4 coordinates, to work around over-zealous
108 ** warnings coming from some compiler (notably, clang). In reality, the size
109 ** of each GeoPoly memory allocate is adjusted as necessary so that the
110 ** GeoPoly.a[] array at the end is the appropriate size.
111 */
112 typedef struct GeoPoly GeoPoly;
113 struct GeoPoly {
114 int nVertex; /* Number of vertexes */
115 unsigned char hdr[4]; /* Header for on-disk representation */
116 GeoCoord a[8]; /* 2*nVertex values. X (longitude) first, then Y */
117 };
118
119 /* The size of a memory allocation needed for a GeoPoly object sufficient
120 ** to hold N coordinate pairs.
121 */
122 #define GEOPOLY_SZ(N) (sizeof(GeoPoly) + sizeof(GeoCoord)*2*((N)-4))
123
124 /* Macros to access coordinates of a GeoPoly.
125 ** We have to use these macros, rather than just say p->a[i] in order
126 ** to silence (incorrect) UBSAN warnings if the array index is too large.
127 */
128 #define GeoX(P,I) (((GeoCoord*)(P)->a)[(I)*2])
129 #define GeoY(P,I) (((GeoCoord*)(P)->a)[(I)*2+1])
130
131
132 /*
133 ** State of a parse of a GeoJSON input.
134 */
135 typedef struct GeoParse GeoParse;
136 struct GeoParse {
137 const unsigned char *z; /* Unparsed input */
138 int nVertex; /* Number of vertexes in a[] */
139 int nAlloc; /* Space allocated to a[] */
140 int nErr; /* Number of errors encountered */
141 GeoCoord *a; /* Array of vertexes. From sqlite3_malloc64() */
142 };
143
144 /* Do a 4-byte byte swap */
145 static void geopolySwab32(unsigned char *a){
146 unsigned char t = a[0];
147 a[0] = a[3];
148 a[3] = t;
149 t = a[1];
150 a[1] = a[2];
151 a[2] = t;
152 }
153
154 /* Skip whitespace. Return the next non-whitespace character. */
155 static char geopolySkipSpace(GeoParse *p){
156 while( fast_isspace(p->z[0]) ) p->z++;
157 return p->z[0];
158 }
159
160 /* Parse out a number. Write the value into *pVal if pVal!=0.
161 ** return non-zero on success and zero if the next token is not a number.
162 */
163 static int geopolyParseNumber(GeoParse *p, GeoCoord *pVal){
164 char c = geopolySkipSpace(p);
165 const unsigned char *z = p->z;
166 int j = 0;
167 int seenDP = 0;
168 int seenE = 0;
169 if( c=='-' ){
170 j = 1;
171 c = z[j];
172 }
173 if( c=='0' && z[j+1]>='0' && z[j+1]<='9' ) return 0;
174 for(;; j++){
175 c = z[j];
176 if( safe_isdigit(c) ) continue;
177 if( c=='.' ){
178 if( z[j-1]=='-' ) return 0;
179 if( seenDP ) return 0;
180 seenDP = 1;
181 continue;
182 }
183 if( c=='e' || c=='E' ){
184 if( z[j-1]<'0' ) return 0;
185 if( seenE ) return -1;
186 seenDP = seenE = 1;
187 c = z[j+1];
188 if( c=='+' || c=='-' ){
189 j++;
190 c = z[j+1];
191 }
192 if( c<'0' || c>'9' ) return 0;
193 continue;
194 }
195 break;
196 }
197 if( z[j-1]<'0' ) return 0;
198 if( pVal ){
199 #ifdef SQLITE_AMALGAMATION
200 /* The sqlite3AtoF() routine is much much faster than atof(), if it
201 ** is available */
202 double r;
203 (void)sqlite3AtoF((const char*)p->z, &r);
204 *pVal = r;
205 #else
206 *pVal = (GeoCoord)atof((const char*)p->z);
207 #endif
208 }
209 p->z += j;
210 return 1;
211 }
212
213 /*
214 ** If the input is a well-formed JSON array of coordinates with at least
215 ** four coordinates and where each coordinate is itself a two-value array,
216 ** then convert the JSON into a GeoPoly object and return a pointer to
217 ** that object.
218 **
219 ** If any error occurs, return NULL.
220 */
221 static GeoPoly *geopolyParseJson(const unsigned char *z, int *pRc){
222 GeoParse s;
223 int rc = SQLITE_OK;
224 memset(&s, 0, sizeof(s));
225 s.z = z;
226 if( geopolySkipSpace(&s)=='[' ){
227 s.z++;
228 while( geopolySkipSpace(&s)=='[' ){
229 int ii = 0;
230 char c;
231 s.z++;
232 if( s.nVertex>=s.nAlloc ){
233 GeoCoord *aNew;
234 s.nAlloc = s.nAlloc*2 + 16;
235 aNew = sqlite3_realloc64(s.a, s.nAlloc*sizeof(GeoCoord)*2 );
236 if( aNew==0 ){
237 rc = SQLITE_NOMEM;
238 s.nErr++;
239 break;
240 }
241 s.a = aNew;
242 }
243 while( geopolyParseNumber(&s, ii<=1 ? &s.a[s.nVertex*2+ii] : 0) ){
244 ii++;
245 if( ii==2 ) s.nVertex++;
246 c = geopolySkipSpace(&s);
247 s.z++;
248 if( c==',' ) continue;
249 if( c==']' && ii>=2 ) break;
250 s.nErr++;
251 rc = SQLITE_ERROR;
252 goto parse_json_err;
253 }
254 if( geopolySkipSpace(&s)==',' ){
255 s.z++;
256 continue;
257 }
258 break;
259 }
260 if( geopolySkipSpace(&s)==']'
261 && s.nVertex>=4
262 && s.a[0]==s.a[s.nVertex*2-2]
263 && s.a[1]==s.a[s.nVertex*2-1]
264 && (s.z++, geopolySkipSpace(&s)==0)
265 ){
266 GeoPoly *pOut;
267 int x = 1;
268 s.nVertex--; /* Remove the redundant vertex at the end */
269 pOut = sqlite3_malloc64( GEOPOLY_SZ((sqlite3_int64)s.nVertex) );
270 x = 1;
271 if( pOut==0 ) goto parse_json_err;
272 pOut->nVertex = s.nVertex;
273 memcpy(pOut->a, s.a, s.nVertex*2*sizeof(GeoCoord));
274 pOut->hdr[0] = *(unsigned char*)&x;
275 pOut->hdr[1] = (s.nVertex>>16)&0xff;
276 pOut->hdr[2] = (s.nVertex>>8)&0xff;
277 pOut->hdr[3] = s.nVertex&0xff;
278 sqlite3_free(s.a);
279 if( pRc ) *pRc = SQLITE_OK;
280 return pOut;
281 }else{
282 s.nErr++;
283 rc = SQLITE_ERROR;
284 }
285 }
286 parse_json_err:
287 if( pRc ) *pRc = rc;
288 sqlite3_free(s.a);
289 return 0;
290 }
291
292 /*
293 ** Given a function parameter, try to interpret it as a polygon, either
294 ** in the binary format or JSON text. Compute a GeoPoly object and
295 ** return a pointer to that object. Or if the input is not a well-formed
296 ** polygon, put an error message in sqlite3_context and return NULL.
297 */
298 static GeoPoly *geopolyFuncParam(
299 sqlite3_context *pCtx, /* Context for error messages */
300 sqlite3_value *pVal, /* The value to decode */
301 int *pRc /* Write error here */
302 ){
303 GeoPoly *p = 0;
304 int nByte;
305 testcase( pCtx==0 );
306 if( sqlite3_value_type(pVal)==SQLITE_BLOB
307 && (nByte = sqlite3_value_bytes(pVal))>=(int)(4+6*sizeof(GeoCoord))
308 ){
309 const unsigned char *a = sqlite3_value_blob(pVal);
310 int nVertex;
311 if( a==0 ){
312 if( pCtx ) sqlite3_result_error_nomem(pCtx);
313 return 0;
314 }
315 nVertex = (a[1]<<16) + (a[2]<<8) + a[3];
316 if( (a[0]==0 || a[0]==1)
317 && (nVertex*2*sizeof(GeoCoord) + 4)==(unsigned int)nByte
318 ){
319 p = sqlite3_malloc64( sizeof(*p) + (nVertex-1)*2*sizeof(GeoCoord) );
320 if( p==0 ){
321 if( pRc ) *pRc = SQLITE_NOMEM;
322 if( pCtx ) sqlite3_result_error_nomem(pCtx);
323 }else{
324 int x = 1;
325 p->nVertex = nVertex;
326 memcpy(p->hdr, a, nByte);
327 if( a[0] != *(unsigned char*)&x ){
328 int ii;
329 for(ii=0; ii<nVertex; ii++){
330 geopolySwab32((unsigned char*)&GeoX(p,ii));
331 geopolySwab32((unsigned char*)&GeoY(p,ii));
332 }
333 p->hdr[0] ^= 1;
334 }
335 }
336 }
337 if( pRc ) *pRc = SQLITE_OK;
338 return p;
339 }else if( sqlite3_value_type(pVal)==SQLITE_TEXT ){
340 const unsigned char *zJson = sqlite3_value_text(pVal);
341 if( zJson==0 ){
342 if( pRc ) *pRc = SQLITE_NOMEM;
343 return 0;
344 }
345 return geopolyParseJson(zJson, pRc);
346 }else{
347 if( pRc ) *pRc = SQLITE_ERROR;
348 return 0;
349 }
350 }
351
352 /*
353 ** Implementation of the geopoly_blob(X) function.
354 **
355 ** If the input is a well-formed Geopoly BLOB or JSON string
356 ** then return the BLOB representation of the polygon. Otherwise
357 ** return NULL.
358 */
359 static void geopolyBlobFunc(
360 sqlite3_context *context,
361 int argc,
362 sqlite3_value **argv
363 ){
364 GeoPoly *p = geopolyFuncParam(context, argv[0], 0);
365 (void)argc;
366 if( p ){
367 sqlite3_result_blob(context, p->hdr,
368 4+8*p->nVertex, SQLITE_TRANSIENT);
369 sqlite3_free(p);
370 }
371 }
372
373 /*
374 ** SQL function: geopoly_json(X)
375 **
376 ** Interpret X as a polygon and render it as a JSON array
377 ** of coordinates. Or, if X is not a valid polygon, return NULL.
378 */
379 static void geopolyJsonFunc(
380 sqlite3_context *context,
381 int argc,
382 sqlite3_value **argv
383 ){
384 GeoPoly *p = geopolyFuncParam(context, argv[0], 0);
385 (void)argc;
386 if( p ){
387 sqlite3 *db = sqlite3_context_db_handle(context);
388 sqlite3_str *x = sqlite3_str_new(db);
389 int i;
390 sqlite3_str_append(x, "[", 1);
391 for(i=0; i<p->nVertex; i++){
392 sqlite3_str_appendf(x, "[%!g,%!g],", GeoX(p,i), GeoY(p,i));
393 }
394 sqlite3_str_appendf(x, "[%!g,%!g]]", GeoX(p,0), GeoY(p,0));
395 sqlite3_result_text(context, sqlite3_str_finish(x), -1, sqlite3_free);
396 sqlite3_free(p);
397 }
398 }
399
400 /*
401 ** SQL function: geopoly_svg(X, ....)
402 **
403 ** Interpret X as a polygon and render it as a SVG <polyline>.
404 ** Additional arguments are added as attributes to the <polyline>.
405 */
406 static void geopolySvgFunc(
407 sqlite3_context *context,
408 int argc,
409 sqlite3_value **argv
410 ){
411 GeoPoly *p;
412 if( argc<1 ) return;
413 p = geopolyFuncParam(context, argv[0], 0);
414 if( p ){
415 sqlite3 *db = sqlite3_context_db_handle(context);
416 sqlite3_str *x = sqlite3_str_new(db);
417 int i;
418 char cSep = '\'';
419 sqlite3_str_appendf(x, "<polyline points=");
420 for(i=0; i<p->nVertex; i++){
421 sqlite3_str_appendf(x, "%c%g,%g", cSep, GeoX(p,i), GeoY(p,i));
422 cSep = ' ';
423 }
424 sqlite3_str_appendf(x, " %g,%g'", GeoX(p,0), GeoY(p,0));
425 for(i=1; i<argc; i++){
426 const char *z = (const char*)sqlite3_value_text(argv[i]);
427 if( z && z[0] ){
428 sqlite3_str_appendf(x, " %s", z);
429 }
430 }
431 sqlite3_str_appendf(x, "></polyline>");
432 sqlite3_result_text(context, sqlite3_str_finish(x), -1, sqlite3_free);
433 sqlite3_free(p);
434 }
435 }
436
437 /*
438 ** SQL Function: geopoly_xform(poly, A, B, C, D, E, F)
439 **
440 ** Transform and/or translate a polygon as follows:
441 **
442 ** x1 = A*x0 + B*y0 + E
443 ** y1 = C*x0 + D*y0 + F
444 **
445 ** For a translation:
446 **
447 ** geopoly_xform(poly, 1, 0, 0, 1, x-offset, y-offset)
448 **
449 ** Rotate by R around the point (0,0):
450 **
451 ** geopoly_xform(poly, cos(R), sin(R), -sin(R), cos(R), 0, 0)
452 */
453 static void geopolyXformFunc(
454 sqlite3_context *context,
455 int argc,
456 sqlite3_value **argv
457 ){
458 GeoPoly *p = geopolyFuncParam(context, argv[0], 0);
459 double A = sqlite3_value_double(argv[1]);
460 double B = sqlite3_value_double(argv[2]);
461 double C = sqlite3_value_double(argv[3]);
462 double D = sqlite3_value_double(argv[4]);
463 double E = sqlite3_value_double(argv[5]);
464 double F = sqlite3_value_double(argv[6]);
465 GeoCoord x1, y1, x0, y0;
466 int ii;
467 (void)argc;
468 if( p ){
469 for(ii=0; ii<p->nVertex; ii++){
470 x0 = GeoX(p,ii);
471 y0 = GeoY(p,ii);
472 x1 = (GeoCoord)(A*x0 + B*y0 + E);
473 y1 = (GeoCoord)(C*x0 + D*y0 + F);
474 GeoX(p,ii) = x1;
475 GeoY(p,ii) = y1;
476 }
477 sqlite3_result_blob(context, p->hdr,
478 4+8*p->nVertex, SQLITE_TRANSIENT);
479 sqlite3_free(p);
480 }
481 }
482
483 /*
484 ** Compute the area enclosed by the polygon.
485 **
486 ** This routine can also be used to detect polygons that rotate in
487 ** the wrong direction. Polygons are suppose to be counter-clockwise (CCW).
488 ** This routine returns a negative value for clockwise (CW) polygons.
489 */
490 static double geopolyArea(GeoPoly *p){
491 double rArea = 0.0;
492 int ii;
493 for(ii=0; ii<p->nVertex-1; ii++){
494 rArea += (GeoX(p,ii) - GeoX(p,ii+1)) /* (x0 - x1) */
495 * (GeoY(p,ii) + GeoY(p,ii+1)) /* (y0 + y1) */
496 * 0.5;
497 }
498 rArea += (GeoX(p,ii) - GeoX(p,0)) /* (xN - x0) */
499 * (GeoY(p,ii) + GeoY(p,0)) /* (yN + y0) */
500 * 0.5;
501 return rArea;
502 }
503
504 /*
505 ** Implementation of the geopoly_area(X) function.
506 **
507 ** If the input is a well-formed Geopoly BLOB then return the area
508 ** enclosed by the polygon. If the polygon circulates clockwise instead
509 ** of counterclockwise (as it should) then return the negative of the
510 ** enclosed area. Otherwise return NULL.
511 */
512 static void geopolyAreaFunc(
513 sqlite3_context *context,
514 int argc,
515 sqlite3_value **argv
516 ){
517 GeoPoly *p = geopolyFuncParam(context, argv[0], 0);
518 (void)argc;
519 if( p ){
520 sqlite3_result_double(context, geopolyArea(p));
521 sqlite3_free(p);
522 }
523 }
524
525 /*
526 ** Implementation of the geopoly_ccw(X) function.
527 **
528 ** If the rotation of polygon X is clockwise (incorrect) instead of
529 ** counter-clockwise (the correct winding order according to RFC7946)
530 ** then reverse the order of the vertexes in polygon X.
531 **
532 ** In other words, this routine returns a CCW polygon regardless of the
533 ** winding order of its input.
534 **
535 ** Use this routine to sanitize historical inputs that that sometimes
536 ** contain polygons that wind in the wrong direction.
537 */
538 static void geopolyCcwFunc(
539 sqlite3_context *context,
540 int argc,
541 sqlite3_value **argv
542 ){
543 GeoPoly *p = geopolyFuncParam(context, argv[0], 0);
544 (void)argc;
545 if( p ){
546 if( geopolyArea(p)<0.0 ){
547 int ii, jj;
548 for(ii=1, jj=p->nVertex-1; ii<jj; ii++, jj--){
549 GeoCoord t = GeoX(p,ii);
550 GeoX(p,ii) = GeoX(p,jj);
551 GeoX(p,jj) = t;
552 t = GeoY(p,ii);
553 GeoY(p,ii) = GeoY(p,jj);
554 GeoY(p,jj) = t;
555 }
556 }
557 sqlite3_result_blob(context, p->hdr,
558 4+8*p->nVertex, SQLITE_TRANSIENT);
559 sqlite3_free(p);
560 }
561 }
562
563 #define GEOPOLY_PI 3.1415926535897932385
564
565 /* Fast approximation for sine(X) for X between -0.5*pi and 2*pi
566 */
567 static double geopolySine(double r){
568 assert( r>=-0.5*GEOPOLY_PI && r<=2.0*GEOPOLY_PI );
569 if( r>=1.5*GEOPOLY_PI ){
570 r -= 2.0*GEOPOLY_PI;
571 }
572 if( r>=0.5*GEOPOLY_PI ){
573 return -geopolySine(r-GEOPOLY_PI);
574 }else{
575 double r2 = r*r;
576 double r3 = r2*r;
577 double r5 = r3*r2;
578 return 0.9996949*r - 0.1656700*r3 + 0.0075134*r5;
579 }
580 }
581
582 /*
583 ** Function: geopoly_regular(X,Y,R,N)
584 **
585 ** Construct a simple, convex, regular polygon centered at X, Y
586 ** with circumradius R and with N sides.
587 */
588 static void geopolyRegularFunc(
589 sqlite3_context *context,
590 int argc,
591 sqlite3_value **argv
592 ){
593 double x = sqlite3_value_double(argv[0]);
594 double y = sqlite3_value_double(argv[1]);
595 double r = sqlite3_value_double(argv[2]);
596 int n = sqlite3_value_int(argv[3]);
597 int i;
598 GeoPoly *p;
599 (void)argc;
600
601 if( n<3 || r<=0.0 ) return;
602 if( n>1000 ) n = 1000;
603 p = sqlite3_malloc64( sizeof(*p) + (n-1)*2*sizeof(GeoCoord) );
604 if( p==0 ){
605 sqlite3_result_error_nomem(context);
606 return;
607 }
608 i = 1;
609 p->hdr[0] = *(unsigned char*)&i;
610 p->hdr[1] = 0;
611 p->hdr[2] = (n>>8)&0xff;
612 p->hdr[3] = n&0xff;
613 for(i=0; i<n; i++){
614 double rAngle = 2.0*GEOPOLY_PI*i/n;
615 GeoX(p,i) = x - r*geopolySine(rAngle-0.5*GEOPOLY_PI);
616 GeoY(p,i) = y + r*geopolySine(rAngle);
617 }
618 sqlite3_result_blob(context, p->hdr, 4+8*n, SQLITE_TRANSIENT);
619 sqlite3_free(p);
620 }
621
622 /*
623 ** If pPoly is a polygon, compute its bounding box. Then:
624 **
625 ** (1) if aCoord!=0 store the bounding box in aCoord, returning NULL
626 ** (2) otherwise, compute a GeoPoly for the bounding box and return the
627 ** new GeoPoly
628 **
629 ** If pPoly is NULL but aCoord is not NULL, then compute a new GeoPoly from
630 ** the bounding box in aCoord and return a pointer to that GeoPoly.
631 */
632 static GeoPoly *geopolyBBox(
633 sqlite3_context *context, /* For recording the error */
634 sqlite3_value *pPoly, /* The polygon */
635 RtreeCoord *aCoord, /* Results here */
636 int *pRc /* Error code here */
637 ){
638 GeoPoly *pOut = 0;
639 GeoPoly *p;
640 float mnX, mxX, mnY, mxY;
641 if( pPoly==0 && aCoord!=0 ){
642 p = 0;
643 mnX = aCoord[0].f;
644 mxX = aCoord[1].f;
645 mnY = aCoord[2].f;
646 mxY = aCoord[3].f;
647 goto geopolyBboxFill;
648 }else{
649 p = geopolyFuncParam(context, pPoly, pRc);
650 }
651 if( p ){
652 int ii;
653 mnX = mxX = GeoX(p,0);
654 mnY = mxY = GeoY(p,0);
655 for(ii=1; ii<p->nVertex; ii++){
656 double r = GeoX(p,ii);
657 if( r<mnX ) mnX = (float)r;
658 else if( r>mxX ) mxX = (float)r;
659 r = GeoY(p,ii);
660 if( r<mnY ) mnY = (float)r;
661 else if( r>mxY ) mxY = (float)r;
662 }
663 if( pRc ) *pRc = SQLITE_OK;
664 if( aCoord==0 ){
665 geopolyBboxFill:
666 pOut = sqlite3_realloc64(p, GEOPOLY_SZ(4));
667 if( pOut==0 ){
668 sqlite3_free(p);
669 if( context ) sqlite3_result_error_nomem(context);
670 if( pRc ) *pRc = SQLITE_NOMEM;
671 return 0;
672 }
673 pOut->nVertex = 4;
674 ii = 1;
675 pOut->hdr[0] = *(unsigned char*)&ii;
676 pOut->hdr[1] = 0;
677 pOut->hdr[2] = 0;
678 pOut->hdr[3] = 4;
679 GeoX(pOut,0) = mnX;
680 GeoY(pOut,0) = mnY;
681 GeoX(pOut,1) = mxX;
682 GeoY(pOut,1) = mnY;
683 GeoX(pOut,2) = mxX;
684 GeoY(pOut,2) = mxY;
685 GeoX(pOut,3) = mnX;
686 GeoY(pOut,3) = mxY;
687 }else{
688 sqlite3_free(p);
689 aCoord[0].f = mnX;
690 aCoord[1].f = mxX;
691 aCoord[2].f = mnY;
692 aCoord[3].f = mxY;
693 }
694 }else if( aCoord ){
695 memset(aCoord, 0, sizeof(RtreeCoord)*4);
696 }
697 return pOut;
698 }
699
700 /*
701 ** Implementation of the geopoly_bbox(X) SQL function.
702 */
703 static void geopolyBBoxFunc(
704 sqlite3_context *context,
705 int argc,
706 sqlite3_value **argv
707 ){
708 GeoPoly *p = geopolyBBox(context, argv[0], 0, 0);
709 (void)argc;
710 if( p ){
711 sqlite3_result_blob(context, p->hdr,
712 4+8*p->nVertex, SQLITE_TRANSIENT);
713 sqlite3_free(p);
714 }
715 }
716
717 /*
718 ** State vector for the geopoly_group_bbox() aggregate function.
719 */
720 typedef struct GeoBBox GeoBBox;
721 struct GeoBBox {
722 int isInit;
723 RtreeCoord a[4];
724 };
725
726
727 /*
728 ** Implementation of the geopoly_group_bbox(X) aggregate SQL function.
729 */
730 static void geopolyBBoxStep(
731 sqlite3_context *context,
732 int argc,
733 sqlite3_value **argv
734 ){
735 RtreeCoord a[4];
736 int rc = SQLITE_OK;
737 (void)argc;
738 (void)geopolyBBox(context, argv[0], a, &rc);
739 if( rc==SQLITE_OK ){
740 GeoBBox *pBBox;
741 pBBox = (GeoBBox*)sqlite3_aggregate_context(context, sizeof(*pBBox));
742 if( pBBox==0 ) return;
743 if( pBBox->isInit==0 ){
744 pBBox->isInit = 1;
745 memcpy(pBBox->a, a, sizeof(RtreeCoord)*4);
746 }else{
747 if( a[0].f < pBBox->a[0].f ) pBBox->a[0] = a[0];
748 if( a[1].f > pBBox->a[1].f ) pBBox->a[1] = a[1];
749 if( a[2].f < pBBox->a[2].f ) pBBox->a[2] = a[2];
750 if( a[3].f > pBBox->a[3].f ) pBBox->a[3] = a[3];
751 }
752 }
753 }
754 static void geopolyBBoxFinal(
755 sqlite3_context *context
756 ){
757 GeoPoly *p;
758 GeoBBox *pBBox;
759 pBBox = (GeoBBox*)sqlite3_aggregate_context(context, 0);
760 if( pBBox==0 ) return;
761 p = geopolyBBox(context, 0, pBBox->a, 0);
762 if( p ){
763 sqlite3_result_blob(context, p->hdr,
764 4+8*p->nVertex, SQLITE_TRANSIENT);
765 sqlite3_free(p);
766 }
767 }
768
769
770 /*
771 ** Determine if point (x0,y0) is beneath line segment (x1,y1)->(x2,y2).
772 ** Returns:
773 **
774 ** +2 x0,y0 is on the line segment
775 **
776 ** +1 x0,y0 is beneath line segment
777 **
778 ** 0 x0,y0 is not on or beneath the line segment or the line segment
779 ** is vertical and x0,y0 is not on the line segment
780 **
781 ** The left-most coordinate min(x1,x2) is not considered to be part of
782 ** the line segment for the purposes of this analysis.
783 */
784 static int pointBeneathLine(
785 double x0, double y0,
786 double x1, double y1,
787 double x2, double y2
788 ){
789 double y;
790 if( x0==x1 && y0==y1 ) return 2;
791 if( x1<x2 ){
792 if( x0<=x1 || x0>x2 ) return 0;
793 }else if( x1>x2 ){
794 if( x0<=x2 || x0>x1 ) return 0;
795 }else{
796 /* Vertical line segment */
797 if( x0!=x1 ) return 0;
798 if( y0<y1 && y0<y2 ) return 0;
799 if( y0>y1 && y0>y2 ) return 0;
800 return 2;
801 }
802 y = y1 + (y2-y1)*(x0-x1)/(x2-x1);
803 if( y0==y ) return 2;
804 if( y0<y ) return 1;
805 return 0;
806 }
807
808 /*
809 ** SQL function: geopoly_contains_point(P,X,Y)
810 **
811 ** Return +2 if point X,Y is within polygon P.
812 ** Return +1 if point X,Y is on the polygon boundary.
813 ** Return 0 if point X,Y is outside the polygon
814 */
815 static void geopolyContainsPointFunc(
816 sqlite3_context *context,
817 int argc,
818 sqlite3_value **argv
819 ){
820 GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);
821 double x0 = sqlite3_value_double(argv[1]);
822 double y0 = sqlite3_value_double(argv[2]);
823 int v = 0;
824 int cnt = 0;
825 int ii;
826 (void)argc;
827
828 if( p1==0 ) return;
829 for(ii=0; ii<p1->nVertex-1; ii++){
830 v = pointBeneathLine(x0,y0,GeoX(p1,ii), GeoY(p1,ii),
831 GeoX(p1,ii+1),GeoY(p1,ii+1));
832 if( v==2 ) break;
833 cnt += v;
834 }
835 if( v!=2 ){
836 v = pointBeneathLine(x0,y0,GeoX(p1,ii), GeoY(p1,ii),
837 GeoX(p1,0), GeoY(p1,0));
838 }
839 if( v==2 ){
840 sqlite3_result_int(context, 1);
841 }else if( ((v+cnt)&1)==0 ){
842 sqlite3_result_int(context, 0);
843 }else{
844 sqlite3_result_int(context, 2);
845 }
846 sqlite3_free(p1);
847 }
848
849 /* Forward declaration */
850 static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2);
851
852 /*
853 ** SQL function: geopoly_within(P1,P2)
854 **
855 ** Return +2 if P1 and P2 are the same polygon
856 ** Return +1 if P2 is contained within P1
857 ** Return 0 if any part of P2 is on the outside of P1
858 **
859 */
860 static void geopolyWithinFunc(
861 sqlite3_context *context,
862 int argc,
863 sqlite3_value **argv
864 ){
865 GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);
866 GeoPoly *p2 = geopolyFuncParam(context, argv[1], 0);
867 (void)argc;
868 if( p1 && p2 ){
869 int x = geopolyOverlap(p1, p2);
870 if( x<0 ){
871 sqlite3_result_error_nomem(context);
872 }else{
873 sqlite3_result_int(context, x==2 ? 1 : x==4 ? 2 : 0);
874 }
875 }
876 sqlite3_free(p1);
877 sqlite3_free(p2);
878 }
879
880 /* Objects used by the overlap algorithm. */
881 typedef struct GeoEvent GeoEvent;
882 typedef struct GeoSegment GeoSegment;
883 typedef struct GeoOverlap GeoOverlap;
884 struct GeoEvent {
885 double x; /* X coordinate at which event occurs */
886 int eType; /* 0 for ADD, 1 for REMOVE */
887 GeoSegment *pSeg; /* The segment to be added or removed */
888 GeoEvent *pNext; /* Next event in the sorted list */
889 };
890 struct GeoSegment {
891 double C, B; /* y = C*x + B */
892 double y; /* Current y value */
893 float y0; /* Initial y value */
894 unsigned char side; /* 1 for p1, 2 for p2 */
895 unsigned int idx; /* Which segment within the side */
896 GeoSegment *pNext; /* Next segment in a list sorted by y */
897 };
898 struct GeoOverlap {
899 GeoEvent *aEvent; /* Array of all events */
900 GeoSegment *aSegment; /* Array of all segments */
901 int nEvent; /* Number of events */
902 int nSegment; /* Number of segments */
903 };
904
905 /*
906 ** Add a single segment and its associated events.
907 */
908 static void geopolyAddOneSegment(
909 GeoOverlap *p,
910 GeoCoord x0,
911 GeoCoord y0,
912 GeoCoord x1,
913 GeoCoord y1,
914 unsigned char side,
915 unsigned int idx
916 ){
917 GeoSegment *pSeg;
918 GeoEvent *pEvent;
919 if( x0==x1 ) return; /* Ignore vertical segments */
920 if( x0>x1 ){
921 GeoCoord t = x0;
922 x0 = x1;
923 x1 = t;
924 t = y0;
925 y0 = y1;
926 y1 = t;
927 }
928 pSeg = p->aSegment + p->nSegment;
929 p->nSegment++;
930 pSeg->C = (y1-y0)/(x1-x0);
931 pSeg->B = y1 - x1*pSeg->C;
932 pSeg->y0 = y0;
933 pSeg->side = side;
934 pSeg->idx = idx;
935 pEvent = p->aEvent + p->nEvent;
936 p->nEvent++;
937 pEvent->x = x0;
938 pEvent->eType = 0;
939 pEvent->pSeg = pSeg;
940 pEvent = p->aEvent + p->nEvent;
941 p->nEvent++;
942 pEvent->x = x1;
943 pEvent->eType = 1;
944 pEvent->pSeg = pSeg;
945 }
946
947
948
949 /*
950 ** Insert all segments and events for polygon pPoly.
951 */
952 static void geopolyAddSegments(
953 GeoOverlap *p, /* Add segments to this Overlap object */
954 GeoPoly *pPoly, /* Take all segments from this polygon */
955 unsigned char side /* The side of pPoly */
956 ){
957 unsigned int i;
958 GeoCoord *x;
959 for(i=0; i<(unsigned)pPoly->nVertex-1; i++){
960 x = &GeoX(pPoly,i);
961 geopolyAddOneSegment(p, x[0], x[1], x[2], x[3], side, i);
962 }
963 x = &GeoX(pPoly,i);
964 geopolyAddOneSegment(p, x[0], x[1], pPoly->a[0], pPoly->a[1], side, i);
965 }
966
967 /*
968 ** Merge two lists of sorted events by X coordinate
969 */
970 static GeoEvent *geopolyEventMerge(GeoEvent *pLeft, GeoEvent *pRight){
971 GeoEvent head, *pLast;
972 head.pNext = 0;
973 pLast = &head;
974 while( pRight && pLeft ){
975 if( pRight->x <= pLeft->x ){
976 pLast->pNext = pRight;
977 pLast = pRight;
978 pRight = pRight->pNext;
979 }else{
980 pLast->pNext = pLeft;
981 pLast = pLeft;
982 pLeft = pLeft->pNext;
983 }
984 }
985 pLast->pNext = pRight ? pRight : pLeft;
986 return head.pNext;
987 }
988
989 /*
990 ** Sort an array of nEvent event objects into a list.
991 */
992 static GeoEvent *geopolySortEventsByX(GeoEvent *aEvent, int nEvent){
993 int mx = 0;
994 int i, j;
995 GeoEvent *p;
996 GeoEvent *a[50];
997 for(i=0; i<nEvent; i++){
998 p = &aEvent[i];
999 p->pNext = 0;
1000 for(j=0; j<mx && a[j]; j++){
1001 p = geopolyEventMerge(a[j], p);
1002 a[j] = 0;
1003 }
1004 a[j] = p;
1005 if( j>=mx ) mx = j+1;
1006 }
1007 p = 0;
1008 for(i=0; i<mx; i++){
1009 p = geopolyEventMerge(a[i], p);
1010 }
1011 return p;
1012 }
1013
1014 /*
1015 ** Merge two lists of sorted segments by Y, and then by C.
1016 */
1017 static GeoSegment *geopolySegmentMerge(GeoSegment *pLeft, GeoSegment *pRight){
1018 GeoSegment head, *pLast;
1019 head.pNext = 0;
1020 pLast = &head;
1021 while( pRight && pLeft ){
1022 double r = pRight->y - pLeft->y;
1023 if( r==0.0 ) r = pRight->C - pLeft->C;
1024 if( r<0.0 ){
1025 pLast->pNext = pRight;
1026 pLast = pRight;
1027 pRight = pRight->pNext;
1028 }else{
1029 pLast->pNext = pLeft;
1030 pLast = pLeft;
1031 pLeft = pLeft->pNext;
1032 }
1033 }
1034 pLast->pNext = pRight ? pRight : pLeft;
1035 return head.pNext;
1036 }
1037
1038 /*
1039 ** Sort a list of GeoSegments in order of increasing Y and in the event of
1040 ** a tie, increasing C (slope).
1041 */
1042 static GeoSegment *geopolySortSegmentsByYAndC(GeoSegment *pList){
1043 int mx = 0;
1044 int i;
1045 GeoSegment *p;
1046 GeoSegment *a[50];
1047 while( pList ){
1048 p = pList;
1049 pList = pList->pNext;
1050 p->pNext = 0;
1051 for(i=0; i<mx && a[i]; i++){
1052 p = geopolySegmentMerge(a[i], p);
1053 a[i] = 0;
1054 }
1055 a[i] = p;
1056 if( i>=mx ) mx = i+1;
1057 }
1058 p = 0;
1059 for(i=0; i<mx; i++){
1060 p = geopolySegmentMerge(a[i], p);
1061 }
1062 return p;
1063 }
1064
1065 /*
1066 ** Determine the overlap between two polygons
1067 */
1068 static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2){
1069 sqlite3_int64 nVertex = p1->nVertex + p2->nVertex + 2;
1070 GeoOverlap *p;
1071 sqlite3_int64 nByte;
1072 GeoEvent *pThisEvent;
1073 double rX;
1074 int rc = 0;
1075 int needSort = 0;
1076 GeoSegment *pActive = 0;
1077 GeoSegment *pSeg;
1078 unsigned char aOverlap[4];
1079
1080 nByte = sizeof(GeoEvent)*nVertex*2
1081 + sizeof(GeoSegment)*nVertex
1082 + sizeof(GeoOverlap);
1083 p = sqlite3_malloc64( nByte );
1084 if( p==0 ) return -1;
1085 p->aEvent = (GeoEvent*)&p[1];
1086 p->aSegment = (GeoSegment*)&p->aEvent[nVertex*2];
1087 p->nEvent = p->nSegment = 0;
1088 geopolyAddSegments(p, p1, 1);
1089 geopolyAddSegments(p, p2, 2);
1090 pThisEvent = geopolySortEventsByX(p->aEvent, p->nEvent);
1091 rX = pThisEvent && pThisEvent->x==0.0 ? -1.0 : 0.0;
1092 memset(aOverlap, 0, sizeof(aOverlap));
1093 while( pThisEvent ){
1094 if( pThisEvent->x!=rX ){
1095 GeoSegment *pPrev = 0;
1096 int iMask = 0;
1097 GEODEBUG(("Distinct X: %g\n", pThisEvent->x));
1098 rX = pThisEvent->x;
1099 if( needSort ){
1100 GEODEBUG(("SORT\n"));
1101 pActive = geopolySortSegmentsByYAndC(pActive);
1102 needSort = 0;
1103 }
1104 for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
1105 if( pPrev ){
1106 if( pPrev->y!=pSeg->y ){
1107 GEODEBUG(("MASK: %d\n", iMask));
1108 aOverlap[iMask] = 1;
1109 }
1110 }
1111 iMask ^= pSeg->side;
1112 pPrev = pSeg;
1113 }
1114 pPrev = 0;
1115 for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
1116 double y = pSeg->C*rX + pSeg->B;
1117 GEODEBUG(("Segment %d.%d %g->%g\n", pSeg->side, pSeg->idx, pSeg->y, y));
1118 pSeg->y = y;
1119 if( pPrev ){
1120 if( pPrev->y>pSeg->y && pPrev->side!=pSeg->side ){
1121 rc = 1;
1122 GEODEBUG(("Crossing: %d.%d and %d.%d\n",
1123 pPrev->side, pPrev->idx,
1124 pSeg->side, pSeg->idx));
1125 goto geopolyOverlapDone;
1126 }else if( pPrev->y!=pSeg->y ){
1127 GEODEBUG(("MASK: %d\n", iMask));
1128 aOverlap[iMask] = 1;
1129 }
1130 }
1131 iMask ^= pSeg->side;
1132 pPrev = pSeg;
1133 }
1134 }
1135 GEODEBUG(("%s %d.%d C=%g B=%g\n",
1136 pThisEvent->eType ? "RM " : "ADD",
1137 pThisEvent->pSeg->side, pThisEvent->pSeg->idx,
1138 pThisEvent->pSeg->C,
1139 pThisEvent->pSeg->B));
1140 if( pThisEvent->eType==0 ){
1141 /* Add a segment */
1142 pSeg = pThisEvent->pSeg;
1143 pSeg->y = pSeg->y0;
1144 pSeg->pNext = pActive;
1145 pActive = pSeg;
1146 needSort = 1;
1147 }else{
1148 /* Remove a segment */
1149 if( pActive==pThisEvent->pSeg ){
1150 pActive = ALWAYS(pActive) ? pActive->pNext : 0;
1151 }else{
1152 for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
1153 if( pSeg->pNext==pThisEvent->pSeg ){
1154 pSeg->pNext = ALWAYS(pSeg->pNext) ? pSeg->pNext->pNext : 0;
1155 break;
1156 }
1157 }
1158 }
1159 }
1160 pThisEvent = pThisEvent->pNext;
1161 }
1162 if( aOverlap[3]==0 ){
1163 rc = 0;
1164 }else if( aOverlap[1]!=0 && aOverlap[2]==0 ){
1165 rc = 3;
1166 }else if( aOverlap[1]==0 && aOverlap[2]!=0 ){
1167 rc = 2;
1168 }else if( aOverlap[1]==0 && aOverlap[2]==0 ){
1169 rc = 4;
1170 }else{
1171 rc = 1;
1172 }
1173
1174 geopolyOverlapDone:
1175 sqlite3_free(p);
1176 return rc;
1177 }
1178
1179 /*
1180 ** SQL function: geopoly_overlap(P1,P2)
1181 **
1182 ** Determine whether or not P1 and P2 overlap. Return value:
1183 **
1184 ** 0 The two polygons are disjoint
1185 ** 1 They overlap
1186 ** 2 P1 is completely contained within P2
1187 ** 3 P2 is completely contained within P1
1188 ** 4 P1 and P2 are the same polygon
1189 ** NULL Either P1 or P2 or both are not valid polygons
1190 */
1191 static void geopolyOverlapFunc(
1192 sqlite3_context *context,
1193 int argc,
1194 sqlite3_value **argv
1195 ){
1196 GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);
1197 GeoPoly *p2 = geopolyFuncParam(context, argv[1], 0);
1198 (void)argc;
1199 if( p1 && p2 ){
1200 int x = geopolyOverlap(p1, p2);
1201 if( x<0 ){
1202 sqlite3_result_error_nomem(context);
1203 }else{
1204 sqlite3_result_int(context, x);
1205 }
1206 }
1207 sqlite3_free(p1);
1208 sqlite3_free(p2);
1209 }
1210
1211 /*
1212 ** Enable or disable debugging output
1213 */
1214 static void geopolyDebugFunc(
1215 sqlite3_context *context,
1216 int argc,
1217 sqlite3_value **argv
1218 ){
1219 (void)context;
1220 (void)argc;
1221 #ifdef GEOPOLY_ENABLE_DEBUG
1222 geo_debug = sqlite3_value_int(argv[0]);
1223 #else
1224 (void)argv;
1225 #endif
1226 }
1227
1228 /*
1229 ** This function is the implementation of both the xConnect and xCreate
1230 ** methods of the geopoly virtual table.
1231 **
1232 ** argv[0] -> module name
1233 ** argv[1] -> database name
1234 ** argv[2] -> table name
1235 ** argv[...] -> column names...
1236 */
1237 static int geopolyInit(
1238 sqlite3 *db, /* Database connection */
1239 void *pAux, /* One of the RTREE_COORD_* constants */
1240 int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */
1241 sqlite3_vtab **ppVtab, /* OUT: New virtual table */
1242 char **pzErr, /* OUT: Error message, if any */
1243 int isCreate /* True for xCreate, false for xConnect */
1244 ){
1245 int rc = SQLITE_OK;
1246 Rtree *pRtree;
1247 sqlite3_int64 nDb; /* Length of string argv[1] */
1248 sqlite3_int64 nName; /* Length of string argv[2] */
1249 sqlite3_str *pSql;
1250 char *zSql;
1251 int ii;
1252 (void)pAux;
1253
1254 if( argc>=RTREE_MAX_AUX_COLUMN+4 ){
1255 *pzErr = sqlite3_mprintf("Too many columns for a geopoly table");
1256 return SQLITE_ERROR;
1257 }
1258
1259 sqlite3_vtab_config(db, SQLITE_VTAB_CONSTRAINT_SUPPORT, 1);
1260 sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
1261
1262 /* Allocate the sqlite3_vtab structure */
1263 nDb = strlen(argv[1]);
1264 nName = strlen(argv[2]);
1265 pRtree = (Rtree *)sqlite3_malloc64(sizeof(Rtree)+nDb+nName*2+8);
1266 if( !pRtree ){
1267 return SQLITE_NOMEM;
1268 }
1269 memset(pRtree, 0, sizeof(Rtree)+nDb+nName*2+8);
1270 pRtree->nBusy = 1;
1271 pRtree->base.pModule = &rtreeModule;
1272 pRtree->zDb = (char *)&pRtree[1];
1273 pRtree->zName = &pRtree->zDb[nDb+1];
1274 pRtree->zNodeName = &pRtree->zName[nName+1];
1275 pRtree->eCoordType = RTREE_COORD_REAL32;
1276 pRtree->nDim = 2;
1277 pRtree->nDim2 = 4;
1278 memcpy(pRtree->zDb, argv[1], nDb);
1279 memcpy(pRtree->zName, argv[2], nName);
1280 memcpy(pRtree->zNodeName, argv[2], nName);
1281 memcpy(&pRtree->zNodeName[nName], "_node", 6);
1282
1283
1284 /* Create/Connect to the underlying relational database schema. If
1285 ** that is successful, call sqlite3_declare_vtab() to configure
1286 ** the r-tree table schema.
1287 */
1288 pSql = sqlite3_str_new(db);
1289 sqlite3_str_appendf(pSql, "CREATE TABLE x(_shape");
1290 pRtree->nAux = 1; /* Add one for _shape */
1291 pRtree->nAuxNotNull = 1; /* The _shape column is always not-null */
1292 for(ii=3; ii<argc; ii++){
1293 pRtree->nAux++;
1294 sqlite3_str_appendf(pSql, ",%s", argv[ii]);
1295 }
1296 sqlite3_str_appendf(pSql, ");");
1297 zSql = sqlite3_str_finish(pSql);
1298 if( !zSql ){
1299 rc = SQLITE_NOMEM;
1300 }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){
1301 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
1302 }
1303 sqlite3_free(zSql);
1304 if( rc ) goto geopolyInit_fail;
1305 pRtree->nBytesPerCell = 8 + pRtree->nDim2*4;
1306
1307 /* Figure out the node size to use. */
1308 rc = getNodeSize(db, pRtree, isCreate, pzErr);
1309 if( rc ) goto geopolyInit_fail;
1310 rc = rtreeSqlInit(pRtree, db, argv[1], argv[2], isCreate);
1311 if( rc ){
1312 *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
1313 goto geopolyInit_fail;
1314 }
1315
1316 *ppVtab = (sqlite3_vtab *)pRtree;
1317 return SQLITE_OK;
1318
1319 geopolyInit_fail:
1320 if( rc==SQLITE_OK ) rc = SQLITE_ERROR;
1321 assert( *ppVtab==0 );
1322 assert( pRtree->nBusy==1 );
1323 rtreeRelease(pRtree);
1324 return rc;
1325 }
1326
1327
1328 /*
1329 ** GEOPOLY virtual table module xCreate method.
1330 */
1331 static int geopolyCreate(
1332 sqlite3 *db,
1333 void *pAux,
1334 int argc, const char *const*argv,
1335 sqlite3_vtab **ppVtab,
1336 char **pzErr
1337 ){
1338 return geopolyInit(db, pAux, argc, argv, ppVtab, pzErr, 1);
1339 }
1340
1341 /*
1342 ** GEOPOLY virtual table module xConnect method.
1343 */
1344 static int geopolyConnect(
1345 sqlite3 *db,
1346 void *pAux,
1347 int argc, const char *const*argv,
1348 sqlite3_vtab **ppVtab,
1349 char **pzErr
1350 ){
1351 return geopolyInit(db, pAux, argc, argv, ppVtab, pzErr, 0);
1352 }
1353
1354
1355 /*
1356 ** GEOPOLY virtual table module xFilter method.
1357 **
1358 ** Query plans:
1359 **
1360 ** 1 rowid lookup
1361 ** 2 search for objects overlapping the same bounding box
1362 ** that contains polygon argv[0]
1363 ** 3 search for objects overlapping the same bounding box
1364 ** that contains polygon argv[0]
1365 ** 4 full table scan
1366 */
1367 static int geopolyFilter(
1368 sqlite3_vtab_cursor *pVtabCursor, /* The cursor to initialize */
1369 int idxNum, /* Query plan */
1370 const char *idxStr, /* Not Used */
1371 int argc, sqlite3_value **argv /* Parameters to the query plan */
1372 ){
1373 Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
1374 RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
1375 RtreeNode *pRoot = 0;
1376 int rc = SQLITE_OK;
1377 int iCell = 0;
1378 (void)idxStr;
1379
1380 rtreeReference(pRtree);
1381
1382 /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
1383 resetCursor(pCsr);
1384
1385 pCsr->iStrategy = idxNum;
1386 if( idxNum==1 ){
1387 /* Special case - lookup by rowid. */
1388 RtreeNode *pLeaf; /* Leaf on which the required cell resides */
1389 RtreeSearchPoint *p; /* Search point for the leaf */
1390 i64 iRowid = sqlite3_value_int64(argv[0]);
1391 i64 iNode = 0;
1392 rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
1393 if( rc==SQLITE_OK && pLeaf!=0 ){
1394 p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
1395 assert( p!=0 ); /* Always returns pCsr->sPoint */
1396 pCsr->aNode[0] = pLeaf;
1397 p->id = iNode;
1398 p->eWithin = PARTLY_WITHIN;
1399 rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
1400 p->iCell = (u8)iCell;
1401 RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
1402 }else{
1403 pCsr->atEOF = 1;
1404 }
1405 }else{
1406 /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array
1407 ** with the configured constraints.
1408 */
1409 rc = nodeAcquire(pRtree, 1, 0, &pRoot);
1410 if( rc==SQLITE_OK && idxNum<=3 ){
1411 RtreeCoord bbox[4];
1412 RtreeConstraint *p;
1413 assert( argc==1 );
1414 assert( argv[0]!=0 );
1415 geopolyBBox(0, argv[0], bbox, &rc);
1416 if( rc ){
1417 goto geopoly_filter_end;
1418 }
1419 pCsr->aConstraint = p = sqlite3_malloc(sizeof(RtreeConstraint)*4);
1420 pCsr->nConstraint = 4;
1421 if( p==0 ){
1422 rc = SQLITE_NOMEM;
1423 }else{
1424 memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*4);
1425 memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
1426 if( idxNum==2 ){
1427 /* Overlap query */
1428 p->op = 'B';
1429 p->iCoord = 0;
1430 p->u.rValue = bbox[1].f;
1431 p++;
1432 p->op = 'D';
1433 p->iCoord = 1;
1434 p->u.rValue = bbox[0].f;
1435 p++;
1436 p->op = 'B';
1437 p->iCoord = 2;
1438 p->u.rValue = bbox[3].f;
1439 p++;
1440 p->op = 'D';
1441 p->iCoord = 3;
1442 p->u.rValue = bbox[2].f;
1443 }else{
1444 /* Within query */
1445 p->op = 'D';
1446 p->iCoord = 0;
1447 p->u.rValue = bbox[0].f;
1448 p++;
1449 p->op = 'B';
1450 p->iCoord = 1;
1451 p->u.rValue = bbox[1].f;
1452 p++;
1453 p->op = 'D';
1454 p->iCoord = 2;
1455 p->u.rValue = bbox[2].f;
1456 p++;
1457 p->op = 'B';
1458 p->iCoord = 3;
1459 p->u.rValue = bbox[3].f;
1460 }
1461 }
1462 }
1463 if( rc==SQLITE_OK ){
1464 RtreeSearchPoint *pNew;
1465 pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1));
1466 if( pNew==0 ){
1467 rc = SQLITE_NOMEM;
1468 goto geopoly_filter_end;
1469 }
1470 pNew->id = 1;
1471 pNew->iCell = 0;
1472 pNew->eWithin = PARTLY_WITHIN;
1473 assert( pCsr->bPoint==1 );
1474 pCsr->aNode[0] = pRoot;
1475 pRoot = 0;
1476 RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
1477 rc = rtreeStepToLeaf(pCsr);
1478 }
1479 }
1480
1481 geopoly_filter_end:
1482 nodeRelease(pRtree, pRoot);
1483 rtreeRelease(pRtree);
1484 return rc;
1485 }
1486
1487 /*
1488 ** Rtree virtual table module xBestIndex method. There are three
1489 ** table scan strategies to choose from (in order from most to
1490 ** least desirable):
1491 **
1492 ** idxNum idxStr Strategy
1493 ** ------------------------------------------------
1494 ** 1 "rowid" Direct lookup by rowid.
1495 ** 2 "rtree" R-tree overlap query using geopoly_overlap()
1496 ** 3 "rtree" R-tree within query using geopoly_within()
1497 ** 4 "fullscan" full-table scan.
1498 ** ------------------------------------------------
1499 */
1500 static int geopolyBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
1501 int ii;
1502 int iRowidTerm = -1;
1503 int iFuncTerm = -1;
1504 int idxNum = 0;
1505 (void)tab;
1506
1507 for(ii=0; ii<pIdxInfo->nConstraint; ii++){
1508 struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];
1509 if( !p->usable ) continue;
1510 if( p->iColumn<0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
1511 iRowidTerm = ii;
1512 break;
1513 }
1514 if( p->iColumn==0 && p->op>=SQLITE_INDEX_CONSTRAINT_FUNCTION ){
1515 /* p->op==SQLITE_INDEX_CONSTRAINT_FUNCTION for geopoly_overlap()
1516 ** p->op==(SQLITE_INDEX_CONTRAINT_FUNCTION+1) for geopoly_within().
1517 ** See geopolyFindFunction() */
1518 iFuncTerm = ii;
1519 idxNum = p->op - SQLITE_INDEX_CONSTRAINT_FUNCTION + 2;
1520 }
1521 }
1522
1523 if( iRowidTerm>=0 ){
1524 pIdxInfo->idxNum = 1;
1525 pIdxInfo->idxStr = "rowid";
1526 pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1;
1527 pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1;
1528 pIdxInfo->estimatedCost = 30.0;
1529 pIdxInfo->estimatedRows = 1;
1530 pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
1531 return SQLITE_OK;
1532 }
1533 if( iFuncTerm>=0 ){
1534 pIdxInfo->idxNum = idxNum;
1535 pIdxInfo->idxStr = "rtree";
1536 pIdxInfo->aConstraintUsage[iFuncTerm].argvIndex = 1;
1537 pIdxInfo->aConstraintUsage[iFuncTerm].omit = 0;
1538 pIdxInfo->estimatedCost = 300.0;
1539 pIdxInfo->estimatedRows = 10;
1540 return SQLITE_OK;
1541 }
1542 pIdxInfo->idxNum = 4;
1543 pIdxInfo->idxStr = "fullscan";
1544 pIdxInfo->estimatedCost = 3000000.0;
1545 pIdxInfo->estimatedRows = 100000;
1546 return SQLITE_OK;
1547 }
1548
1549
1550 /*
1551 ** GEOPOLY virtual table module xColumn method.
1552 */
1553 static int geopolyColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
1554 Rtree *pRtree = (Rtree *)cur->pVtab;
1555 RtreeCursor *pCsr = (RtreeCursor *)cur;
1556 RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
1557 int rc = SQLITE_OK;
1558 RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
1559
1560 if( rc ) return rc;
1561 if( p==0 ) return SQLITE_OK;
1562 if( i==0 && sqlite3_vtab_nochange(ctx) ) return SQLITE_OK;
1563 if( i<=pRtree->nAux ){
1564 if( !pCsr->bAuxValid ){
1565 if( pCsr->pReadAux==0 ){
1566 rc = sqlite3_prepare_v3(pRtree->db, pRtree->zReadAuxSql, -1, 0,
1567 &pCsr->pReadAux, 0);
1568 if( rc ) return rc;
1569 }
1570 sqlite3_bind_int64(pCsr->pReadAux, 1,
1571 nodeGetRowid(pRtree, pNode, p->iCell));
1572 rc = sqlite3_step(pCsr->pReadAux);
1573 if( rc==SQLITE_ROW ){
1574 pCsr->bAuxValid = 1;
1575 }else{
1576 sqlite3_reset(pCsr->pReadAux);
1577 if( rc==SQLITE_DONE ) rc = SQLITE_OK;
1578 return rc;
1579 }
1580 }
1581 sqlite3_result_value(ctx, sqlite3_column_value(pCsr->pReadAux, i+2));
1582 }
1583 return SQLITE_OK;
1584 }
1585
1586
1587 /*
1588 ** The xUpdate method for GEOPOLY module virtual tables.
1589 **
1590 ** For DELETE:
1591 **
1592 ** argv[0] = the rowid to be deleted
1593 **
1594 ** For INSERT:
1595 **
1596 ** argv[0] = SQL NULL
1597 ** argv[1] = rowid to insert, or an SQL NULL to select automatically
1598 ** argv[2] = _shape column
1599 ** argv[3] = first application-defined column....
1600 **
1601 ** For UPDATE:
1602 **
1603 ** argv[0] = rowid to modify. Never NULL
1604 ** argv[1] = rowid after the change. Never NULL
1605 ** argv[2] = new value for _shape
1606 ** argv[3] = new value for first application-defined column....
1607 */
1608 static int geopolyUpdate(
1609 sqlite3_vtab *pVtab,
1610 int nData,
1611 sqlite3_value **aData,
1612 sqlite_int64 *pRowid
1613 ){
1614 Rtree *pRtree = (Rtree *)pVtab;
1615 int rc = SQLITE_OK;
1616 RtreeCell cell; /* New cell to insert if nData>1 */
1617 i64 oldRowid; /* The old rowid */
1618 int oldRowidValid; /* True if oldRowid is valid */
1619 i64 newRowid; /* The new rowid */
1620 int newRowidValid; /* True if newRowid is valid */
1621 int coordChange = 0; /* Change in coordinates */
1622
1623 if( pRtree->nNodeRef ){
1624 /* Unable to write to the btree while another cursor is reading from it,
1625 ** since the write might do a rebalance which would disrupt the read
1626 ** cursor. */
1627 return SQLITE_LOCKED_VTAB;
1628 }
1629 rtreeReference(pRtree);
1630 assert(nData>=1);
1631
1632 oldRowidValid = sqlite3_value_type(aData[0])!=SQLITE_NULL;;
1633 oldRowid = oldRowidValid ? sqlite3_value_int64(aData[0]) : 0;
1634 newRowidValid = nData>1 && sqlite3_value_type(aData[1])!=SQLITE_NULL;
1635 newRowid = newRowidValid ? sqlite3_value_int64(aData[1]) : 0;
1636 cell.iRowid = newRowid;
1637
1638 if( nData>1 /* not a DELETE */
1639 && (!oldRowidValid /* INSERT */
1640 || !sqlite3_value_nochange(aData[2]) /* UPDATE _shape */
1641 || oldRowid!=newRowid) /* Rowid change */
1642 ){
1643 assert( aData[2]!=0 );
1644 geopolyBBox(0, aData[2], cell.aCoord, &rc);
1645 if( rc ){
1646 if( rc==SQLITE_ERROR ){
1647 pVtab->zErrMsg =
1648 sqlite3_mprintf("_shape does not contain a valid polygon");
1649 }
1650 goto geopoly_update_end;
1651 }
1652 coordChange = 1;
1653
1654 /* If a rowid value was supplied, check if it is already present in
1655 ** the table. If so, the constraint has failed. */
1656 if( newRowidValid && (!oldRowidValid || oldRowid!=newRowid) ){
1657 int steprc;
1658 sqlite3_bind_int64(pRtree->pReadRowid, 1, cell.iRowid);
1659 steprc = sqlite3_step(pRtree->pReadRowid);
1660 rc = sqlite3_reset(pRtree->pReadRowid);
1661 if( SQLITE_ROW==steprc ){
1662 if( sqlite3_vtab_on_conflict(pRtree->db)==SQLITE_REPLACE ){
1663 rc = rtreeDeleteRowid(pRtree, cell.iRowid);
1664 }else{
1665 rc = rtreeConstraintError(pRtree, 0);
1666 }
1667 }
1668 }
1669 }
1670
1671 /* If aData[0] is not an SQL NULL value, it is the rowid of a
1672 ** record to delete from the r-tree table. The following block does
1673 ** just that.
1674 */
1675 if( rc==SQLITE_OK && (nData==1 || (coordChange && oldRowidValid)) ){
1676 rc = rtreeDeleteRowid(pRtree, oldRowid);
1677 }
1678
1679 /* If the aData[] array contains more than one element, elements
1680 ** (aData[2]..aData[argc-1]) contain a new record to insert into
1681 ** the r-tree structure.
1682 */
1683 if( rc==SQLITE_OK && nData>1 && coordChange ){
1684 /* Insert the new record into the r-tree */
1685 RtreeNode *pLeaf = 0;
1686 if( !newRowidValid ){
1687 rc = rtreeNewRowid(pRtree, &cell.iRowid);
1688 }
1689 *pRowid = cell.iRowid;
1690 if( rc==SQLITE_OK ){
1691 rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
1692 }
1693 if( rc==SQLITE_OK ){
1694 int rc2;
1695 rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
1696 rc2 = nodeRelease(pRtree, pLeaf);
1697 if( rc==SQLITE_OK ){
1698 rc = rc2;
1699 }
1700 }
1701 }
1702
1703 /* Change the data */
1704 if( rc==SQLITE_OK && nData>1 ){
1705 sqlite3_stmt *pUp = pRtree->pWriteAux;
1706 int jj;
1707 int nChange = 0;
1708 sqlite3_bind_int64(pUp, 1, cell.iRowid);
1709 assert( pRtree->nAux>=1 );
1710 if( sqlite3_value_nochange(aData[2]) ){
1711 sqlite3_bind_null(pUp, 2);
1712 }else{
1713 GeoPoly *p = 0;
1714 if( sqlite3_value_type(aData[2])==SQLITE_TEXT
1715 && (p = geopolyFuncParam(0, aData[2], &rc))!=0
1716 && rc==SQLITE_OK
1717 ){
1718 sqlite3_bind_blob(pUp, 2, p->hdr, 4+8*p->nVertex, SQLITE_TRANSIENT);
1719 }else{
1720 sqlite3_bind_value(pUp, 2, aData[2]);
1721 }
1722 sqlite3_free(p);
1723 nChange = 1;
1724 }
1725 for(jj=1; jj<nData-2; jj++){
1726 nChange++;
1727 sqlite3_bind_value(pUp, jj+2, aData[jj+2]);
1728 }
1729 if( nChange ){
1730 sqlite3_step(pUp);
1731 rc = sqlite3_reset(pUp);
1732 }
1733 }
1734
1735 geopoly_update_end:
1736 rtreeRelease(pRtree);
1737 return rc;
1738 }
1739
1740 /*
1741 ** Report that geopoly_overlap() is an overloaded function suitable
1742 ** for use in xBestIndex.
1743 */
1744 static int geopolyFindFunction(
1745 sqlite3_vtab *pVtab,
1746 int nArg,
1747 const char *zName,
1748 void (**pxFunc)(sqlite3_context*,int,sqlite3_value**),
1749 void **ppArg
1750 ){
1751 (void)pVtab;
1752 (void)nArg;
1753 if( sqlite3_stricmp(zName, "geopoly_overlap")==0 ){
1754 *pxFunc = geopolyOverlapFunc;
1755 *ppArg = 0;
1756 return SQLITE_INDEX_CONSTRAINT_FUNCTION;
1757 }
1758 if( sqlite3_stricmp(zName, "geopoly_within")==0 ){
1759 *pxFunc = geopolyWithinFunc;
1760 *ppArg = 0;
1761 return SQLITE_INDEX_CONSTRAINT_FUNCTION+1;
1762 }
1763 return 0;
1764 }
1765
1766
1767 static sqlite3_module geopolyModule = {
1768 3, /* iVersion */
1769 geopolyCreate, /* xCreate - create a table */
1770 geopolyConnect, /* xConnect - connect to an existing table */
1771 geopolyBestIndex, /* xBestIndex - Determine search strategy */
1772 rtreeDisconnect, /* xDisconnect - Disconnect from a table */
1773 rtreeDestroy, /* xDestroy - Drop a table */
1774 rtreeOpen, /* xOpen - open a cursor */
1775 rtreeClose, /* xClose - close a cursor */
1776 geopolyFilter, /* xFilter - configure scan constraints */
1777 rtreeNext, /* xNext - advance a cursor */
1778 rtreeEof, /* xEof */
1779 geopolyColumn, /* xColumn - read data */
1780 rtreeRowid, /* xRowid - read data */
1781 geopolyUpdate, /* xUpdate - write data */
1782 rtreeBeginTransaction, /* xBegin - begin transaction */
1783 rtreeEndTransaction, /* xSync - sync transaction */
1784 rtreeEndTransaction, /* xCommit - commit transaction */
1785 rtreeEndTransaction, /* xRollback - rollback transaction */
1786 geopolyFindFunction, /* xFindFunction - function overloading */
1787 rtreeRename, /* xRename - rename the table */
1788 rtreeSavepoint, /* xSavepoint */
1789 0, /* xRelease */
1790 0, /* xRollbackTo */
1791 rtreeShadowName, /* xShadowName */
1792 rtreeIntegrity /* xIntegrity */
1793 };
1794
1795 static int sqlite3_geopoly_init(sqlite3 *db){
1796 int rc = SQLITE_OK;
1797 static const struct {
1798 void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
1799 signed char nArg;
1800 unsigned char bPure;
1801 const char *zName;
1802 } aFunc[] = {
1803 { geopolyAreaFunc, 1, 1, "geopoly_area" },
1804 { geopolyBlobFunc, 1, 1, "geopoly_blob" },
1805 { geopolyJsonFunc, 1, 1, "geopoly_json" },
1806 { geopolySvgFunc, -1, 1, "geopoly_svg" },
1807 { geopolyWithinFunc, 2, 1, "geopoly_within" },
1808 { geopolyContainsPointFunc, 3, 1, "geopoly_contains_point" },
1809 { geopolyOverlapFunc, 2, 1, "geopoly_overlap" },
1810 { geopolyDebugFunc, 1, 0, "geopoly_debug" },
1811 { geopolyBBoxFunc, 1, 1, "geopoly_bbox" },
1812 { geopolyXformFunc, 7, 1, "geopoly_xform" },
1813 { geopolyRegularFunc, 4, 1, "geopoly_regular" },
1814 { geopolyCcwFunc, 1, 1, "geopoly_ccw" },
1815 };
1816 static const struct {
1817 void (*xStep)(sqlite3_context*,int,sqlite3_value**);
1818 void (*xFinal)(sqlite3_context*);
1819 const char *zName;
1820 } aAgg[] = {
1821 { geopolyBBoxStep, geopolyBBoxFinal, "geopoly_group_bbox" },
1822 };
1823 unsigned int i;
1824 for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){
1825 int enc;
1826 if( aFunc[i].bPure ){
1827 enc = SQLITE_UTF8|SQLITE_DETERMINISTIC|SQLITE_INNOCUOUS;
1828 }else{
1829 enc = SQLITE_UTF8|SQLITE_DIRECTONLY;
1830 }
1831 rc = sqlite3_create_function(db, aFunc[i].zName, aFunc[i].nArg,
1832 enc, 0,
1833 aFunc[i].xFunc, 0, 0);
1834 }
1835 for(i=0; i<sizeof(aAgg)/sizeof(aAgg[0]) && rc==SQLITE_OK; i++){
1836 rc = sqlite3_create_function(db, aAgg[i].zName, 1,
1837 SQLITE_UTF8|SQLITE_DETERMINISTIC|SQLITE_INNOCUOUS, 0,
1838 0, aAgg[i].xStep, aAgg[i].xFinal);
1839 }
1840 if( rc==SQLITE_OK ){
1841 rc = sqlite3_create_module_v2(db, "geopoly", &geopolyModule, 0, 0);
1842 }
1843 return rc;
1844 }