/ Check-in [77bb7b7d]
Login
☰Home Timeline Branches

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

Overview
Comment:Preliminary tests show geopoly_overlap() is working.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | geojson
Files: files | file ages | folders
SHA3-256: 77bb7b7d7278725e4e02935d485c3540bb41f4fc29ca8da679b2a380ebc38d7d
User & Date: drh 2018-05-12 20:28:51
Context
2018-05-12
21:09
Add the geopoly_svg() SQL function. (check-in: 318ba5f0 user: drh tags: geojson)
20:28
Preliminary tests show geopoly_overlap() is working. (check-in: 77bb7b7d user: drh tags: geojson)
16:05
An initial attempt at an overlap function in the geopoly extension. (check-in: c857976e user: drh tags: geojson)
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to ext/misc/geopoly.c. 

16
17
18
19
20
21
22








23
24
25
26
27
28
29
...
635
636
637
638
639
640
641

642
643
644
645
646
647
648
...
656
657
658
659
660
661
662
663
664

665


666











667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696

697
698
699
700
701
702
703
...
753
754
755
756
757
758
759












760
761
762
763
764
765
766
...
773
774
775
776
777
778
779

780
781
782
783
784
785
786
787
788
789
790

#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define SQLITE_HAVE_GEOPLOY 1









#ifndef JSON_NULL   /* The following stuff repeats things found in json1 */
/*
** Versions of isspace(), isalnum() and isdigit() to which it is safe
** to pass signed char values.
*/
#ifdef sqlite3Isdigit
................................................................................
static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2){
  int nVertex = p1->nVertex + p2->nVertex + 2;
  GeoOverlap *p;
  int nByte;
  GeoEvent *pThisEvent;
  double rX;
  int rc = 0;

  GeoSegment *pActive = 0;
  GeoSegment *pSeg;
  unsigned char aOverlap[4];

  nByte = sizeof(GeoEvent)*nVertex*2 
           + sizeof(GeoSegment)*nVertex 
           + sizeof(GeoOverlap);
................................................................................
  pThisEvent = geopolySortEventsByX(p->aEvent, p->nEvent);
  rX = pThisEvent->x==0.0 ? -1.0 : 0.0;
  memset(aOverlap, 0, sizeof(aOverlap));
  while( pThisEvent ){
    if( pThisEvent->x!=rX ){
      GeoSegment *pPrev = 0;
      int iMask = 0;
      printf("Distinct X: %g\n", pThisEvent->x);
      rX = pThisEvent->x;

      pActive = geopolySortSegmentsByYAndC(pActive);


      for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){











        double y = pSeg->C*rX + pSeg->B;
        printf("Segment %d.%d %g->%g\n", pSeg->side, pSeg->idx, pSeg->y, y);
        pSeg->y = y;
        if( pPrev ){
          if( pPrev->y>pSeg->y ){
            rc = 1;
            printf("Crossing: %d.%d and %d.%d\n",
                    pPrev->side, pPrev->idx,
                    pSeg->side, pSeg->idx);
            goto geopolyOverlapDone;
          }else if( pPrev->y!=pSeg->y ){
            printf("MASK: %d\n", iMask);
            aOverlap[iMask] = 1;
          }
        }
        iMask ^= pSeg->side;
        pPrev = pSeg;
      }
    }
    printf("%s %d.%d C=%g B=%g\n",
      pThisEvent->eType ? "RM " : "ADD",
      pThisEvent->pSeg->side, pThisEvent->pSeg->idx,
      pThisEvent->pSeg->C,
      pThisEvent->pSeg->B);
    if( pThisEvent->eType==0 ){
      /* Add a segment */
      pSeg = pThisEvent->pSeg;
      pSeg->y = pSeg->C*rX + pSeg->B;
      pSeg->pNext = pActive;
      pActive = pSeg;

    }else{
      /* Remove a segment */
      if( pActive==pThisEvent->pSeg ){
        pActive = pActive->pNext;
      }else{
        for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
          if( pSeg->pNext==pThisEvent->pSeg ){
................................................................................
      sqlite3_result_int(context, x);
    }
  }
  sqlite3_free(p1);
  sqlite3_free(p2);
}














#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_geopoly_init(
  sqlite3 *db, 
  char **pzErrMsg, 
................................................................................
    const char *zName;
  } aFunc[] = {
     { geopolyAreaFunc,          1,    "geopoly_area"     },
     { geopolyBlobFunc,          1,    "geopoly_blob"     },
     { geopolyJsonFunc,          1,    "geopoly_json"     },
     { geopolyWithinFunc,        3,    "geopoly_within"   },
     { geopolyOverlapFunc,       2,    "geopoly_overlap"  },

  };
  int i;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){
    rc = sqlite3_create_function(db, aFunc[i].zName, aFunc[i].nArg,
                                 SQLITE_UTF8, 0,
                                 aFunc[i].xFunc, 0, 0);
  }
  return rc;
}








>
>
>
>
>
>
>
>







 







>







 







|

>
|
>
>

>
>
>
>
>
>
>
>
>
>
>

|




|

|


|







|



|






>







 







>
>
>
>
>
>
>
>
>
>
>
>







 







>












16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
...
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
...
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
...
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
...
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827

#include "sqlite3ext.h"
SQLITE_EXTENSION_INIT1
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define SQLITE_HAVE_GEOPLOY 1

/* Enable -DGEOPOLY_ENABLE_DEBUG for debugging facilities */
#ifdef GEOPOLY_ENABLE_DEBUG
  static int geo_debug = 0;
# define GEODEBUG(X) if(geo_debug)printf X
#else
# define GEODEBUG(X)
#endif

#ifndef JSON_NULL   /* The following stuff repeats things found in json1 */
/*
** Versions of isspace(), isalnum() and isdigit() to which it is safe
** to pass signed char values.
*/
#ifdef sqlite3Isdigit
................................................................................
static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2){
  int nVertex = p1->nVertex + p2->nVertex + 2;
  GeoOverlap *p;
  int nByte;
  GeoEvent *pThisEvent;
  double rX;
  int rc = 0;
  int needSort = 0;
  GeoSegment *pActive = 0;
  GeoSegment *pSeg;
  unsigned char aOverlap[4];

  nByte = sizeof(GeoEvent)*nVertex*2 
           + sizeof(GeoSegment)*nVertex 
           + sizeof(GeoOverlap);
................................................................................
  pThisEvent = geopolySortEventsByX(p->aEvent, p->nEvent);
  rX = pThisEvent->x==0.0 ? -1.0 : 0.0;
  memset(aOverlap, 0, sizeof(aOverlap));
  while( pThisEvent ){
    if( pThisEvent->x!=rX ){
      GeoSegment *pPrev = 0;
      int iMask = 0;
      GEODEBUG(("Distinct X: %g\n", pThisEvent->x));
      rX = pThisEvent->x;
      if( needSort ){
        pActive = geopolySortSegmentsByYAndC(pActive);
        needSort = 0;
      }
      for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
        if( pPrev ){
          if( pPrev->y!=pSeg->y ){
            GEODEBUG(("MASK: %d\n", iMask));
            aOverlap[iMask] = 1;
          }
        }
        iMask ^= pSeg->side;
        pPrev = pSeg;
      }
      pPrev = 0;
      for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
        double y = pSeg->C*rX + pSeg->B;
        GEODEBUG(("Segment %d.%d %g->%g\n", pSeg->side, pSeg->idx, pSeg->y, y));
        pSeg->y = y;
        if( pPrev ){
          if( pPrev->y>pSeg->y ){
            rc = 1;
            GEODEBUG(("Crossing: %d.%d and %d.%d\n",
                    pPrev->side, pPrev->idx,
                    pSeg->side, pSeg->idx));
            goto geopolyOverlapDone;
          }else if( pPrev->y!=pSeg->y ){
            GEODEBUG(("MASK: %d\n", iMask));
            aOverlap[iMask] = 1;
          }
        }
        iMask ^= pSeg->side;
        pPrev = pSeg;
      }
    }
    GEODEBUG(("%s %d.%d C=%g B=%g\n",
      pThisEvent->eType ? "RM " : "ADD",
      pThisEvent->pSeg->side, pThisEvent->pSeg->idx,
      pThisEvent->pSeg->C,
      pThisEvent->pSeg->B));
    if( pThisEvent->eType==0 ){
      /* Add a segment */
      pSeg = pThisEvent->pSeg;
      pSeg->y = pSeg->C*rX + pSeg->B;
      pSeg->pNext = pActive;
      pActive = pSeg;
      needSort = 1;
    }else{
      /* Remove a segment */
      if( pActive==pThisEvent->pSeg ){
        pActive = pActive->pNext;
      }else{
        for(pSeg=pActive; pSeg; pSeg=pSeg->pNext){
          if( pSeg->pNext==pThisEvent->pSeg ){
................................................................................
      sqlite3_result_int(context, x);
    }
  }
  sqlite3_free(p1);
  sqlite3_free(p2);
}

/*
** Enable or disable debugging output
*/
static void geopolyDebugFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
#ifdef GEOPOLY_ENABLE_DEBUG
  geo_debug = sqlite3_value_int(argv[0]);
#endif
}

#ifdef _WIN32
__declspec(dllexport)
#endif
int sqlite3_geopoly_init(
  sqlite3 *db, 
  char **pzErrMsg, 
................................................................................
    const char *zName;
  } aFunc[] = {
     { geopolyAreaFunc,          1,    "geopoly_area"     },
     { geopolyBlobFunc,          1,    "geopoly_blob"     },
     { geopolyJsonFunc,          1,    "geopoly_json"     },
     { geopolyWithinFunc,        3,    "geopoly_within"   },
     { geopolyOverlapFunc,       2,    "geopoly_overlap"  },
     { geopolyDebugFunc,         1,    "geopoly_debug"    },
  };
  int i;
  SQLITE_EXTENSION_INIT2(pApi);
  (void)pzErrMsg;  /* Unused parameter */
  for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){
    rc = sqlite3_create_function(db, aFunc[i].zName, aFunc[i].nArg,
                                 SQLITE_UTF8, 0,
                                 aFunc[i].xFunc, 0, 0);
  }
  return rc;
}

This page was generated in about 0.026s by Fossil 2.13 [6c2b5bafb6] 2020-10-20 23:40:13