| 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*)ⅈ |
| 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 |
} |