/ Check-in [0593aac8]
Login

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

Overview
Comment:Forward port the geopoly extension functions into the r-tree extension, with the idea of creating a new spatial index based on simply polygons.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-geopoly
Files: files | file ages | folders
SHA3-256: 0593aac88a8c25ddafba4c29a181ee083dfc3dab44335feb6f12fdea6ce7fb27
User & Date: drh 2018-05-25 19:22:47
Context
2018-05-25
20:53
Incremental check-in: Progress toward implementing the geopoly vtab. check-in: 9b7d6f98 user: drh tags: rtree-geopoly
19:22
Forward port the geopoly extension functions into the r-tree extension, with the idea of creating a new spatial index based on simply polygons. check-in: 0593aac8 user: drh tags: rtree-geopoly
2018-05-24
23:51
When doing a one-pass UPDATE or DELETE on virtual tables, close the cursor prior to running VUpdate. This allows one-pass to work on virtual tables that do not allow concurrent reads and writes. Enhance rtree to take advantage of this new capability. check-in: b816023c user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to Makefile.in.

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

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   #
................................................................................
  1396   1396   SRC09 = \
  1397   1397     $(TOP)\ext\fts3\fts3.h \
  1398   1398     $(TOP)\ext\fts3\fts3Int.h \
  1399   1399     $(TOP)\ext\fts3\fts3_hash.h \
  1400   1400     $(TOP)\ext\fts3\fts3_tokenizer.h \
  1401   1401     $(TOP)\ext\icu\sqliteicu.h \
  1402   1402     $(TOP)\ext\rtree\rtree.h \
         1403  +  $(TOP)\ext\rtree\geopoly.c \
  1403   1404     $(TOP)\ext\rbu\sqlite3rbu.h \
  1404   1405     $(TOP)\ext\session\sqlite3session.h
  1405   1406   
  1406   1407   # Generated source code files
  1407   1408   #
  1408   1409   SRC10 = \
  1409   1410     opcodes.c \
................................................................................
  1569   1570     $(TOP)\ext\fts2\fts2_tokenizer.h
  1570   1571   EXTHDR = $(EXTHDR) \
  1571   1572     $(TOP)\ext\fts3\fts3.h \
  1572   1573     $(TOP)\ext\fts3\fts3Int.h \
  1573   1574     $(TOP)\ext\fts3\fts3_hash.h \
  1574   1575     $(TOP)\ext\fts3\fts3_tokenizer.h
  1575   1576   EXTHDR = $(EXTHDR) \
  1576         -  $(TOP)\ext\rtree\rtree.h
         1577  +  $(TOP)\ext\rtree\rtree.h \
         1578  +  $(TOP)\ext\rtree\geopoly.c
  1577   1579   EXTHDR = $(EXTHDR) \
  1578   1580     $(TOP)\ext\icu\sqliteicu.h
  1579   1581   EXTHDR = $(EXTHDR) \
  1580   1582     $(TOP)\ext\rtree\sqlite3rtree.h
  1581   1583   EXTHDR = $(EXTHDR) \
  1582   1584     $(TOP)\ext\session\sqlite3session.h
  1583   1585   

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>
................................................................................
 11625  11627   else
 11626  11628     enable_udlimit=no
 11627  11629   fi
 11628  11630   
 11629  11631   if test "${enable_udlimit}" = "yes" ; then
 11630  11632     OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_UPDATE_DELETE_LIMIT"
 11631  11633   fi
        11634  +
        11635  +#########
        11636  +# See whether we should enable GEOPOLY
        11637  +# Check whether --enable-geopoly was given.
        11638  +if test "${enable_geopoly+set}" = set; then :
        11639  +  enableval=$enable_geopoly; enable_geopoly=yes
        11640  +else
        11641  +  enable_geopoly=no
        11642  +fi
        11643  +
        11644  +if test "${enable_geopoly}" = "yes" ; then
        11645  +  OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_GEOPOLY"
        11646  +  enable_rtree=yes
        11647  +fi
 11632  11648   
 11633  11649   #########
 11634  11650   # See whether we should enable RTREE
 11635  11651   # Check whether --enable-rtree was given.
 11636  11652   if test "${enable_rtree+set}" = set; then :
 11637  11653     enableval=$enable_rtree; enable_rtree=yes
 11638  11654   else

Changes to configure.ac.

   655    655   # statements.
   656    656   AC_ARG_ENABLE(update-limit, AC_HELP_STRING([--enable-update-limit],
   657    657         [Enable the UPDATE/DELETE LIMIT clause]),
   658    658         [enable_udlimit=yes],[enable_udlimit=no])
   659    659   if test "${enable_udlimit}" = "yes" ; then
   660    660     OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_UPDATE_DELETE_LIMIT"
   661    661   fi
          662  +
          663  +#########
          664  +# See whether we should enable GEOPOLY
          665  +AC_ARG_ENABLE(geopoly, AC_HELP_STRING([--enable-geopoly],
          666  +      [Enable the GEOPOLY extension]),
          667  +      [enable_geopoly=yes],[enable_geopoly=no])
          668  +if test "${enable_geopoly}" = "yes" ; then
          669  +  OPT_FEATURE_FLAGS="${OPT_FEATURE_FLAGS} -DSQLITE_ENABLE_GEOPOLY"
          670  +  enable_rtree=yes
          671  +fi
   662    672   
   663    673   #########
   664    674   # See whether we should enable RTREE
   665    675   AC_ARG_ENABLE(rtree, AC_HELP_STRING([--enable-rtree],
   666    676         [Enable the RTREE extension]),
   667    677         [enable_rtree=yes],[enable_rtree=no])
   668    678   if test "${enable_rtree}" = "yes" ; then

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  +  const unsigned char *z = p->z;
          150  +  char c = geopolySkipSpace(p);
          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){
          197  +  GeoParse s;
          198  +  memset(&s, 0, sizeof(s));
          199  +  s.z = z;
          200  +  if( geopolySkipSpace(&s)=='[' ){
          201  +    s.z++;
          202  +    while( geopolySkipSpace(&s)=='[' ){
          203  +      int ii = 0;
          204  +      char c;
          205  +      s.z++;
          206  +      if( s.nVertex<=s.nAlloc ){
          207  +        GeoCoord *aNew;
          208  +        s.nAlloc = s.nAlloc*2 + 16;
          209  +        aNew = sqlite3_realloc64(s.a, s.nAlloc*sizeof(GeoCoord)*2 );
          210  +        if( aNew==0 ){
          211  +          s.nErr++;
          212  +          break;
          213  +        }
          214  +        s.a = aNew;
          215  +      }
          216  +      while( geopolyParseNumber(&s, ii<=1 ? &s.a[s.nVertex*2+ii] : 0) ){
          217  +        ii++;
          218  +        if( ii==2 ) s.nVertex++;
          219  +        c = geopolySkipSpace(&s);
          220  +        s.z++;
          221  +        if( c==',' ) continue;
          222  +        if( c==']' ) break;
          223  +        s.nErr++;
          224  +        goto parse_json_err;
          225  +      }
          226  +      if( geopolySkipSpace(&s)==',' ){
          227  +        s.z++;
          228  +        continue;
          229  +      }
          230  +      break;
          231  +    }
          232  +    if( geopolySkipSpace(&s)==']' && s.nVertex>=4 ){
          233  +      int nByte;
          234  +      GeoPoly *pOut;
          235  +      int x = (s.nVertex-1)*2;
          236  +      if( s.a[x]==s.a[0] && s.a[x+1]==s.a[1] ) s.nVertex--;
          237  +      nByte = sizeof(GeoPoly) * (s.nVertex-1)*2*sizeof(GeoCoord);
          238  +      pOut = sqlite3_malloc64( nByte );
          239  +      x = 1;
          240  +      if( pOut==0 ) goto parse_json_err;
          241  +      pOut->nVertex = s.nVertex;
          242  +      memcpy(pOut->a, s.a, s.nVertex*2*sizeof(GeoCoord));
          243  +      pOut->hdr[0] = *(unsigned char*)&x;
          244  +      pOut->hdr[1] = (s.nVertex>>16)&0xff;
          245  +      pOut->hdr[2] = (s.nVertex>>8)&0xff;
          246  +      pOut->hdr[3] = s.nVertex&0xff;
          247  +      sqlite3_free(s.a);
          248  +      return pOut;
          249  +    }else{
          250  +      s.nErr++;
          251  +    }
          252  +  }
          253  +parse_json_err:
          254  +  sqlite3_free(s.a);
          255  +  return 0;
          256  +}
          257  +
          258  +/*
          259  +** Given a function parameter, try to interpret it as a polygon, either
          260  +** in the binary format or JSON text.  Compute a GeoPoly object and
          261  +** return a pointer to that object.  Or if the input is not a well-formed
          262  +** polygon, put an error message in sqlite3_context and return NULL.
          263  +*/
          264  +static GeoPoly *geopolyFuncParam(sqlite3_context *pCtx, sqlite3_value *pVal){
          265  +  GeoPoly *p = 0;
          266  +  int nByte;
          267  +  if( sqlite3_value_type(pVal)==SQLITE_BLOB
          268  +   && (nByte = sqlite3_value_bytes(pVal))>=(4+6*sizeof(GeoCoord))
          269  +  ){
          270  +    const unsigned char *a = sqlite3_value_blob(pVal);
          271  +    int nVertex;
          272  +    nVertex = (a[1]<<16) + (a[2]<<8) + a[3];
          273  +    if( (a[0]==0 && a[0]==1)
          274  +     && (nVertex*2*sizeof(GeoCoord) + 4)==nByte
          275  +    ){
          276  +      p = sqlite3_malloc64( sizeof(*p) + (nVertex-1)*2*sizeof(GeoCoord) );
          277  +      if( p ){
          278  +        int x = 1;
          279  +        p->nVertex = nVertex;
          280  +        memcpy(p->hdr, a, nByte);
          281  +        if( a[0] != *(unsigned char*)&x ){
          282  +          int ii;
          283  +          for(ii=0; ii<nVertex*2; ii++){
          284  +            geopolySwab32((unsigned char*)&p->a[ii]);
          285  +          }
          286  +          p->hdr[0] ^= 1;
          287  +        }
          288  +      }
          289  +    }
          290  +  }else if( sqlite3_value_type(pVal)==SQLITE_TEXT ){
          291  +    p = geopolyParseJson(sqlite3_value_text(pVal));
          292  +  }
          293  +  if( p==0 ){
          294  +    sqlite3_result_error(pCtx, "not a valid polygon", -1);
          295  +  }
          296  +  return p;
          297  +}
          298  +
          299  +/*
          300  +** Implementation of the geopoly_blob(X) function.
          301  +**
          302  +** If the input is a well-formed Geopoly BLOB or JSON string
          303  +** then return the BLOB representation of the polygon.  Otherwise
          304  +** return NULL.
          305  +*/
          306  +static void geopolyBlobFunc(
          307  +  sqlite3_context *context,
          308  +  int argc,
          309  +  sqlite3_value **argv
          310  +){
          311  +  GeoPoly *p = geopolyFuncParam(context, argv[0]);
          312  +  if( p ){
          313  +    sqlite3_result_blob(context, p->hdr, 
          314  +       4+8*p->nVertex, SQLITE_TRANSIENT);
          315  +    sqlite3_free(p);
          316  +  }
          317  +}
          318  +
          319  +/*
          320  +** SQL function:     geopoly_json(X)
          321  +**
          322  +** Interpret X as a polygon and render it as a JSON array
          323  +** of coordinates.  Or, if X is not a valid polygon, return NULL.
          324  +*/
          325  +static void geopolyJsonFunc(
          326  +  sqlite3_context *context,
          327  +  int argc,
          328  +  sqlite3_value **argv
          329  +){
          330  +  GeoPoly *p = geopolyFuncParam(context, argv[0]);
          331  +  if( p ){
          332  +    sqlite3 *db = sqlite3_context_db_handle(context);
          333  +    sqlite3_str *x = sqlite3_str_new(db);
          334  +    int i;
          335  +    sqlite3_str_append(x, "[", 1);
          336  +    for(i=0; i<p->nVertex; i++){
          337  +      sqlite3_str_appendf(x, "[%!g,%!g],", p->a[i*2], p->a[i*2+1]);
          338  +    }
          339  +    sqlite3_str_appendf(x, "[%!g,%!g]]", p->a[0], p->a[1]);
          340  +    sqlite3_result_text(context, sqlite3_str_finish(x), -1, sqlite3_free);
          341  +    sqlite3_free(p);
          342  +  }
          343  +}
          344  +
          345  +/*
          346  +** SQL function:     geopoly_svg(X, ....)
          347  +**
          348  +** Interpret X as a polygon and render it as a SVG <polyline>.
          349  +** Additional arguments are added as attributes to the <polyline>.
          350  +*/
          351  +static void geopolySvgFunc(
          352  +  sqlite3_context *context,
          353  +  int argc,
          354  +  sqlite3_value **argv
          355  +){
          356  +  GeoPoly *p = geopolyFuncParam(context, argv[0]);
          357  +  if( p ){
          358  +    sqlite3 *db = sqlite3_context_db_handle(context);
          359  +    sqlite3_str *x = sqlite3_str_new(db);
          360  +    int i;
          361  +    char cSep = '\'';
          362  +    sqlite3_str_appendf(x, "<polyline points=");
          363  +    for(i=0; i<p->nVertex; i++){
          364  +      sqlite3_str_appendf(x, "%c%g,%g", cSep, p->a[i*2], p->a[i*2+1]);
          365  +      cSep = ' ';
          366  +    }
          367  +    sqlite3_str_appendf(x, " %g,%g'", p->a[0], p->a[1]);
          368  +    for(i=1; i<argc; i++){
          369  +      const char *z = (const char*)sqlite3_value_text(argv[i]);
          370  +      if( z && z[0] ){
          371  +        sqlite3_str_appendf(x, " %s", z);
          372  +      }
          373  +    }
          374  +    sqlite3_str_appendf(x, "></polyline>");
          375  +    sqlite3_result_text(context, sqlite3_str_finish(x), -1, sqlite3_free);
          376  +    sqlite3_free(p);
          377  +  }
          378  +}
          379  +
          380  +/*
          381  +** Implementation of the geopoly_area(X) function.
          382  +**
          383  +** If the input is a well-formed Geopoly BLOB then return the area
          384  +** enclosed by the polygon.  If the polygon circulates clockwise instead
          385  +** of counterclockwise (as it should) then return the negative of the
          386  +** enclosed area.  Otherwise return NULL.
          387  +*/
          388  +static void geopolyAreaFunc(
          389  +  sqlite3_context *context,
          390  +  int argc,
          391  +  sqlite3_value **argv
          392  +){
          393  +  GeoPoly *p = geopolyFuncParam(context, argv[0]);
          394  +  if( p ){
          395  +    double rArea = 0.0;
          396  +    int ii;
          397  +    for(ii=0; ii<p->nVertex-1; ii++){
          398  +      rArea += (p->a[ii*2] - p->a[ii*2+2])           /* (x0 - x1) */
          399  +                * (p->a[ii*2+1] + p->a[ii*2+3])      /* (y0 + y1) */
          400  +                * 0.5;
          401  +    }
          402  +    rArea += (p->a[ii*2] - p->a[0])                  /* (xN - x0) */
          403  +             * (p->a[ii*2+1] + p->a[1])              /* (yN + y0) */
          404  +             * 0.5;
          405  +    sqlite3_result_double(context, rArea);
          406  +    sqlite3_free(p);
          407  +  }            
          408  +}
          409  +
          410  +/*
          411  +** Determine if point (x0,y0) is beneath line segment (x1,y1)->(x2,y2).
          412  +** Returns:
          413  +**
          414  +**    +2  x0,y0 is on the line segement
          415  +**
          416  +**    +1  x0,y0 is beneath line segment
          417  +**
          418  +**    0   x0,y0 is not on or beneath the line segment or the line segment
          419  +**        is vertical and x0,y0 is not on the line segment
          420  +**
          421  +** The left-most coordinate min(x1,x2) is not considered to be part of
          422  +** the line segment for the purposes of this analysis.
          423  +*/
          424  +static int pointBeneathLine(
          425  +  double x0, double y0,
          426  +  double x1, double y1,
          427  +  double x2, double y2
          428  +){
          429  +  double y;
          430  +  if( x0==x1 && y0==y1 ) return 2;
          431  +  if( x1<x2 ){
          432  +    if( x0<=x1 || x0>x2 ) return 0;
          433  +  }else if( x1>x2 ){
          434  +    if( x0<=x2 || x0>x1 ) return 0;
          435  +  }else{
          436  +    /* Vertical line segment */
          437  +    if( x0!=x1 ) return 0;
          438  +    if( y0<y1 && y0<y2 ) return 0;
          439  +    if( y0>y1 && y0>y2 ) return 0;
          440  +    return 2;
          441  +  }
          442  +  y = y1 + (y2-y1)*(x0-x1)/(x2-x1);
          443  +  if( y0==y ) return 2;
          444  +  if( y0<y ) return 1;
          445  +  return 0;
          446  +}
          447  +
          448  +/*
          449  +** SQL function:    geopoly_within(P,X,Y)
          450  +**
          451  +** Return +2 if point X,Y is within polygon P.
          452  +** Return +1 if point X,Y is on the polygon boundary.
          453  +** Return 0 if point X,Y is outside the polygon
          454  +*/
          455  +static void geopolyWithinFunc(
          456  +  sqlite3_context *context,
          457  +  int argc,
          458  +  sqlite3_value **argv
          459  +){
          460  +  GeoPoly *p = geopolyFuncParam(context, argv[0]);
          461  +  double x0 = sqlite3_value_double(argv[1]);
          462  +  double y0 = sqlite3_value_double(argv[2]);
          463  +  if( p ){
          464  +    int v = 0;
          465  +    int cnt = 0;
          466  +    int ii;
          467  +    for(ii=0; ii<p->nVertex-1; ii++){
          468  +      v = pointBeneathLine(x0,y0,p->a[ii*2],p->a[ii*2+1],
          469  +                                 p->a[ii*2+2],p->a[ii*2+3]);
          470  +      if( v==2 ) break;
          471  +      cnt += v;
          472  +    }
          473  +    if( v!=2 ){
          474  +      v = pointBeneathLine(x0,y0,p->a[ii*2],p->a[ii*2+1],
          475  +                                 p->a[0],p->a[1]);
          476  +    }
          477  +    if( v==2 ){
          478  +      sqlite3_result_int(context, 1);
          479  +    }else if( ((v+cnt)&1)==0 ){
          480  +      sqlite3_result_int(context, 0);
          481  +    }else{
          482  +      sqlite3_result_int(context, 2);
          483  +    }
          484  +    sqlite3_free(p);
          485  +  }            
          486  +}
          487  +
          488  +/* Objects used by the overlap algorihm. */
          489  +typedef struct GeoEvent GeoEvent;
          490  +typedef struct GeoSegment GeoSegment;
          491  +typedef struct GeoOverlap GeoOverlap;
          492  +struct GeoEvent {
          493  +  double x;              /* X coordinate at which event occurs */
          494  +  int eType;             /* 0 for ADD, 1 for REMOVE */
          495  +  GeoSegment *pSeg;      /* The segment to be added or removed */
          496  +  GeoEvent *pNext;       /* Next event in the sorted list */
          497  +};
          498  +struct GeoSegment {
          499  +  double C, B;           /* y = C*x + B */
          500  +  double y;              /* Current y value */
          501  +  float y0;              /* Initial y value */
          502  +  unsigned char side;    /* 1 for p1, 2 for p2 */
          503  +  unsigned int idx;      /* Which segment within the side */
          504  +  GeoSegment *pNext;     /* Next segment in a list sorted by y */
          505  +};
          506  +struct GeoOverlap {
          507  +  GeoEvent *aEvent;          /* Array of all events */
          508  +  GeoSegment *aSegment;      /* Array of all segments */
          509  +  int nEvent;                /* Number of events */
          510  +  int nSegment;              /* Number of segments */
          511  +};
          512  +
          513  +/*
          514  +** Add a single segment and its associated events.
          515  +*/
          516  +static void geopolyAddOneSegment(
          517  +  GeoOverlap *p,
          518  +  GeoCoord x0,
          519  +  GeoCoord y0,
          520  +  GeoCoord x1,
          521  +  GeoCoord y1,
          522  +  unsigned char side,
          523  +  unsigned int idx
          524  +){
          525  +  GeoSegment *pSeg;
          526  +  GeoEvent *pEvent;
          527  +  if( x0==x1 ) return;  /* Ignore vertical segments */
          528  +  if( x0>x1 ){
          529  +    GeoCoord t = x0;
          530  +    x0 = x1;
          531  +    x1 = t;
          532  +    t = y0;
          533  +    y0 = y1;
          534  +    y1 = t;
          535  +  }
          536  +  pSeg = p->aSegment + p->nSegment;
          537  +  p->nSegment++;
          538  +  pSeg->C = (y1-y0)/(x1-x0);
          539  +  pSeg->B = y1 - x1*pSeg->C;
          540  +  pSeg->y0 = y0;
          541  +  pSeg->side = side;
          542  +  pSeg->idx = idx;
          543  +  pEvent = p->aEvent + p->nEvent;
          544  +  p->nEvent++;
          545  +  pEvent->x = x0;
          546  +  pEvent->eType = 0;
          547  +  pEvent->pSeg = pSeg;
          548  +  pEvent = p->aEvent + p->nEvent;
          549  +  p->nEvent++;
          550  +  pEvent->x = x1;
          551  +  pEvent->eType = 1;
          552  +  pEvent->pSeg = pSeg;
          553  +}
          554  +  
          555  +
          556  +
          557  +/*
          558  +** Insert all segments and events for polygon pPoly.
          559  +*/
          560  +static void geopolyAddSegments(
          561  +  GeoOverlap *p,          /* Add segments to this Overlap object */
          562  +  GeoPoly *pPoly,         /* Take all segments from this polygon */
          563  +  unsigned char side      /* The side of pPoly */
          564  +){
          565  +  unsigned int i;
          566  +  GeoCoord *x;
          567  +  for(i=0; i<pPoly->nVertex-1; i++){
          568  +    x = pPoly->a + (i*2);
          569  +    geopolyAddOneSegment(p, x[0], x[1], x[2], x[3], side, i);
          570  +  }
          571  +  x = pPoly->a + (i*2);
          572  +  geopolyAddOneSegment(p, x[0], x[1], pPoly->a[0], pPoly->a[1], side, i);
          573  +}
          574  +
          575  +/*
          576  +** Merge two lists of sorted events by X coordinate
          577  +*/
          578  +static GeoEvent *geopolyEventMerge(GeoEvent *pLeft, GeoEvent *pRight){
          579  +  GeoEvent head, *pLast;
          580  +  head.pNext = 0;
          581  +  pLast = &head;
          582  +  while( pRight && pLeft ){
          583  +    if( pRight->x <= pLeft->x ){
          584  +      pLast->pNext = pRight;
          585  +      pLast = pRight;
          586  +      pRight = pRight->pNext;
          587  +    }else{
          588  +      pLast->pNext = pLeft;
          589  +      pLast = pLeft;
          590  +      pLeft = pLeft->pNext;
          591  +    }
          592  +  }
          593  +  pLast->pNext = pRight ? pRight : pLeft;
          594  +  return head.pNext;  
          595  +}
          596  +
          597  +/*
          598  +** Sort an array of nEvent event objects into a list.
          599  +*/
          600  +static GeoEvent *geopolySortEventsByX(GeoEvent *aEvent, int nEvent){
          601  +  int mx = 0;
          602  +  int i, j;
          603  +  GeoEvent *p;
          604  +  GeoEvent *a[50];
          605  +  for(i=0; i<nEvent; i++){
          606  +    p = &aEvent[i];
          607  +    p->pNext = 0;
          608  +    for(j=0; j<mx && a[j]; j++){
          609  +      p = geopolyEventMerge(a[j], p);
          610  +      a[j] = 0;
          611  +    }
          612  +    a[j] = p;
          613  +    if( j>=mx ) mx = j+1;
          614  +  }
          615  +  p = 0;
          616  +  for(i=0; i<mx; i++){
          617  +    p = geopolyEventMerge(a[i], p);
          618  +  }
          619  +  return p;
          620  +}
          621  +
          622  +/*
          623  +** Merge two lists of sorted segments by Y, and then by C.
          624  +*/
          625  +static GeoSegment *geopolySegmentMerge(GeoSegment *pLeft, GeoSegment *pRight){
          626  +  GeoSegment head, *pLast;
          627  +  head.pNext = 0;
          628  +  pLast = &head;
          629  +  while( pRight && pLeft ){
          630  +    double r = pRight->y - pLeft->y;
          631  +    if( r==0.0 ) r = pRight->C - pLeft->C;
          632  +    if( r<0.0 ){
          633  +      pLast->pNext = pRight;
          634  +      pLast = pRight;
          635  +      pRight = pRight->pNext;
          636  +    }else{
          637  +      pLast->pNext = pLeft;
          638  +      pLast = pLeft;
          639  +      pLeft = pLeft->pNext;
          640  +    }
          641  +  }
          642  +  pLast->pNext = pRight ? pRight : pLeft;
          643  +  return head.pNext;  
          644  +}
          645  +
          646  +/*
          647  +** Sort a list of GeoSegments in order of increasing Y and in the event of
          648  +** a tie, increasing C (slope).
          649  +*/
          650  +static GeoSegment *geopolySortSegmentsByYAndC(GeoSegment *pList){
          651  +  int mx = 0;
          652  +  int i;
          653  +  GeoSegment *p;
          654  +  GeoSegment *a[50];
          655  +  while( pList ){
          656  +    p = pList;
          657  +    pList = pList->pNext;
          658  +    p->pNext = 0;
          659  +    for(i=0; i<mx && a[i]; i++){
          660  +      p = geopolySegmentMerge(a[i], p);
          661  +      a[i] = 0;
          662  +    }
          663  +    a[i] = p;
          664  +    if( i>=mx ) mx = i+1;
          665  +  }
          666  +  p = 0;
          667  +  for(i=0; i<mx; i++){
          668  +    p = geopolySegmentMerge(a[i], p);
          669  +  }
          670  +  return p;
          671  +}
          672  +
          673  +/*
          674  +** Determine the overlap between two polygons
          675  +*/
          676  +static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2){
          677  +  int nVertex = p1->nVertex + p2->nVertex + 2;
          678  +  GeoOverlap *p;
          679  +  int nByte;
          680  +  GeoEvent *pThisEvent;
          681  +  double rX;
          682  +  int rc = 0;
          683  +  int needSort = 0;
          684  +  GeoSegment *pActive = 0;
          685  +  GeoSegment *pSeg;
          686  +  unsigned char aOverlap[4];
          687  +
          688  +  nByte = sizeof(GeoEvent)*nVertex*2 
          689  +           + sizeof(GeoSegment)*nVertex 
          690  +           + sizeof(GeoOverlap);
          691  +  p = sqlite3_malloc( nByte );
          692  +  if( p==0 ) return -1;
          693  +  p->aEvent = (GeoEvent*)&p[1];
          694  +  p->aSegment = (GeoSegment*)&p->aEvent[nVertex*2];
          695  +  p->nEvent = p->nSegment = 0;
          696  +  geopolyAddSegments(p, p1, 1);
          697  +  geopolyAddSegments(p, p2, 2);
          698  +  pThisEvent = geopolySortEventsByX(p->aEvent, p->nEvent);
          699  +  rX = pThisEvent->x==0.0 ? -1.0 : 0.0;
          700  +  memset(aOverlap, 0, sizeof(aOverlap));
          701  +  while( pThisEvent ){
          702  +    if( pThisEvent->x!=rX ){
          703  +      GeoSegment *pPrev = 0;
          704  +      int iMask = 0;
          705  +      GEODEBUG(("Distinct X: %g\n", pThisEvent->x));
          706  +      rX = pThisEvent->x;
          707  +      if( needSort ){
          708  +        GEODEBUG(("SORT\n"));
          709  +        pActive = geopolySortSegmentsByYAndC(pActive);
          710  +        needSort = 0;
          711  +      }
          712  +      for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
          713  +        if( pPrev ){
          714  +          if( pPrev->y!=pSeg->y ){
          715  +            GEODEBUG(("MASK: %d\n", iMask));
          716  +            aOverlap[iMask] = 1;
          717  +          }
          718  +        }
          719  +        iMask ^= pSeg->side;
          720  +        pPrev = pSeg;
          721  +      }
          722  +      pPrev = 0;
          723  +      for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
          724  +        double y = pSeg->C*rX + pSeg->B;
          725  +        GEODEBUG(("Segment %d.%d %g->%g\n", pSeg->side, pSeg->idx, pSeg->y, y));
          726  +        pSeg->y = y;
          727  +        if( pPrev ){
          728  +          if( pPrev->y>pSeg->y && pPrev->side!=pSeg->side ){
          729  +            rc = 1;
          730  +            GEODEBUG(("Crossing: %d.%d and %d.%d\n",
          731  +                    pPrev->side, pPrev->idx,
          732  +                    pSeg->side, pSeg->idx));
          733  +            goto geopolyOverlapDone;
          734  +          }else if( pPrev->y!=pSeg->y ){
          735  +            GEODEBUG(("MASK: %d\n", iMask));
          736  +            aOverlap[iMask] = 1;
          737  +          }
          738  +        }
          739  +        iMask ^= pSeg->side;
          740  +        pPrev = pSeg;
          741  +      }
          742  +    }
          743  +    GEODEBUG(("%s %d.%d C=%g B=%g\n",
          744  +      pThisEvent->eType ? "RM " : "ADD",
          745  +      pThisEvent->pSeg->side, pThisEvent->pSeg->idx,
          746  +      pThisEvent->pSeg->C,
          747  +      pThisEvent->pSeg->B));
          748  +    if( pThisEvent->eType==0 ){
          749  +      /* Add a segment */
          750  +      pSeg = pThisEvent->pSeg;
          751  +      pSeg->y = pSeg->y0;
          752  +      pSeg->pNext = pActive;
          753  +      pActive = pSeg;
          754  +      needSort = 1;
          755  +    }else{
          756  +      /* Remove a segment */
          757  +      if( pActive==pThisEvent->pSeg ){
          758  +        pActive = pActive->pNext;
          759  +      }else{
          760  +        for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
          761  +          if( pSeg->pNext==pThisEvent->pSeg ){
          762  +            pSeg->pNext = pSeg->pNext->pNext;
          763  +            break;
          764  +          }
          765  +        }
          766  +      }
          767  +    }
          768  +    pThisEvent = pThisEvent->pNext;
          769  +  }
          770  +  if( aOverlap[3]==0 ){
          771  +    rc = 0;
          772  +  }else if( aOverlap[1]!=0 && aOverlap[2]==0 ){
          773  +    rc = 3;
          774  +  }else if( aOverlap[1]==0 && aOverlap[2]!=0 ){
          775  +    rc = 2;
          776  +  }else if( aOverlap[1]==0 && aOverlap[2]==0 ){
          777  +    rc = 4;
          778  +  }else{
          779  +    rc = 1;
          780  +  }
          781  +
          782  +geopolyOverlapDone:
          783  +  sqlite3_free(p);
          784  +  return rc;
          785  +}
          786  +
          787  +/*
          788  +** SQL function:    geopoly_overlap(P1,P2)
          789  +**
          790  +** Determine whether or not P1 and P2 overlap. Return value:
          791  +**
          792  +**   0     The two polygons are disjoint
          793  +**   1     They overlap
          794  +**   2     P1 is completely contained within P2
          795  +**   3     P2 is completely contained within P1
          796  +**   4     P1 and P2 are the same polygon
          797  +**   NULL  Either P1 or P2 or both are not valid polygons
          798  +*/
          799  +static void geopolyOverlapFunc(
          800  +  sqlite3_context *context,
          801  +  int argc,
          802  +  sqlite3_value **argv
          803  +){
          804  +  GeoPoly *p1 = geopolyFuncParam(context, argv[0]);
          805  +  GeoPoly *p2 = geopolyFuncParam(context, argv[1]);
          806  +  if( p1 && p2 ){
          807  +    int x = geopolyOverlap(p1, p2);
          808  +    if( x<0 ){
          809  +      sqlite3_result_error_nomem(context);
          810  +    }else{
          811  +      sqlite3_result_int(context, x);
          812  +    }
          813  +  }
          814  +  sqlite3_free(p1);
          815  +  sqlite3_free(p2);
          816  +}
          817  +
          818  +/*
          819  +** Enable or disable debugging output
          820  +*/
          821  +static void geopolyDebugFunc(
          822  +  sqlite3_context *context,
          823  +  int argc,
          824  +  sqlite3_value **argv
          825  +){
          826  +#ifdef GEOPOLY_ENABLE_DEBUG
          827  +  geo_debug = sqlite3_value_int(argv[0]);
          828  +#endif
          829  +}
          830  +
          831  +static int sqlite3_geopoly_init(sqlite3 *db){
          832  +  int rc = SQLITE_OK;
          833  +  static const struct {
          834  +    void (*xFunc)(sqlite3_context*,int,sqlite3_value**);
          835  +    int nArg;
          836  +    const char *zName;
          837  +  } aFunc[] = {
          838  +     { geopolyAreaFunc,          1,    "geopoly_area"     },
          839  +     { geopolyBlobFunc,          1,    "geopoly_blob"     },
          840  +     { geopolyJsonFunc,          1,    "geopoly_json"     },
          841  +     { geopolySvgFunc,          -1,    "geopoly_svg"      },
          842  +     { geopolyWithinFunc,        3,    "geopoly_within"   },
          843  +     { geopolyOverlapFunc,       2,    "geopoly_overlap"  },
          844  +     { geopolyDebugFunc,         1,    "geopoly_debug"    },
          845  +  };
          846  +  int i;
          847  +  for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){
          848  +    rc = sqlite3_create_function(db, aFunc[i].zName, aFunc[i].nArg,
          849  +                                 SQLITE_UTF8, 0,
          850  +                                 aFunc[i].xFunc, 0, 0);
          851  +  }
          852  +  return rc;
          853  +}

Changes to ext/rtree/rtree.c.

  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()

Changes to main.mk.

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

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
................................................................................
   387    388      fts3_tokenizer1.c
   388    389      fts3_tokenize_vtab.c
   389    390      fts3_write.c
   390    391      fts3_snippet.c
   391    392      fts3_unicode.c
   392    393      fts3_unicode2.c
   393    394   
          395  +   json1.c
   394    396      rtree.c
   395    397      icu.c
   396    398      fts3_icu.c
   397    399      sqlite3rbu.c
   398    400      dbstat.c
   399    401      dbpage.c
   400    402      sqlite3session.c
   401         -   json1.c
   402    403      fts5.c
   403    404      stmt.c
   404    405   } {
   405    406     copy_file tsrc/$file
   406    407   }
   407    408   
   408    409   # Synthesize an alternative sqlite3_sourceid() implementation that