/ Check-in [6eb5d09b]
Login

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

Overview
Comment:Provide the two-argument geopoly_within(P1,P2) routine that determines if polygon P2 is contained within polygon P1. Make this function available to the query planner for optimized rtree lookups. Update the visual01.txt script to verify that the new functionality actually works.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-geopoly
Files: files | file ages | folders
SHA3-256:6eb5d09b7f9d9bf8edbf993dccc2e2f702b95ba96cf68445609feb0ccc3ac0f7
User & Date: drh 2018-08-25 19:51:49
Context
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
19:51
Provide the two-argument geopoly_within(P1,P2) routine that determines if polygon P2 is contained within polygon P1. Make this function available to the query planner for optimized rtree lookups. Update the visual01.txt script to verify that the new functionality actually works. check-in: 6eb5d09b user: drh tags: rtree-geopoly
18:57
Fix a harmless compiler warning. check-in: d49be983 user: drh tags: rtree-geopoly
Changes
Hide Diffs Unified Diffs Ignore Whitespace 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
619


620
621
622
623
624
625
626
....
1215
1216
1217
1218
1219
1220
1221

1222
1223
1224
1225
1226
1227
1228
1229
1230

1231
1232
1233
1234
1235
1236
1237

1238
1239
1240
1241
1242
1243
1244
....
1428
1429
1430
1431
1432
1433
1434





1435
1436
1437
1438
1439
1440
1441
....
1469
1470
1471
1472
1473
1474
1475

1476
1477
1478
1479
1480
1481
1482
  }
  y = y1 + (y2-y1)*(x0-x1)/(x2-x1);
  if( y0==y ) return 2;
  if( y0<y ) return 1;
  return 0;
}




/*
** SQL function:    geopoly_within(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 geopolyWithinFunc(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  GeoPoly *p = geopolyFuncParam(context, argv[0], 0);


  double x0 = sqlite3_value_double(argv[1]);
  double y0 = sqlite3_value_double(argv[2]);
  if( p ){
    int v = 0;
    int cnt = 0;
    int ii;
    for(ii=0; ii<p->nVertex-1; ii++){
      v = pointBeneathLine(x0,y0,p->a[ii*2],p->a[ii*2+1],
                                 p->a[ii*2+2],p->a[ii*2+3]);
      if( v==2 ) break;
      cnt += v;
    }
    if( v!=2 ){
      v = pointBeneathLine(x0,y0,p->a[ii*2],p->a[ii*2+1],
                                 p->a[0],p->a[1]);
    }
    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(p);
  }            


}

/* Objects used by the overlap algorihm. */
typedef struct GeoEvent GeoEvent;
typedef struct GeoSegment GeoSegment;
typedef struct GeoOverlap GeoOverlap;
struct GeoEvent {
................................................................................
    if( p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_FUNCTION ){
      iFuncTerm = ii;
    }
  }

  if( iRowidTerm>=0 ){
    pIdxInfo->idxNum = 1;

    pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1;
    pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1;
    pIdxInfo->estimatedCost = 30.0;
    pIdxInfo->estimatedRows = 1;
    pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
    return SQLITE_OK;
  }
  if( iFuncTerm>=0 ){
    pIdxInfo->idxNum = 2;

    pIdxInfo->aConstraintUsage[iFuncTerm].argvIndex = 1;
    pIdxInfo->aConstraintUsage[iFuncTerm].omit = 0;
    pIdxInfo->estimatedCost = 300.0;
    pIdxInfo->estimatedRows = 10;
    return SQLITE_OK;
  }
  pIdxInfo->idxNum = 3;

  pIdxInfo->estimatedCost = 3000000.0;
  pIdxInfo->estimatedRows = 100000;
  return SQLITE_OK;
}


/* 
................................................................................
  void **ppArg
){
  if( sqlite3_stricmp(zName, "geopoly_overlap")==0 ){
    *pxFunc = geopolyOverlapFunc;
    *ppArg = 0;
    return SQLITE_INDEX_CONSTRAINT_FUNCTION;
  }





  return 0;
}


static sqlite3_module geopolyModule = {
  2,                          /* iVersion */
  geopolyCreate,              /* xCreate - create a table */
................................................................................
    int nArg;
    const char *zName;
  } aFunc[] = {
     { geopolyAreaFunc,          1,    "geopoly_area"     },
     { geopolyBlobFunc,          1,    "geopoly_blob"     },
     { geopolyJsonFunc,          1,    "geopoly_json"     },
     { geopolySvgFunc,          -1,    "geopoly_svg"      },

     { geopolyWithinFunc,        3,    "geopoly_within"   },
     { geopolyOverlapFunc,       2,    "geopoly_overlap"  },
     { geopolyDebugFunc,         1,    "geopoly_debug"    },
     { geopolyBBoxFunc,          1,    "geopoly_bbox"     },
     { geopolyXformFunc,         7,    "geopoly_xform"    },
  };
  int 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
608

609
610
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
....
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
....
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
....
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
  }
  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 ){
      v = pointBeneathLine(x0,y0,p1->a[ii*2],p1->a[ii*2+1],
                                 p1->a[0],p1->a[1]);
    }
    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 {
................................................................................
    if( p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_FUNCTION ){
      iFuncTerm = ii;
    }
  }

  if( iRowidTerm>=0 ){
    pIdxInfo->idxNum = 1;
    pIdxInfo->idxStr = "rowid";
    pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1;
    pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1;
    pIdxInfo->estimatedCost = 30.0;
    pIdxInfo->estimatedRows = 1;
    pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE;
    return SQLITE_OK;
  }
  if( iFuncTerm>=0 ){
    pIdxInfo->idxNum = 2;
    pIdxInfo->idxStr = "rtree";
    pIdxInfo->aConstraintUsage[iFuncTerm].argvIndex = 1;
    pIdxInfo->aConstraintUsage[iFuncTerm].omit = 0;
    pIdxInfo->estimatedCost = 300.0;
    pIdxInfo->estimatedRows = 10;
    return SQLITE_OK;
  }
  pIdxInfo->idxNum = 3;
  pIdxInfo->idxStr = "fullscan";
  pIdxInfo->estimatedCost = 3000000.0;
  pIdxInfo->estimatedRows = 100000;
  return SQLITE_OK;
}


/* 
................................................................................
  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;
  }
  return 0;
}


static sqlite3_module geopolyModule = {
  2,                          /* iVersion */
  geopolyCreate,              /* xCreate - create a table */
................................................................................
    int nArg;
    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;

Changes to ext/rtree/visual01.txt.

370
371
372
373
374
375
376


377







378
379
380
381
382
383
384
385
386
387
388































































389
       )
  FROM geo1;
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'


.print '<h1>Query</h1>'







.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE geopoly_overlap(_shape, poly);
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'































































.print '</html>'







>
>
|
>
>
>
>
>
>
>











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

370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
       )
  FROM geo1;
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'

.print '<h1>Overlap Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE geopoly_overlap(_shape, poly);
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE geopoly_overlap(_shape, poly);
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'

.print '<h1>Within Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE geopoly_within(_shape, poly);
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE geopoly_within(_shape, poly);
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'

.print '<h1>Not Overlap Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE NOT geopoly_overlap(_shape, poly);
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE NOT geopoly_overlap(_shape, poly);
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'

.print '<h1>Not Within Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE NOT geopoly_within(_shape, poly);
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
         printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
       )
  FROM geo1, querypoly
 WHERE NOT geopoly_within(_shape, poly);
SELECT geopoly_svg(poly, 
         printf('style="fill:%s;fill-opacity:0.5;"',clr)
       )
  FROM querypoly;
.print '</svg>'
.print '</html>'