/ Check-in [666133e3]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add support for the Geopoly extension to the R-Tree extension. This also involves adding the SQLITE_INDEX_CONSTRAINT_FUNCTION capability to the xFindFunction method of the sqlite3_module object, and to the sqlite3_index_info.aConstraint.op field in the xBestIndex implementation of virtual tables.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 666133e32ca8e95807f8437dc8401bc93e2e6508ab8e6ae1e6031b7cee1584ae
User & Date: drh 2018-08-27 17:13:12
Context
2018-08-28
11:23
Fix a problem causing spurious SQLITE_CORRUPT errors when using the snapshot API to read from old database snapshots. check-in: 535155be user: dan tags: trunk
2018-08-27
17:13
Add support for the Geopoly extension to the R-Tree extension. This also involves adding the SQLITE_INDEX_CONSTRAINT_FUNCTION capability to the xFindFunction method of the sqlite3_module object, and to the sqlite3_index_info.aConstraint.op field in the xBestIndex implementation of virtual tables. check-in: 666133e3 user: drh tags: trunk
17:05
Minor changes to the visual01.txt test script. Closed-Leaf check-in: 4bc28eed user: drh tags: rtree-geopoly
2018-08-24
19:04
Set SQLITE_PTRSIZE to 4 when compiling with xlc on 32-bit AIX. check-in: d158e5b1 user: mistachkin tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to Makefile.in.

   346    346     $(TOP)/ext/fts3/fts3_unicode2.c \
   347    347     $(TOP)/ext/fts3/fts3_write.c
   348    348   SRC += \
   349    349     $(TOP)/ext/icu/sqliteicu.h \
   350    350     $(TOP)/ext/icu/icu.c
   351    351   SRC += \
   352    352     $(TOP)/ext/rtree/rtree.h \
   353         -  $(TOP)/ext/rtree/rtree.c
          353  +  $(TOP)/ext/rtree/rtree.c \
          354  +  $(TOP)/ext/rtree/geopoly.c
   354    355   SRC += \
   355    356     $(TOP)/ext/session/sqlite3session.c \
   356    357     $(TOP)/ext/session/sqlite3session.h
   357    358   SRC += \
   358    359     $(TOP)/ext/rbu/sqlite3rbu.h \
   359    360     $(TOP)/ext/rbu/sqlite3rbu.c
   360    361   SRC += \
................................................................................
   548    549     $(TOP)/ext/fts2/fts2_tokenizer.h
   549    550   EXTHDR += \
   550    551     $(TOP)/ext/fts3/fts3.h \
   551    552     $(TOP)/ext/fts3/fts3Int.h \
   552    553     $(TOP)/ext/fts3/fts3_hash.h \
   553    554     $(TOP)/ext/fts3/fts3_tokenizer.h
   554    555   EXTHDR += \
   555         -  $(TOP)/ext/rtree/rtree.h
          556  +  $(TOP)/ext/rtree/rtree.h \
          557  +  $(TOP)/ext/rtree/geopoly.c
   556    558   EXTHDR += \
   557    559     $(TOP)/ext/icu/sqliteicu.h
   558    560   EXTHDR += \
   559    561     $(TOP)/ext/rtree/sqlite3rtree.h
   560    562   
   561    563   # executables needed for testing
   562    564   #

Changes to Makefile.msc.

   334    334   
   335    335   # These are the "standard" SQLite compilation options used when compiling for
   336    336   # the Windows platform.
   337    337   #
   338    338   !IFNDEF OPT_FEATURE_FLAGS
   339    339   !IF $(MINIMAL_AMALGAMATION)==0
   340    340   OPT_FEATURE_FLAGS = $(OPT_FEATURE_FLAGS) -DSQLITE_ENABLE_FTS3=1
   341         -OPT_FEATURE_FLAGS = $(OPT_FEATURE_FLAGS) -DSQLITE_ENABLE_RTREE=1
          341  +OPT_FEATURE_FLAGS = $(OPT_FEATURE_FLAGS) -DSQLITE_ENABLE_RTREE=1 -DSQLITE_ENABLE_GEOPOLY=1
   342    342   !ENDIF
   343    343   OPT_FEATURE_FLAGS = $(OPT_FEATURE_FLAGS) -DSQLITE_ENABLE_COLUMN_METADATA=1
   344    344   !ENDIF
   345    345   
   346    346   # Should the session extension be enabled?  If so, add compilation options
   347    347   # to enable it.
   348    348   #
................................................................................
  1409   1409   SRC09 = \
  1410   1410     $(TOP)\ext\fts3\fts3.h \
  1411   1411     $(TOP)\ext\fts3\fts3Int.h \
  1412   1412     $(TOP)\ext\fts3\fts3_hash.h \
  1413   1413     $(TOP)\ext\fts3\fts3_tokenizer.h \
  1414   1414     $(TOP)\ext\icu\sqliteicu.h \
  1415   1415     $(TOP)\ext\rtree\rtree.h \
         1416  +  $(TOP)\ext\rtree\geopoly.c \
  1416   1417     $(TOP)\ext\rbu\sqlite3rbu.h \
  1417   1418     $(TOP)\ext\session\sqlite3session.h
  1418   1419   
  1419   1420   # Generated source code files
  1420   1421   #
  1421   1422   SRC10 = \
  1422   1423     opcodes.c \
................................................................................
  1583   1584     $(TOP)\ext\fts2\fts2_tokenizer.h
  1584   1585   EXTHDR = $(EXTHDR) \
  1585   1586     $(TOP)\ext\fts3\fts3.h \
  1586   1587     $(TOP)\ext\fts3\fts3Int.h \
  1587   1588     $(TOP)\ext\fts3\fts3_hash.h \
  1588   1589     $(TOP)\ext\fts3\fts3_tokenizer.h
  1589   1590   EXTHDR = $(EXTHDR) \
  1590         -  $(TOP)\ext\rtree\rtree.h
         1591  +  $(TOP)\ext\rtree\rtree.h \
         1592  +  $(TOP)\ext\rtree\geopoly.c
  1591   1593   EXTHDR = $(EXTHDR) \
  1592   1594     $(TOP)\ext\icu\sqliteicu.h
  1593   1595   EXTHDR = $(EXTHDR) \
  1594   1596     $(TOP)\ext\rtree\sqlite3rtree.h
  1595   1597   EXTHDR = $(EXTHDR) \
  1596   1598     $(TOP)\ext\session\sqlite3session.h
  1597   1599   

Changes to configure.

   907    907   enable_memsys5
   908    908   enable_memsys3
   909    909   enable_fts3
   910    910   enable_fts4
   911    911   enable_fts5
   912    912   enable_json1
   913    913   enable_update_limit
          914  +enable_geopoly
   914    915   enable_rtree
   915    916   enable_session
   916    917   enable_gcov
   917    918   '
   918    919         ac_precious_vars='build_alias
   919    920   host_alias
   920    921   target_alias
................................................................................
  1559   1560     --enable-memsys5        Enable MEMSYS5
  1560   1561     --enable-memsys3        Enable MEMSYS3
  1561   1562     --enable-fts3           Enable the FTS3 extension
  1562   1563     --enable-fts4           Enable the FTS4 extension
  1563   1564     --enable-fts5           Enable the FTS5 extension
  1564   1565     --enable-json1          Enable the JSON1 extension
  1565   1566     --enable-update-limit   Enable the UPDATE/DELETE LIMIT clause
         1567  +  --enable-geopoly        Enable the GEOPOLY extension
  1566   1568     --enable-rtree          Enable the RTREE extension
  1567   1569     --enable-session        Enable the SESSION extension
  1568   1570     --enable-gcov           Enable coverage testing using gcov
  1569   1571   
  1570   1572   Optional Packages:
  1571   1573     --with-PACKAGE[=ARG]    use PACKAGE [ARG=yes]
  1572   1574     --without-PACKAGE       do not use PACKAGE (same as --with-PACKAGE=no)
................................................................................
  3928   3930   { $as_echo "$as_me:${as_lineno-$LINENO}: checking the name lister ($NM) interface" >&5
  3929   3931   $as_echo_n "checking the name lister ($NM) interface... " >&6; }
  3930   3932   if ${lt_cv_nm_interface+:} false; then :
  3931   3933     $as_echo_n "(cached) " >&6
  3932   3934   else
  3933   3935     lt_cv_nm_interface="BSD nm"
  3934   3936     echo "int some_variable = 0;" > conftest.$ac_ext
  3935         -  (eval echo "\"\$as_me:3935: $ac_compile\"" >&5)
         3937  +  (eval echo "\"\$as_me:3937: $ac_compile\"" >&5)
  3936   3938     (eval "$ac_compile" 2>conftest.err)
  3937   3939     cat conftest.err >&5
  3938         -  (eval echo "\"\$as_me:3938: $NM \\\"conftest.$ac_objext\\\"\"" >&5)
         3940  +  (eval echo "\"\$as_me:3940: $NM \\\"conftest.$ac_objext\\\"\"" >&5)
  3939   3941     (eval "$NM \"conftest.$ac_objext\"" 2>conftest.err > conftest.out)
  3940   3942     cat conftest.err >&5
  3941         -  (eval echo "\"\$as_me:3941: output\"" >&5)
         3943  +  (eval echo "\"\$as_me:3943: output\"" >&5)
  3942   3944     cat conftest.out >&5
  3943   3945     if $GREP 'External.*some_variable' conftest.out > /dev/null; then
  3944   3946       lt_cv_nm_interface="MS dumpbin"
  3945   3947     fi
  3946   3948     rm -f conftest*
  3947   3949   fi
  3948   3950   { $as_echo "$as_me:${as_lineno-$LINENO}: result: $lt_cv_nm_interface" >&5
................................................................................
  5140   5142   	;;
  5141   5143       esac
  5142   5144     fi
  5143   5145     rm -rf conftest*
  5144   5146     ;;
  5145   5147   *-*-irix6*)
  5146   5148     # Find out which ABI we are using.
  5147         -  echo '#line 5147 "configure"' > conftest.$ac_ext
         5149  +  echo '#line 5149 "configure"' > conftest.$ac_ext
  5148   5150     if { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_compile\""; } >&5
  5149   5151     (eval $ac_compile) 2>&5
  5150   5152     ac_status=$?
  5151   5153     $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
  5152   5154     test $ac_status = 0; }; then
  5153   5155       if test "$lt_cv_prog_gnu_ld" = yes; then
  5154   5156         case `/usr/bin/file conftest.$ac_objext` in
................................................................................
  6665   6667      # Note that $ac_compile itself does not contain backslashes and begins
  6666   6668      # with a dollar sign (not a hyphen), so the echo should work correctly.
  6667   6669      # The option is referenced via a variable to avoid confusing sed.
  6668   6670      lt_compile=`echo "$ac_compile" | $SED \
  6669   6671      -e 's:.*FLAGS}\{0,1\} :&$lt_compiler_flag :; t' \
  6670   6672      -e 's: [^ ]*conftest\.: $lt_compiler_flag&:; t' \
  6671   6673      -e 's:$: $lt_compiler_flag:'`
  6672         -   (eval echo "\"\$as_me:6672: $lt_compile\"" >&5)
         6674  +   (eval echo "\"\$as_me:6674: $lt_compile\"" >&5)
  6673   6675      (eval "$lt_compile" 2>conftest.err)
  6674   6676      ac_status=$?
  6675   6677      cat conftest.err >&5
  6676         -   echo "$as_me:6676: \$? = $ac_status" >&5
         6678  +   echo "$as_me:6678: \$? = $ac_status" >&5
  6677   6679      if (exit $ac_status) && test -s "$ac_outfile"; then
  6678   6680        # The compiler can only warn and ignore the option if not recognized
  6679   6681        # So say no if there are warnings other than the usual output.
  6680   6682        $ECHO "X$_lt_compiler_boilerplate" | $Xsed -e '/^$/d' >conftest.exp
  6681   6683        $SED '/^$/d; /^ *+/d' conftest.err >conftest.er2
  6682   6684        if test ! -s conftest.er2 || diff conftest.exp conftest.er2 >/dev/null; then
  6683   6685          lt_cv_prog_compiler_rtti_exceptions=yes
................................................................................
  7004   7006      # Note that $ac_compile itself does not contain backslashes and begins
  7005   7007      # with a dollar sign (not a hyphen), so the echo should work correctly.
  7006   7008      # The option is referenced via a variable to avoid confusing sed.
  7007   7009      lt_compile=`echo "$ac_compile" | $SED \
  7008   7010      -e 's:.*FLAGS}\{0,1\} :&$lt_compiler_flag :; t' \
  7009   7011      -e 's: [^ ]*conftest\.: $lt_compiler_flag&:; t' \
  7010   7012      -e 's:$: $lt_compiler_flag:'`
  7011         -   (eval echo "\"\$as_me:7011: $lt_compile\"" >&5)
         7013  +   (eval echo "\"\$as_me:7013: $lt_compile\"" >&5)
  7012   7014      (eval "$lt_compile" 2>conftest.err)
  7013   7015      ac_status=$?
  7014   7016      cat conftest.err >&5
  7015         -   echo "$as_me:7015: \$? = $ac_status" >&5
         7017  +   echo "$as_me:7017: \$? = $ac_status" >&5
  7016   7018      if (exit $ac_status) && test -s "$ac_outfile"; then
  7017   7019        # The compiler can only warn and ignore the option if not recognized
  7018   7020        # So say no if there are warnings other than the usual output.
  7019   7021        $ECHO "X$_lt_compiler_boilerplate" | $Xsed -e '/^$/d' >conftest.exp
  7020   7022        $SED '/^$/d; /^ *+/d' conftest.err >conftest.er2
  7021   7023        if test ! -s conftest.er2 || diff conftest.exp conftest.er2 >/dev/null; then
  7022   7024          lt_cv_prog_compiler_pic_works=yes
................................................................................
  7109   7111      # (2) before a word containing "conftest.", or (3) at the end.
  7110   7112      # Note that $ac_compile itself does not contain backslashes and begins
  7111   7113      # with a dollar sign (not a hyphen), so the echo should work correctly.
  7112   7114      lt_compile=`echo "$ac_compile" | $SED \
  7113   7115      -e 's:.*FLAGS}\{0,1\} :&$lt_compiler_flag :; t' \
  7114   7116      -e 's: [^ ]*conftest\.: $lt_compiler_flag&:; t' \
  7115   7117      -e 's:$: $lt_compiler_flag:'`
  7116         -   (eval echo "\"\$as_me:7116: $lt_compile\"" >&5)
         7118  +   (eval echo "\"\$as_me:7118: $lt_compile\"" >&5)
  7117   7119      (eval "$lt_compile" 2>out/conftest.err)
  7118   7120      ac_status=$?
  7119   7121      cat out/conftest.err >&5
  7120         -   echo "$as_me:7120: \$? = $ac_status" >&5
         7122  +   echo "$as_me:7122: \$? = $ac_status" >&5
  7121   7123      if (exit $ac_status) && test -s out/conftest2.$ac_objext
  7122   7124      then
  7123   7125        # The compiler can only warn and ignore the option if not recognized
  7124   7126        # So say no if there are warnings
  7125   7127        $ECHO "X$_lt_compiler_boilerplate" | $Xsed -e '/^$/d' > out/conftest.exp
  7126   7128        $SED '/^$/d; /^ *+/d' out/conftest.err >out/conftest.er2
  7127   7129        if test ! -s out/conftest.er2 || diff out/conftest.exp out/conftest.er2 >/dev/null; then
................................................................................
  7164   7166      # (2) before a word containing "conftest.", or (3) at the end.
  7165   7167      # Note that $ac_compile itself does not contain backslashes and begins
  7166   7168      # with a dollar sign (not a hyphen), so the echo should work correctly.
  7167   7169      lt_compile=`echo "$ac_compile" | $SED \
  7168   7170      -e 's:.*FLAGS}\{0,1\} :&$lt_compiler_flag :; t' \
  7169   7171      -e 's: [^ ]*conftest\.: $lt_compiler_flag&:; t' \
  7170   7172      -e 's:$: $lt_compiler_flag:'`
  7171         -   (eval echo "\"\$as_me:7171: $lt_compile\"" >&5)
         7173  +   (eval echo "\"\$as_me:7173: $lt_compile\"" >&5)
  7172   7174      (eval "$lt_compile" 2>out/conftest.err)
  7173   7175      ac_status=$?
  7174   7176      cat out/conftest.err >&5
  7175         -   echo "$as_me:7175: \$? = $ac_status" >&5
         7177  +   echo "$as_me:7177: \$? = $ac_status" >&5
  7176   7178      if (exit $ac_status) && test -s out/conftest2.$ac_objext
  7177   7179      then
  7178   7180        # The compiler can only warn and ignore the option if not recognized
  7179   7181        # So say no if there are warnings
  7180   7182        $ECHO "X$_lt_compiler_boilerplate" | $Xsed -e '/^$/d' > out/conftest.exp
  7181   7183        $SED '/^$/d; /^ *+/d' out/conftest.err >out/conftest.er2
  7182   7184        if test ! -s out/conftest.er2 || diff out/conftest.exp out/conftest.er2 >/dev/null; then
................................................................................
  9544   9546   else
  9545   9547     	  if test "$cross_compiling" = yes; then :
  9546   9548     lt_cv_dlopen_self=cross
  9547   9549   else
  9548   9550     lt_dlunknown=0; lt_dlno_uscore=1; lt_dlneed_uscore=2
  9549   9551     lt_status=$lt_dlunknown
  9550   9552     cat > conftest.$ac_ext <<_LT_EOF
  9551         -#line 9551 "configure"
         9553  +#line 9553 "configure"
  9552   9554   #include "confdefs.h"
  9553   9555   
  9554   9556   #if HAVE_DLFCN_H
  9555   9557   #include <dlfcn.h>
  9556   9558   #endif
  9557   9559   
  9558   9560   #include <stdio.h>
................................................................................
  9640   9642   else
  9641   9643     	  if test "$cross_compiling" = yes; then :
  9642   9644     lt_cv_dlopen_self_static=cross
  9643   9645   else
  9644   9646     lt_dlunknown=0; lt_dlno_uscore=1; lt_dlneed_uscore=2
  9645   9647     lt_status=$lt_dlunknown
  9646   9648     cat > conftest.$ac_ext <<_LT_EOF
  9647         -#line 9647 "configure"
         9649  +#line 9649 "configure"
  9648   9650   #include "confdefs.h"
  9649   9651   
  9650   9652   #if HAVE_DLFCN_H
  9651   9653   #include <dlfcn.h>
  9652   9654   #endif
  9653   9655   
  9654   9656   #include <stdio.h>
................................................................................
 11605  11607   if test "${enable_update_limit+set}" = set; then :
 11606  11608     enableval=$enable_update_limit;
 11607  11609   fi
 11608  11610   
 11609  11611   if test "${enable_udlimit}" = "yes" ; then
 11610  11612     OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_UPDATE_DELETE_LIMIT"
 11611  11613   fi
        11614  +
        11615  +#########
        11616  +# See whether we should enable GEOPOLY
        11617  +# Check whether --enable-geopoly was given.
        11618  +if test "${enable_geopoly+set}" = set; then :
        11619  +  enableval=$enable_geopoly; enable_geopoly=yes
        11620  +else
        11621  +  enable_geopoly=no
        11622  +fi
        11623  +
        11624  +if test "${enable_geopoly}" = "yes" ; then
        11625  +  OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_GEOPOLY"
        11626  +  enable_rtree=yes
        11627  +fi
 11612  11628   
 11613  11629   #########
 11614  11630   # See whether we should enable RTREE
 11615  11631   # Check whether --enable-rtree was given.
 11616  11632   if test "${enable_rtree+set}" = set; then :
 11617  11633     enableval=$enable_rtree;
 11618  11634   fi

Changes to configure.ac.

   644    644   # See whether we should enable the LIMIT clause on UPDATE and DELETE
   645    645   # statements.
   646    646   AC_ARG_ENABLE(update-limit, AC_HELP_STRING([--enable-update-limit],
   647    647         [Enable the UPDATE/DELETE LIMIT clause]))
   648    648   if test "${enable_udlimit}" = "yes" ; then
   649    649     OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_UPDATE_DELETE_LIMIT"
   650    650   fi
          651  +
          652  +#########
          653  +# See whether we should enable GEOPOLY
          654  +AC_ARG_ENABLE(geopoly, AC_HELP_STRING([--enable-geopoly],
          655  +      [Enable the GEOPOLY extension]),
          656  +      [enable_geopoly=yes],[enable_geopoly=no])
          657  +if test "${enable_geopoly}" = "yes" ; then
          658  +  OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_GEOPOLY"
          659  +  enable_rtree=yes
          660  +fi
   651    661   
   652    662   #########
   653    663   # See whether we should enable RTREE
   654    664   AC_ARG_ENABLE(rtree, AC_HELP_STRING([--enable-rtree],
   655    665         [Enable the RTREE extension]))
   656    666   if test "${enable_rtree}" = "yes" ; then
   657    667     OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_RTREE"

Added ext/rtree/geopoly.c.

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

Changes to ext/rtree/rtree.c.

  2889   2889     }
  2890   2890     return rc;
  2891   2891   }
  2892   2892   
  2893   2893   /*
  2894   2894   ** Select a currently unused rowid for a new r-tree record.
  2895   2895   */
  2896         -static int newRowid(Rtree *pRtree, i64 *piRowid){
         2896  +static int rtreeNewRowid(Rtree *pRtree, i64 *piRowid){
  2897   2897     int rc;
  2898   2898     sqlite3_bind_null(pRtree->pWriteRowid, 1);
  2899   2899     sqlite3_bind_null(pRtree->pWriteRowid, 2);
  2900   2900     sqlite3_step(pRtree->pWriteRowid);
  2901   2901     rc = sqlite3_reset(pRtree->pWriteRowid);
  2902   2902     *piRowid = sqlite3_last_insert_rowid(pRtree->db);
  2903   2903     return rc;
................................................................................
  3176   3176     */
  3177   3177     if( rc==SQLITE_OK && nData>1 ){
  3178   3178       /* Insert the new record into the r-tree */
  3179   3179       RtreeNode *pLeaf = 0;
  3180   3180   
  3181   3181       /* Figure out the rowid of the new row. */
  3182   3182       if( bHaveRowid==0 ){
  3183         -      rc = newRowid(pRtree, &cell.iRowid);
         3183  +      rc = rtreeNewRowid(pRtree, &cell.iRowid);
  3184   3184       }
  3185   3185       *pRowid = cell.iRowid;
  3186   3186   
  3187   3187       if( rc==SQLITE_OK ){
  3188   3188         rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
  3189   3189       }
  3190   3190       if( rc==SQLITE_OK ){
................................................................................
  4218   4218       }else{
  4219   4219         sqlite3_result_error_code(ctx, rc);
  4220   4220       }
  4221   4221       sqlite3_free(zReport);
  4222   4222     }
  4223   4223   }
  4224   4224   
         4225  +/* Conditionally include the geopoly code */
         4226  +#ifdef SQLITE_ENABLE_GEOPOLY
         4227  +# include "geopoly.c"
         4228  +#endif
  4225   4229   
  4226   4230   /*
  4227   4231   ** Register the r-tree module with database handle db. This creates the
  4228   4232   ** virtual table module "rtree" and the debugging/analysis scalar 
  4229   4233   ** function "rtreenode".
  4230   4234   */
  4231   4235   int sqlite3RtreeInit(sqlite3 *db){
................................................................................
  4247   4251   #endif
  4248   4252       rc = sqlite3_create_module_v2(db, "rtree", &rtreeModule, c, 0);
  4249   4253     }
  4250   4254     if( rc==SQLITE_OK ){
  4251   4255       void *c = (void *)RTREE_COORD_INT32;
  4252   4256       rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0);
  4253   4257     }
         4258  +#ifdef SQLITE_ENABLE_GEOPOLY
         4259  +  if( rc==SQLITE_OK ){
         4260  +    rc = sqlite3_geopoly_init(db);
         4261  +  }
         4262  +#endif
  4254   4263   
  4255   4264     return rc;
  4256   4265   }
  4257   4266   
  4258   4267   /*
  4259   4268   ** This routine deletes the RtreeGeomCallback object that was attached
  4260   4269   ** one of the SQL functions create by sqlite3_rtree_geometry_callback()

Added ext/rtree/visual01.txt.

            1  +#!sqlite3
            2  +#
            3  +# This is a visual test case for the geopoly virtual table.
            4  +#
            5  +# Run this script in the sqlite3 CLI, and redirect output into an
            6  +# HTML file.  This display the HTML in a webbrowser.
            7  +#
            8  +
            9  +/* Test data.
           10  +** Lots of shapes to be displayed over a 1000x800 canvas.
           11  +*/
           12  +CREATE TEMP TABLE basis(name TEXT, jshape TEXT);
           13  +INSERT INTO basis(name,jshape) VALUES
           14  +  ('box-20','[[0,0],[20,0],[20,20],[0,20],[0,0]]'),
           15  +  ('house-70','[[0,0],[50,0],[50,50],[25,70],[0,50],[0,0]]'),
           16  +  ('line-40','[[0,0],[40,0],[40,5],[0,5],[0,0]]'),
           17  +  ('line-80','[[0,0],[80,0],[80,7],[0,7],[0,0]]'),
           18  +  ('arrow-50','[[0,0],[25,25],[0,50],[15,25],[0,0]]'),
           19  +  ('triangle-30','[[0,0],[30,0],[15,30],[0,0]]'),
           20  +  ('angle-30','[[0,0],[30,0],[30,30],[26,30],[26,4],[0,4],[0,0]]'),
           21  +  ('star-10','[[1,0],[5,2],[9,0],[7,4],[10,8],[7,7],[5,10],[3,7],[0,8],[3,4],[1,0]]');
           22  +CREATE TEMP TABLE xform(A,B,C,D,clr);
           23  +INSERT INTO xform(A,B,clr) VALUES
           24  +  (1,0,'black'),
           25  +  (0.707,0.707,'blue'),
           26  +  (0.5,0.866,'red'),
           27  +  (-0.866,0.5,'green');
           28  +CREATE TEMP TABLE xyoff(id1,id2,xoff,yoff,PRIMARY KEY(id1,id2,xoff,yoff))
           29  +  WITHOUT ROWID;
           30  +INSERT INTO xyoff VALUES(1,1,811,659);
           31  +INSERT INTO xyoff VALUES(1,1,235,550);
           32  +INSERT INTO xyoff VALUES(1,1,481,620);
           33  +INSERT INTO xyoff VALUES(1,1,106,494);
           34  +INSERT INTO xyoff VALUES(1,1,487,106);
           35  +INSERT INTO xyoff VALUES(1,1,817,595);
           36  +INSERT INTO xyoff VALUES(1,1,240,504);
           37  +INSERT INTO xyoff VALUES(1,1,806,457);
           38  +INSERT INTO xyoff VALUES(1,1,608,107);
           39  +INSERT INTO xyoff VALUES(1,1,768,662);
           40  +INSERT INTO xyoff VALUES(1,2,808,528);
           41  +INSERT INTO xyoff VALUES(1,2,768,528);
           42  +INSERT INTO xyoff VALUES(1,2,771,171);
           43  +INSERT INTO xyoff VALUES(1,2,275,671);
           44  +INSERT INTO xyoff VALUES(1,2,326,336);
           45  +INSERT INTO xyoff VALUES(1,2,690,688);
           46  +INSERT INTO xyoff VALUES(1,2,597,239);
           47  +INSERT INTO xyoff VALUES(1,2,317,528);
           48  +INSERT INTO xyoff VALUES(1,2,366,223);
           49  +INSERT INTO xyoff VALUES(1,2,621,154);
           50  +INSERT INTO xyoff VALUES(1,3,829,469);
           51  +INSERT INTO xyoff VALUES(1,3,794,322);
           52  +INSERT INTO xyoff VALUES(1,3,358,387);
           53  +INSERT INTO xyoff VALUES(1,3,184,444);
           54  +INSERT INTO xyoff VALUES(1,3,729,500);
           55  +INSERT INTO xyoff VALUES(1,3,333,523);
           56  +INSERT INTO xyoff VALUES(1,3,117,595);
           57  +INSERT INTO xyoff VALUES(1,3,496,201);
           58  +INSERT INTO xyoff VALUES(1,3,818,601);
           59  +INSERT INTO xyoff VALUES(1,3,541,343);
           60  +INSERT INTO xyoff VALUES(1,4,603,248);
           61  +INSERT INTO xyoff VALUES(1,4,761,649);
           62  +INSERT INTO xyoff VALUES(1,4,611,181);
           63  +INSERT INTO xyoff VALUES(1,4,607,233);
           64  +INSERT INTO xyoff VALUES(1,4,860,206);
           65  +INSERT INTO xyoff VALUES(1,4,310,231);
           66  +INSERT INTO xyoff VALUES(1,4,727,539);
           67  +INSERT INTO xyoff VALUES(1,4,660,661);
           68  +INSERT INTO xyoff VALUES(1,4,403,133);
           69  +INSERT INTO xyoff VALUES(1,4,619,331);
           70  +INSERT INTO xyoff VALUES(2,1,712,578);
           71  +INSERT INTO xyoff VALUES(2,1,567,313);
           72  +INSERT INTO xyoff VALUES(2,1,231,423);
           73  +INSERT INTO xyoff VALUES(2,1,490,175);
           74  +INSERT INTO xyoff VALUES(2,1,898,353);
           75  +INSERT INTO xyoff VALUES(2,1,589,483);
           76  +INSERT INTO xyoff VALUES(2,1,188,462);
           77  +INSERT INTO xyoff VALUES(2,1,720,106);
           78  +INSERT INTO xyoff VALUES(2,1,793,380);
           79  +INSERT INTO xyoff VALUES(2,1,154,396);
           80  +INSERT INTO xyoff VALUES(2,2,324,218);
           81  +INSERT INTO xyoff VALUES(2,2,120,327);
           82  +INSERT INTO xyoff VALUES(2,2,655,133);
           83  +INSERT INTO xyoff VALUES(2,2,516,603);
           84  +INSERT INTO xyoff VALUES(2,2,529,572);
           85  +INSERT INTO xyoff VALUES(2,2,481,212);
           86  +INSERT INTO xyoff VALUES(2,2,802,107);
           87  +INSERT INTO xyoff VALUES(2,2,234,509);
           88  +INSERT INTO xyoff VALUES(2,2,501,269);
           89  +INSERT INTO xyoff VALUES(2,2,349,553);
           90  +INSERT INTO xyoff VALUES(2,3,495,685);
           91  +INSERT INTO xyoff VALUES(2,3,897,372);
           92  +INSERT INTO xyoff VALUES(2,3,350,681);
           93  +INSERT INTO xyoff VALUES(2,3,832,257);
           94  +INSERT INTO xyoff VALUES(2,3,778,149);
           95  +INSERT INTO xyoff VALUES(2,3,683,426);
           96  +INSERT INTO xyoff VALUES(2,3,693,217);
           97  +INSERT INTO xyoff VALUES(2,3,746,317);
           98  +INSERT INTO xyoff VALUES(2,3,805,369);
           99  +INSERT INTO xyoff VALUES(2,3,336,585);
          100  +INSERT INTO xyoff VALUES(2,4,890,255);
          101  +INSERT INTO xyoff VALUES(2,4,556,565);
          102  +INSERT INTO xyoff VALUES(2,4,865,555);
          103  +INSERT INTO xyoff VALUES(2,4,230,293);
          104  +INSERT INTO xyoff VALUES(2,4,247,251);
          105  +INSERT INTO xyoff VALUES(2,4,730,563);
          106  +INSERT INTO xyoff VALUES(2,4,318,282);
          107  +INSERT INTO xyoff VALUES(2,4,220,431);
          108  +INSERT INTO xyoff VALUES(2,4,828,336);
          109  +INSERT INTO xyoff VALUES(2,4,278,525);
          110  +INSERT INTO xyoff VALUES(3,1,324,656);
          111  +INSERT INTO xyoff VALUES(3,1,625,362);
          112  +INSERT INTO xyoff VALUES(3,1,155,570);
          113  +INSERT INTO xyoff VALUES(3,1,267,433);
          114  +INSERT INTO xyoff VALUES(3,1,599,121);
          115  +INSERT INTO xyoff VALUES(3,1,873,498);
          116  +INSERT INTO xyoff VALUES(3,1,789,520);
          117  +INSERT INTO xyoff VALUES(3,1,656,378);
          118  +INSERT INTO xyoff VALUES(3,1,831,601);
          119  +INSERT INTO xyoff VALUES(3,1,256,471);
          120  +INSERT INTO xyoff VALUES(3,2,332,258);
          121  +INSERT INTO xyoff VALUES(3,2,305,463);
          122  +INSERT INTO xyoff VALUES(3,2,796,341);
          123  +INSERT INTO xyoff VALUES(3,2,830,229);
          124  +INSERT INTO xyoff VALUES(3,2,413,271);
          125  +INSERT INTO xyoff VALUES(3,2,269,140);
          126  +INSERT INTO xyoff VALUES(3,2,628,441);
          127  +INSERT INTO xyoff VALUES(3,2,747,643);
          128  +INSERT INTO xyoff VALUES(3,2,584,435);
          129  +INSERT INTO xyoff VALUES(3,2,784,314);
          130  +INSERT INTO xyoff VALUES(3,3,722,233);
          131  +INSERT INTO xyoff VALUES(3,3,815,421);
          132  +INSERT INTO xyoff VALUES(3,3,401,267);
          133  +INSERT INTO xyoff VALUES(3,3,451,650);
          134  +INSERT INTO xyoff VALUES(3,3,329,485);
          135  +INSERT INTO xyoff VALUES(3,3,878,370);
          136  +INSERT INTO xyoff VALUES(3,3,162,616);
          137  +INSERT INTO xyoff VALUES(3,3,844,183);
          138  +INSERT INTO xyoff VALUES(3,3,161,216);
          139  +INSERT INTO xyoff VALUES(3,3,176,676);
          140  +INSERT INTO xyoff VALUES(3,4,780,128);
          141  +INSERT INTO xyoff VALUES(3,4,566,121);
          142  +INSERT INTO xyoff VALUES(3,4,646,120);
          143  +INSERT INTO xyoff VALUES(3,4,223,557);
          144  +INSERT INTO xyoff VALUES(3,4,251,117);
          145  +INSERT INTO xyoff VALUES(3,4,139,209);
          146  +INSERT INTO xyoff VALUES(3,4,813,597);
          147  +INSERT INTO xyoff VALUES(3,4,454,538);
          148  +INSERT INTO xyoff VALUES(3,4,616,198);
          149  +INSERT INTO xyoff VALUES(3,4,210,159);
          150  +INSERT INTO xyoff VALUES(4,1,208,415);
          151  +INSERT INTO xyoff VALUES(4,1,326,665);
          152  +INSERT INTO xyoff VALUES(4,1,612,133);
          153  +INSERT INTO xyoff VALUES(4,1,537,513);
          154  +INSERT INTO xyoff VALUES(4,1,638,438);
          155  +INSERT INTO xyoff VALUES(4,1,808,269);
          156  +INSERT INTO xyoff VALUES(4,1,552,121);
          157  +INSERT INTO xyoff VALUES(4,1,100,189);
          158  +INSERT INTO xyoff VALUES(4,1,643,664);
          159  +INSERT INTO xyoff VALUES(4,1,726,378);
          160  +INSERT INTO xyoff VALUES(4,2,478,409);
          161  +INSERT INTO xyoff VALUES(4,2,497,507);
          162  +INSERT INTO xyoff VALUES(4,2,233,148);
          163  +INSERT INTO xyoff VALUES(4,2,587,237);
          164  +INSERT INTO xyoff VALUES(4,2,604,166);
          165  +INSERT INTO xyoff VALUES(4,2,165,455);
          166  +INSERT INTO xyoff VALUES(4,2,320,258);
          167  +INSERT INTO xyoff VALUES(4,2,353,496);
          168  +INSERT INTO xyoff VALUES(4,2,347,495);
          169  +INSERT INTO xyoff VALUES(4,2,166,622);
          170  +INSERT INTO xyoff VALUES(4,3,461,332);
          171  +INSERT INTO xyoff VALUES(4,3,685,278);
          172  +INSERT INTO xyoff VALUES(4,3,427,594);
          173  +INSERT INTO xyoff VALUES(4,3,467,346);
          174  +INSERT INTO xyoff VALUES(4,3,125,548);
          175  +INSERT INTO xyoff VALUES(4,3,597,680);
          176  +INSERT INTO xyoff VALUES(4,3,820,445);
          177  +INSERT INTO xyoff VALUES(4,3,144,330);
          178  +INSERT INTO xyoff VALUES(4,3,557,434);
          179  +INSERT INTO xyoff VALUES(4,3,254,315);
          180  +INSERT INTO xyoff VALUES(4,4,157,339);
          181  +INSERT INTO xyoff VALUES(4,4,249,220);
          182  +INSERT INTO xyoff VALUES(4,4,391,323);
          183  +INSERT INTO xyoff VALUES(4,4,589,429);
          184  +INSERT INTO xyoff VALUES(4,4,859,592);
          185  +INSERT INTO xyoff VALUES(4,4,337,680);
          186  +INSERT INTO xyoff VALUES(4,4,410,288);
          187  +INSERT INTO xyoff VALUES(4,4,636,596);
          188  +INSERT INTO xyoff VALUES(4,4,734,433);
          189  +INSERT INTO xyoff VALUES(4,4,559,549);
          190  +INSERT INTO xyoff VALUES(5,1,549,607);
          191  +INSERT INTO xyoff VALUES(5,1,584,498);
          192  +INSERT INTO xyoff VALUES(5,1,699,116);
          193  +INSERT INTO xyoff VALUES(5,1,525,524);
          194  +INSERT INTO xyoff VALUES(5,1,304,667);
          195  +INSERT INTO xyoff VALUES(5,1,302,232);
          196  +INSERT INTO xyoff VALUES(5,1,403,149);
          197  +INSERT INTO xyoff VALUES(5,1,824,403);
          198  +INSERT INTO xyoff VALUES(5,1,697,203);
          199  +INSERT INTO xyoff VALUES(5,1,293,689);
          200  +INSERT INTO xyoff VALUES(5,2,199,275);
          201  +INSERT INTO xyoff VALUES(5,2,395,393);
          202  +INSERT INTO xyoff VALUES(5,2,657,642);
          203  +INSERT INTO xyoff VALUES(5,2,200,655);
          204  +INSERT INTO xyoff VALUES(5,2,882,234);
          205  +INSERT INTO xyoff VALUES(5,2,483,565);
          206  +INSERT INTO xyoff VALUES(5,2,755,640);
          207  +INSERT INTO xyoff VALUES(5,2,810,305);
          208  +INSERT INTO xyoff VALUES(5,2,731,655);
          209  +INSERT INTO xyoff VALUES(5,2,466,690);
          210  +INSERT INTO xyoff VALUES(5,3,563,584);
          211  +INSERT INTO xyoff VALUES(5,3,491,117);
          212  +INSERT INTO xyoff VALUES(5,3,779,292);
          213  +INSERT INTO xyoff VALUES(5,3,375,637);
          214  +INSERT INTO xyoff VALUES(5,3,253,553);
          215  +INSERT INTO xyoff VALUES(5,3,797,514);
          216  +INSERT INTO xyoff VALUES(5,3,229,480);
          217  +INSERT INTO xyoff VALUES(5,3,257,194);
          218  +INSERT INTO xyoff VALUES(5,3,449,555);
          219  +INSERT INTO xyoff VALUES(5,3,849,630);
          220  +INSERT INTO xyoff VALUES(5,4,329,286);
          221  +INSERT INTO xyoff VALUES(5,4,640,197);
          222  +INSERT INTO xyoff VALUES(5,4,104,150);
          223  +INSERT INTO xyoff VALUES(5,4,438,272);
          224  +INSERT INTO xyoff VALUES(5,4,773,226);
          225  +INSERT INTO xyoff VALUES(5,4,441,650);
          226  +INSERT INTO xyoff VALUES(5,4,242,340);
          227  +INSERT INTO xyoff VALUES(5,4,301,435);
          228  +INSERT INTO xyoff VALUES(5,4,171,397);
          229  +INSERT INTO xyoff VALUES(5,4,541,619);
          230  +INSERT INTO xyoff VALUES(6,1,651,301);
          231  +INSERT INTO xyoff VALUES(6,1,637,137);
          232  +INSERT INTO xyoff VALUES(6,1,765,643);
          233  +INSERT INTO xyoff VALUES(6,1,173,296);
          234  +INSERT INTO xyoff VALUES(6,1,263,192);
          235  +INSERT INTO xyoff VALUES(6,1,791,302);
          236  +INSERT INTO xyoff VALUES(6,1,860,601);
          237  +INSERT INTO xyoff VALUES(6,1,780,445);
          238  +INSERT INTO xyoff VALUES(6,1,462,214);
          239  +INSERT INTO xyoff VALUES(6,1,802,207);
          240  +INSERT INTO xyoff VALUES(6,2,811,685);
          241  +INSERT INTO xyoff VALUES(6,2,533,531);
          242  +INSERT INTO xyoff VALUES(6,2,390,614);
          243  +INSERT INTO xyoff VALUES(6,2,260,580);
          244  +INSERT INTO xyoff VALUES(6,2,116,377);
          245  +INSERT INTO xyoff VALUES(6,2,860,458);
          246  +INSERT INTO xyoff VALUES(6,2,438,590);
          247  +INSERT INTO xyoff VALUES(6,2,604,562);
          248  +INSERT INTO xyoff VALUES(6,2,241,242);
          249  +INSERT INTO xyoff VALUES(6,2,667,298);
          250  +INSERT INTO xyoff VALUES(6,3,787,698);
          251  +INSERT INTO xyoff VALUES(6,3,868,521);
          252  +INSERT INTO xyoff VALUES(6,3,412,587);
          253  +INSERT INTO xyoff VALUES(6,3,640,131);
          254  +INSERT INTO xyoff VALUES(6,3,748,410);
          255  +INSERT INTO xyoff VALUES(6,3,257,244);
          256  +INSERT INTO xyoff VALUES(6,3,411,195);
          257  +INSERT INTO xyoff VALUES(6,3,464,356);
          258  +INSERT INTO xyoff VALUES(6,3,157,339);
          259  +INSERT INTO xyoff VALUES(6,3,434,505);
          260  +INSERT INTO xyoff VALUES(6,4,480,671);
          261  +INSERT INTO xyoff VALUES(6,4,519,228);
          262  +INSERT INTO xyoff VALUES(6,4,404,513);
          263  +INSERT INTO xyoff VALUES(6,4,120,538);
          264  +INSERT INTO xyoff VALUES(6,4,403,663);
          265  +INSERT INTO xyoff VALUES(6,4,477,677);
          266  +INSERT INTO xyoff VALUES(6,4,690,154);
          267  +INSERT INTO xyoff VALUES(6,4,606,498);
          268  +INSERT INTO xyoff VALUES(6,4,430,665);
          269  +INSERT INTO xyoff VALUES(6,4,499,273);
          270  +INSERT INTO xyoff VALUES(7,1,118,526);
          271  +INSERT INTO xyoff VALUES(7,1,817,522);
          272  +INSERT INTO xyoff VALUES(7,1,388,638);
          273  +INSERT INTO xyoff VALUES(7,1,181,265);
          274  +INSERT INTO xyoff VALUES(7,1,442,332);
          275  +INSERT INTO xyoff VALUES(7,1,475,282);
          276  +INSERT INTO xyoff VALUES(7,1,722,633);
          277  +INSERT INTO xyoff VALUES(7,1,104,394);
          278  +INSERT INTO xyoff VALUES(7,1,631,262);
          279  +INSERT INTO xyoff VALUES(7,1,372,392);
          280  +INSERT INTO xyoff VALUES(7,2,600,413);
          281  +INSERT INTO xyoff VALUES(7,2,386,223);
          282  +INSERT INTO xyoff VALUES(7,2,839,174);
          283  +INSERT INTO xyoff VALUES(7,2,293,410);
          284  +INSERT INTO xyoff VALUES(7,2,281,391);
          285  +INSERT INTO xyoff VALUES(7,2,859,387);
          286  +INSERT INTO xyoff VALUES(7,2,478,347);
          287  +INSERT INTO xyoff VALUES(7,2,646,690);
          288  +INSERT INTO xyoff VALUES(7,2,713,234);
          289  +INSERT INTO xyoff VALUES(7,2,199,588);
          290  +INSERT INTO xyoff VALUES(7,3,389,256);
          291  +INSERT INTO xyoff VALUES(7,3,349,542);
          292  +INSERT INTO xyoff VALUES(7,3,363,345);
          293  +INSERT INTO xyoff VALUES(7,3,751,302);
          294  +INSERT INTO xyoff VALUES(7,3,423,386);
          295  +INSERT INTO xyoff VALUES(7,3,267,444);
          296  +INSERT INTO xyoff VALUES(7,3,243,182);
          297  +INSERT INTO xyoff VALUES(7,3,453,658);
          298  +INSERT INTO xyoff VALUES(7,3,126,345);
          299  +INSERT INTO xyoff VALUES(7,3,120,472);
          300  +INSERT INTO xyoff VALUES(7,4,359,654);
          301  +INSERT INTO xyoff VALUES(7,4,339,516);
          302  +INSERT INTO xyoff VALUES(7,4,710,452);
          303  +INSERT INTO xyoff VALUES(7,4,810,560);
          304  +INSERT INTO xyoff VALUES(7,4,644,692);
          305  +INSERT INTO xyoff VALUES(7,4,826,327);
          306  +INSERT INTO xyoff VALUES(7,4,465,462);
          307  +INSERT INTO xyoff VALUES(7,4,310,456);
          308  +INSERT INTO xyoff VALUES(7,4,577,613);
          309  +INSERT INTO xyoff VALUES(7,4,502,555);
          310  +INSERT INTO xyoff VALUES(8,1,601,620);
          311  +INSERT INTO xyoff VALUES(8,1,372,683);
          312  +INSERT INTO xyoff VALUES(8,1,758,399);
          313  +INSERT INTO xyoff VALUES(8,1,485,552);
          314  +INSERT INTO xyoff VALUES(8,1,159,563);
          315  +INSERT INTO xyoff VALUES(8,1,536,303);
          316  +INSERT INTO xyoff VALUES(8,1,122,263);
          317  +INSERT INTO xyoff VALUES(8,1,836,435);
          318  +INSERT INTO xyoff VALUES(8,1,544,146);
          319  +INSERT INTO xyoff VALUES(8,1,270,277);
          320  +INSERT INTO xyoff VALUES(8,2,849,281);
          321  +INSERT INTO xyoff VALUES(8,2,563,242);
          322  +INSERT INTO xyoff VALUES(8,2,704,463);
          323  +INSERT INTO xyoff VALUES(8,2,102,165);
          324  +INSERT INTO xyoff VALUES(8,2,797,524);
          325  +INSERT INTO xyoff VALUES(8,2,612,426);
          326  +INSERT INTO xyoff VALUES(8,2,345,372);
          327  +INSERT INTO xyoff VALUES(8,2,820,376);
          328  +INSERT INTO xyoff VALUES(8,2,789,156);
          329  +INSERT INTO xyoff VALUES(8,2,321,466);
          330  +INSERT INTO xyoff VALUES(8,3,150,332);
          331  +INSERT INTO xyoff VALUES(8,3,136,152);
          332  +INSERT INTO xyoff VALUES(8,3,468,528);
          333  +INSERT INTO xyoff VALUES(8,3,409,192);
          334  +INSERT INTO xyoff VALUES(8,3,820,216);
          335  +INSERT INTO xyoff VALUES(8,3,847,249);
          336  +INSERT INTO xyoff VALUES(8,3,801,267);
          337  +INSERT INTO xyoff VALUES(8,3,181,670);
          338  +INSERT INTO xyoff VALUES(8,3,398,563);
          339  +INSERT INTO xyoff VALUES(8,3,439,576);
          340  +INSERT INTO xyoff VALUES(8,4,123,309);
          341  +INSERT INTO xyoff VALUES(8,4,190,496);
          342  +INSERT INTO xyoff VALUES(8,4,571,531);
          343  +INSERT INTO xyoff VALUES(8,4,290,255);
          344  +INSERT INTO xyoff VALUES(8,4,244,412);
          345  +INSERT INTO xyoff VALUES(8,4,264,596);
          346  +INSERT INTO xyoff VALUES(8,4,253,420);
          347  +INSERT INTO xyoff VALUES(8,4,847,536);
          348  +INSERT INTO xyoff VALUES(8,4,120,288);
          349  +INSERT INTO xyoff VALUES(8,4,331,639);
          350  +
          351  +/* Create the geopoly object from test data above */
          352  +CREATE VIRTUAL TABLE geo1 USING geopoly(type,clr);
          353  +INSERT INTO geo1(_shape,type,clr)
          354  +  SELECT geopoly_xform(jshape,A,B,-B,A,xoff,yoff), basis.name, xform.clr
          355  +    FROM basis, xform, xyoff
          356  +   WHERE xyoff.id1=basis.rowid AND xyoff.id2=xform.rowid;
          357  +
          358  +
          359  +/* Query polygon */
          360  +CREATE TEMP TABLE querypoly(poly JSON, clr TEXT);
          361  +INSERT INTO querypoly(clr, poly) VALUES
          362  +  ('orange', '[[300,300],[400,350],[500,250],[480,500],[400,480],[300,550],[280,450],[320,400],[280,350],[300,300]]');
          363  +
          364  +/* Generate the HTML */
          365  +.print '<html>'
          366  +.print '<h1>Everything</h1>'
          367  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          368  +SELECT geopoly_svg(_shape, 
          369  +         printf('style="fill:none;stroke:%s;stroke-width:1"',clr)
          370  +       )
          371  +  FROM geo1;
          372  +SELECT geopoly_svg(poly, 
          373  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          374  +       )
          375  +  FROM querypoly;
          376  +.print '</svg>'
          377  +
          378  +.print '<h1>Overlap Query</h1>'
          379  +.print '<pre>'
          380  +.print 'SELECT *'
          381  +.print '  FROM geo1, querypoly'
          382  +.print ' WHERE geopoly_overlap(_shape, poly);'
          383  +.print 
          384  +EXPLAIN QUERY PLAN
          385  +SELECT geopoly_svg(_shape,
          386  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          387  +       )
          388  +  FROM geo1, querypoly
          389  + WHERE geopoly_overlap(_shape, poly);
          390  +.print '</pre>'
          391  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          392  +SELECT geopoly_svg(_shape,
          393  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          394  +       )
          395  +  FROM geo1, querypoly
          396  + WHERE geopoly_overlap(_shape, poly);
          397  +SELECT geopoly_svg(poly, 
          398  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          399  +       )
          400  +  FROM querypoly;
          401  +.print '</svg>'
          402  +
          403  +.print '<h1>Bounding-Box Overlap Query</h1>'
          404  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          405  +SELECT geopoly_svg(_shape,
          406  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          407  +       ),
          408  +       geopoly_svg(geopoly_bbox(_shape),
          409  +         'style="fill:none;stroke:black;stroke-width:1"'
          410  +       )
          411  +  FROM geo1, querypoly
          412  + WHERE geopoly_overlap(geopoly_bbox(_shape), geopoly_bbox(poly));
          413  +SELECT geopoly_svg(poly, 
          414  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          415  +       )
          416  +  FROM querypoly;
          417  +SELECT geopoly_svg(geopoly_bbox(poly),
          418  +         'style="fill:none;stroke:black;stroke-width:3"'
          419  +       )
          420  +  FROM querypoly;
          421  +.print '</svg>'
          422  +
          423  +.print '<h1>Within Query</h1>'
          424  +.print '<pre>'
          425  +.print 'SELECT *'
          426  +.print '  FROM geo1, querypoly'
          427  +.print ' WHERE geopoly_within(_shape, poly);'
          428  +.print 
          429  +EXPLAIN QUERY PLAN
          430  +SELECT geopoly_svg(_shape,
          431  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          432  +       )
          433  +  FROM geo1, querypoly
          434  + WHERE geopoly_within(_shape, poly);
          435  +.print '</pre>'
          436  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          437  +SELECT geopoly_svg(_shape,
          438  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          439  +       )
          440  +  FROM geo1, querypoly
          441  + WHERE geopoly_within(_shape, poly);
          442  +SELECT geopoly_svg(poly, 
          443  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          444  +       )
          445  +  FROM querypoly;
          446  +.print '</svg>'
          447  +
          448  +.print '<h1>Bounding-Box WITHIN Query</h1>'
          449  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          450  +SELECT geopoly_svg(_shape,
          451  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          452  +       ),
          453  +       geopoly_svg(geopoly_bbox(_shape),
          454  +         'style="fill:none;stroke:black;stroke-width:1"'
          455  +       )
          456  +  FROM geo1, querypoly
          457  + WHERE geopoly_within(geopoly_bbox(_shape), geopoly_bbox(poly));
          458  +SELECT geopoly_svg(poly, 
          459  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          460  +       )
          461  +  FROM querypoly;
          462  +SELECT geopoly_svg(geopoly_bbox(poly),
          463  +         'style="fill:none;stroke:black;stroke-width:3"'
          464  +       )
          465  +  FROM querypoly;
          466  +.print '</svg>'
          467  +
          468  +.print '<h1>Not Overlap Query</h1>'
          469  +.print '<pre>'
          470  +.print 'SELECT *'
          471  +.print '  FROM geo1, querypoly'
          472  +.print ' WHERE NOT geopoly_overlap(_shape, poly);'
          473  +.print 
          474  +EXPLAIN QUERY PLAN
          475  +SELECT geopoly_svg(_shape,
          476  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          477  +       )
          478  +  FROM geo1, querypoly
          479  + WHERE NOT geopoly_overlap(_shape, poly);
          480  +.print '</pre>'
          481  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          482  +SELECT geopoly_svg(_shape,
          483  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          484  +       )
          485  +  FROM geo1, querypoly
          486  + WHERE NOT geopoly_overlap(_shape, poly);
          487  +SELECT geopoly_svg(poly, 
          488  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          489  +       )
          490  +  FROM querypoly;
          491  +.print '</svg>'
          492  +
          493  +.print '<h1>Not Within Query</h1>'
          494  +.print '<pre>'
          495  +.print 'SELECT *'
          496  +.print '  FROM geo1, querypoly'
          497  +.print ' WHERE NOT geopoly_within(_shape, poly);'
          498  +.print 
          499  +EXPLAIN QUERY PLAN
          500  +SELECT geopoly_svg(_shape,
          501  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          502  +       )
          503  +  FROM geo1, querypoly
          504  + WHERE NOT geopoly_within(_shape, poly);
          505  +.print '</pre>'
          506  +.print '<svg width="1000" height="800" style="border:1px solid black">'
          507  +SELECT geopoly_svg(_shape,
          508  +         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
          509  +       )
          510  +  FROM geo1, querypoly
          511  + WHERE NOT geopoly_within(_shape, poly);
          512  +SELECT geopoly_svg(poly, 
          513  +         printf('style="fill:%s;fill-opacity:0.5;"',clr)
          514  +       )
          515  +  FROM querypoly;
          516  +.print '</svg>'
          517  +.print '</html>'

Changes to main.mk.

   225    225     $(TOP)/ext/fts3/fts3_write.c
   226    226   SRC += \
   227    227     $(TOP)/ext/icu/sqliteicu.h \
   228    228     $(TOP)/ext/icu/icu.c
   229    229   SRC += \
   230    230     $(TOP)/ext/rtree/sqlite3rtree.h \
   231    231     $(TOP)/ext/rtree/rtree.h \
   232         -  $(TOP)/ext/rtree/rtree.c
          232  +  $(TOP)/ext/rtree/rtree.c \
          233  +  $(TOP)/ext/rtree/geopoly.c
   233    234   SRC += \
   234    235     $(TOP)/ext/session/sqlite3session.c \
   235    236     $(TOP)/ext/session/sqlite3session.h
   236    237   SRC += \
   237    238     $(TOP)/ext/userauth/userauth.c \
   238    239     $(TOP)/ext/userauth/sqlite3userauth.h 
   239    240   SRC += \
................................................................................
   471    472     $(TOP)/ext/fts2/fts2_tokenizer.h
   472    473   EXTHDR += \
   473    474     $(TOP)/ext/fts3/fts3.h \
   474    475     $(TOP)/ext/fts3/fts3Int.h \
   475    476     $(TOP)/ext/fts3/fts3_hash.h \
   476    477     $(TOP)/ext/fts3/fts3_tokenizer.h
   477    478   EXTHDR += \
   478         -  $(TOP)/ext/rtree/rtree.h
          479  +  $(TOP)/ext/rtree/rtree.h \
          480  +  $(TOP)/ext/rtree/geopoly.c
   479    481   EXTHDR += \
   480    482     $(TOP)/ext/icu/sqliteicu.h
   481    483   EXTHDR += \
   482    484     $(TOP)/ext/fts5/fts5Int.h  \
   483    485     fts5parse.h                \
   484    486     $(TOP)/ext/fts5/fts5.h 
   485    487   EXTHDR += \

Changes to src/expr.c.

  3734   3734         ** see if it is a column in a virtual table.  This is done because
  3735   3735         ** the left operand of infix functions (the operand we want to
  3736   3736         ** control overloading) ends up as the second argument to the
  3737   3737         ** function.  The expression "A glob B" is equivalent to 
  3738   3738         ** "glob(B,A).  We want to use the A in "A glob B" to test
  3739   3739         ** for function overloading.  But we use the B term in "glob(B,A)".
  3740   3740         */
  3741         -      if( nFarg>=2 && (pExpr->flags & EP_InfixFunc) ){
         3741  +      if( nFarg>=2 && ExprHasProperty(pExpr, EP_InfixFunc) ){
  3742   3742           pDef = sqlite3VtabOverloadFunction(db, pDef, nFarg, pFarg->a[1].pExpr);
  3743   3743         }else if( nFarg>0 ){
  3744   3744           pDef = sqlite3VtabOverloadFunction(db, pDef, nFarg, pFarg->a[0].pExpr);
  3745   3745         }
  3746   3746   #endif
  3747   3747         if( pDef->funcFlags & SQLITE_FUNC_NEEDCOLL ){
  3748   3748           if( !pColl ) pColl = db->pDfltColl; 

Changes to src/sqlite.h.in.

  6436   6436   #define SQLITE_INDEX_CONSTRAINT_GLOB      66
  6437   6437   #define SQLITE_INDEX_CONSTRAINT_REGEXP    67
  6438   6438   #define SQLITE_INDEX_CONSTRAINT_NE        68
  6439   6439   #define SQLITE_INDEX_CONSTRAINT_ISNOT     69
  6440   6440   #define SQLITE_INDEX_CONSTRAINT_ISNOTNULL 70
  6441   6441   #define SQLITE_INDEX_CONSTRAINT_ISNULL    71
  6442   6442   #define SQLITE_INDEX_CONSTRAINT_IS        72
         6443  +#define SQLITE_INDEX_CONSTRAINT_FUNCTION 150
  6443   6444   
  6444   6445   /*
  6445   6446   ** CAPI3REF: Register A Virtual Table Implementation
  6446   6447   ** METHOD: sqlite3
  6447   6448   **
  6448   6449   ** ^These routines are used to register a new [virtual table module] name.
  6449   6450   ** ^Module names must be registered before

Changes to src/whereexpr.c.

   336    336   ** appropriate virtual table operator.  The return value is 1 or 2 if there
   337    337   ** is a match.  The usual return is 1, but if the RHS is also a column
   338    338   ** of virtual table in forms (5) or (7) then return 2.
   339    339   **
   340    340   ** If the expression matches none of the patterns above, return 0.
   341    341   */
   342    342   static int isAuxiliaryVtabOperator(
          343  +  sqlite3 *db,                    /* Parsing context */
   343    344     Expr *pExpr,                    /* Test this expression */
   344    345     unsigned char *peOp2,           /* OUT: 0 for MATCH, or else an op2 value */
   345    346     Expr **ppLeft,                  /* Column expression to left of MATCH/op2 */
   346    347     Expr **ppRight                  /* Expression to left of MATCH/op2 */
   347    348   ){
   348    349     if( pExpr->op==TK_FUNCTION ){
   349    350       static const struct Op2 {
................................................................................
   359    360       Expr *pCol;                     /* Column reference */
   360    361       int i;
   361    362   
   362    363       pList = pExpr->x.pList;
   363    364       if( pList==0 || pList->nExpr!=2 ){
   364    365         return 0;
   365    366       }
          367  +
          368  +    /* Built-in operators MATCH, GLOB, LIKE, and REGEXP attach to a
          369  +    ** virtual table on their second argument, which is the same as
          370  +    ** the left-hand side operand in their in-fix form.
          371  +    **
          372  +    **       vtab_column MATCH expression
          373  +    **       MATCH(expression,vtab_column)
          374  +    */
   366    375       pCol = pList->a[1].pExpr;
   367         -    if( pCol->op!=TK_COLUMN || !IsVirtual(pCol->pTab) ){
   368         -      return 0;
          376  +    if( pCol->op==TK_COLUMN && IsVirtual(pCol->pTab) ){
          377  +      for(i=0; i<ArraySize(aOp); i++){
          378  +        if( sqlite3StrICmp(pExpr->u.zToken, aOp[i].zOp)==0 ){
          379  +          *peOp2 = aOp[i].eOp2;
          380  +          *ppRight = pList->a[0].pExpr;
          381  +          *ppLeft = pCol;
          382  +          return 1;
          383  +        }
          384  +      }
   369    385       }
   370         -    for(i=0; i<ArraySize(aOp); i++){
   371         -      if( sqlite3StrICmp(pExpr->u.zToken, aOp[i].zOp)==0 ){
   372         -        *peOp2 = aOp[i].eOp2;
   373         -        *ppRight = pList->a[0].pExpr;
   374         -        *ppLeft = pCol;
   375         -        return 1;
          386  +
          387  +    /* We can also match against the first column of overloaded
          388  +    ** functions where xFindFunction returns a value of at least
          389  +    ** SQLITE_INDEX_CONSTRAINT_FUNCTION.
          390  +    **
          391  +    **      OVERLOADED(vtab_column,expression)
          392  +    **
          393  +    ** Historically, xFindFunction expected to see lower-case function
          394  +    ** names.  But for this use case, xFindFunction is expected to deal
          395  +    ** with function names in an arbitrary case.
          396  +    */
          397  +    pCol = pList->a[0].pExpr;
          398  +    if( pCol->op==TK_COLUMN && IsVirtual(pCol->pTab) ){
          399  +      sqlite3_vtab *pVtab;
          400  +      sqlite3_module *pMod;
          401  +      void (*xNotUsed)(sqlite3_context*,int,sqlite3_value**);
          402  +      void *pNotUsed;
          403  +      pVtab = sqlite3GetVTable(db, pCol->pTab)->pVtab;
          404  +      assert( pVtab!=0 );
          405  +      assert( pVtab->pModule!=0 );
          406  +      pMod = (sqlite3_module *)pVtab->pModule;
          407  +      if( pMod->xFindFunction!=0 ){
          408  +        i = pMod->xFindFunction(pVtab,2, pExpr->u.zToken, &xNotUsed, &pNotUsed);
          409  +        if( i>=SQLITE_INDEX_CONSTRAINT_FUNCTION ){
          410  +          *peOp2 = i;
          411  +          *ppRight = pList->a[1].pExpr;
          412  +          *ppLeft = pCol;
          413  +          return 1;
          414  +        }
   376    415         }
   377    416       }
   378    417     }else if( pExpr->op==TK_NE || pExpr->op==TK_ISNOT || pExpr->op==TK_NOTNULL ){
   379    418       int res = 0;
   380    419       Expr *pLeft = pExpr->pLeft;
   381    420       Expr *pRight = pExpr->pRight;
   382    421       if( pLeft->op==TK_COLUMN && IsVirtual(pLeft->pTab) ){
................................................................................
  1233   1272     ** is one of MATCH, LIKE, GLOB, REGEXP, !=, IS, IS NOT, or NOT NULL.
  1234   1273     ** This information is used by the xBestIndex methods of
  1235   1274     ** virtual tables.  The native query optimizer does not attempt
  1236   1275     ** to do anything with MATCH functions.
  1237   1276     */
  1238   1277     if( pWC->op==TK_AND ){
  1239   1278       Expr *pRight = 0, *pLeft = 0;
  1240         -    int res = isAuxiliaryVtabOperator(pExpr, &eOp2, &pLeft, &pRight);
         1279  +    int res = isAuxiliaryVtabOperator(db, pExpr, &eOp2, &pLeft, &pRight);
  1241   1280       while( res-- > 0 ){
  1242   1281         int idxNew;
  1243   1282         WhereTerm *pNewTerm;
  1244   1283         Bitmask prereqColumn, prereqExpr;
  1245   1284   
  1246   1285         prereqExpr = sqlite3WhereExprUsage(pMaskSet, pRight);
  1247   1286         prereqColumn = sqlite3WhereExprUsage(pMaskSet, pLeft);

Changes to tool/mksqlite3c.tcl.

    95     95   foreach hdr {
    96     96      btree.h
    97     97      btreeInt.h
    98     98      fts3.h
    99     99      fts3Int.h
   100    100      fts3_hash.h
   101    101      fts3_tokenizer.h
          102  +   geopoly.c
   102    103      hash.h
   103    104      hwtime.h
   104    105      keywordhash.h
   105    106      msvc.h
   106    107      mutex.h
   107    108      opcodes.h
   108    109      os_common.h
................................................................................
   388    389      fts3_tokenizer1.c
   389    390      fts3_tokenize_vtab.c
   390    391      fts3_write.c
   391    392      fts3_snippet.c
   392    393      fts3_unicode.c
   393    394      fts3_unicode2.c
   394    395   
          396  +   json1.c
   395    397      rtree.c
   396    398      icu.c
   397    399      fts3_icu.c
   398    400      sqlite3rbu.c
   399    401      dbstat.c
   400    402      dbpage.c
   401    403      sqlite3session.c
   402         -   json1.c
   403    404      fts5.c
   404    405      stmt.c
   405    406   } {
   406    407     copy_file tsrc/$file
   407    408   }
   408    409   
   409    410   # Synthesize an alternative sqlite3_sourceid() implementation that