/ Check-in [5a0e1541]
Login

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

Overview
Comment:Split the three-argument version of geopoly_within() off into a separate function named geopoly_contains_point().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-geopoly
Files: files | file ages | folders
SHA3-256:5a0e1541037b5bbc1b4bf26a7da304c9b32ea72960aca8b9309cf2180757c8a4
User & Date: drh 2018-08-27 15:55:37
Context
2018-08-27
17:05
Minor changes to the visual01.txt test script. Closed-Leaf check-in: 4bc28eed user: drh tags: rtree-geopoly
15:55
Split the three-argument version of geopoly_within() off into a separate function named geopoly_contains_point(). check-in: 5a0e1541 user: drh tags: rtree-geopoly
2018-08-25
23:03
Enhance the geopoly virtual table so that it does a better job of optimizing geopoly_within() queries. check-in: 1f717385 user: drh tags: rtree-geopoly
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to ext/rtree/geopoly.c.

575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611

612
613
614
615
616
617
618
...
622
623
624
625
626
627
628
629















630



631
632
633
634
635
636
637
638
639
640
641
642

643
644
645
646
647
648
649
....
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
....
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
  }
  y = y1 + (y2-y1)*(x0-x1)/(x2-x1);
  if( y0==y ) return 2;
  if( y0<y ) return 1;
  return 0;
}

/* Forward declaration */
static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2);

/*
** SQL function:    geopoly_within(P,X,Y)  -- 3-argument form
**
** Return +2 if point X,Y is within polygon P.
** Return +1 if point X,Y is on the polygon boundary.
** Return 0 if point X,Y is outside the polygon
**
** SQL function:    geopoly_within(P1,P2)  -- 2-argument form
**
** Return +2 if P1 and P2 are the same polygon
** Return +1 if P2 is contained within P1
** Return 0 if any part of P2 is on the outside of P1
**
*/
static void geopolyWithinFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);
  if( p1==0 ) return;
  if( argc==3 ){
    double x0 = sqlite3_value_double(argv[1]);
    double y0 = sqlite3_value_double(argv[2]);
    int v = 0;
    int cnt = 0;
    int ii;

    for(ii=0; ii<p1->nVertex-1; ii++){
      v = pointBeneathLine(x0,y0,p1->a[ii*2],p1->a[ii*2+1],
                                 p1->a[ii*2+2],p1->a[ii*2+3]);
      if( v==2 ) break;
      cnt += v;
    }
    if( v!=2 ){
................................................................................
    if( v==2 ){
      sqlite3_result_int(context, 1);
    }else if( ((v+cnt)&1)==0 ){
      sqlite3_result_int(context, 0);
    }else{
      sqlite3_result_int(context, 2);
    }
  }else{















    assert( argc==2 );



    GeoPoly *p2 = geopolyFuncParam(context, argv[1], 0);
    if( p2 ){
      int x = geopolyOverlap(p1, p2);
      if( x<0 ){
        sqlite3_result_error_nomem(context);
      }else{
        sqlite3_result_int(context, x==2 ? 1 : x==4 ? 2 : 0);
      }
      sqlite3_free(p2);
    }
  }
  sqlite3_free(p1);

}

/* Objects used by the overlap algorihm. */
typedef struct GeoEvent GeoEvent;
typedef struct GeoSegment GeoSegment;
typedef struct GeoOverlap GeoOverlap;
struct GeoEvent {
................................................................................
  void **ppArg
){
  if( sqlite3_stricmp(zName, "geopoly_overlap")==0 ){
    *pxFunc = geopolyOverlapFunc;
    *ppArg = 0;
    return SQLITE_INDEX_CONSTRAINT_FUNCTION;
  }
  if( nArg==2 && sqlite3_stricmp(zName, "geopoly_within")==0 ){
    *pxFunc = geopolyWithinFunc;
    *ppArg = 0;
    return SQLITE_INDEX_CONSTRAINT_FUNCTION+1;
  }
  return 0;
}

................................................................................
    const char *zName;
  } aFunc[] = {
     { geopolyAreaFunc,          1,    "geopoly_area"     },
     { geopolyBlobFunc,          1,    "geopoly_blob"     },
     { geopolyJsonFunc,          1,    "geopoly_json"     },
     { geopolySvgFunc,          -1,    "geopoly_svg"      },
     { geopolyWithinFunc,        2,    "geopoly_within"   },
     { geopolyWithinFunc,        3,    "geopoly_within"   },
     { geopolyOverlapFunc,       2,    "geopoly_overlap"  },
     { geopolyDebugFunc,         1,    "geopoly_debug"    },
     { geopolyBBoxFunc,          1,    "geopoly_bbox"     },
     { geopolyXformFunc,         7,    "geopoly_xform"    },
  };
  int i;
  for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){







<
<
<

|




<
<
<
<
<
<
<

|





<
<





>







 







|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
|
|






<
|
<

>







 







|







 







|







575
576
577
578
579
580
581



582
583
584
585
586
587







588
589
590
591
592
593
594


595
596
597
598
599
600
601
602
603
604
605
606
607
...
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645

646

647
648
649
650
651
652
653
654
655
....
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
....
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
  }
  y = y1 + (y2-y1)*(x0-x1)/(x2-x1);
  if( y0==y ) return 2;
  if( y0<y ) return 1;
  return 0;
}




/*
** SQL function:    geopoly_contains_point(P,X,Y)
**
** Return +2 if point X,Y is within polygon P.
** Return +1 if point X,Y is on the polygon boundary.
** Return 0 if point X,Y is outside the polygon







*/
static void geopolyContainsPointFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);


  double x0 = sqlite3_value_double(argv[1]);
  double y0 = sqlite3_value_double(argv[2]);
  int v = 0;
  int cnt = 0;
  int ii;
  if( p1==0 ) return;
  for(ii=0; ii<p1->nVertex-1; ii++){
    v = pointBeneathLine(x0,y0,p1->a[ii*2],p1->a[ii*2+1],
                               p1->a[ii*2+2],p1->a[ii*2+3]);
    if( v==2 ) break;
    cnt += v;
  }
  if( v!=2 ){
................................................................................
  if( v==2 ){
    sqlite3_result_int(context, 1);
  }else if( ((v+cnt)&1)==0 ){
    sqlite3_result_int(context, 0);
  }else{
    sqlite3_result_int(context, 2);
  }
  sqlite3_free(p1);
}

/* Forward declaration */
static int geopolyOverlap(GeoPoly *p1, GeoPoly *p2);

/*
** SQL function:    geopoly_within(P1,P2)
**
** Return +2 if P1 and P2 are the same polygon
** Return +1 if P2 is contained within P1
** Return 0 if any part of P2 is on the outside of P1
**
*/
static void geopolyWithinFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  GeoPoly *p1 = geopolyFuncParam(context, argv[0], 0);
  GeoPoly *p2 = geopolyFuncParam(context, argv[1], 0);
  if( p1 && p2 ){
    int x = geopolyOverlap(p1, p2);
    if( x<0 ){
      sqlite3_result_error_nomem(context);
    }else{
      sqlite3_result_int(context, x==2 ? 1 : x==4 ? 2 : 0);
    }

  }

  sqlite3_free(p1);
  sqlite3_free(p2);
}

/* Objects used by the overlap algorihm. */
typedef struct GeoEvent GeoEvent;
typedef struct GeoSegment GeoSegment;
typedef struct GeoOverlap GeoOverlap;
struct GeoEvent {
................................................................................
  void **ppArg
){
  if( sqlite3_stricmp(zName, "geopoly_overlap")==0 ){
    *pxFunc = geopolyOverlapFunc;
    *ppArg = 0;
    return SQLITE_INDEX_CONSTRAINT_FUNCTION;
  }
  if( sqlite3_stricmp(zName, "geopoly_within")==0 ){
    *pxFunc = geopolyWithinFunc;
    *ppArg = 0;
    return SQLITE_INDEX_CONSTRAINT_FUNCTION+1;
  }
  return 0;
}

................................................................................
    const char *zName;
  } aFunc[] = {
     { geopolyAreaFunc,          1,    "geopoly_area"             },
     { geopolyBlobFunc,          1,    "geopoly_blob"             },
     { geopolyJsonFunc,          1,    "geopoly_json"             },
     { geopolySvgFunc,          -1,    "geopoly_svg"              },
     { geopolyWithinFunc,        2,    "geopoly_within"           },
     { geopolyContainsPointFunc, 3,    "geopoly_contains_point"   },
     { geopolyOverlapFunc,       2,    "geopoly_overlap"          },
     { geopolyDebugFunc,         1,    "geopoly_debug"            },
     { geopolyBBoxFunc,          1,    "geopoly_bbox"             },
     { geopolyXformFunc,         7,    "geopoly_xform"            },
  };
  int i;
  for(i=0; i<sizeof(aFunc)/sizeof(aFunc[0]) && rc==SQLITE_OK; i++){