1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
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
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
|
<!DOCTYPE html>
<html><head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<link href="sqlite.css" rel="stylesheet">
<title>The Geopoly Interface To The SQLite R*Tree Module</title>
<!-- path= -->
</head>
<body>
<div class=nosearch>
<a href="index.html">
<img class="logo" src="images/sqlite370_banner.gif" alt="SQLite" border="0">
</a>
<div><!-- IE hack to prevent disappearing logo --></div>
<div class="tagline desktoponly">
Small. Fast. Reliable.<br>Choose any three.
</div>
<div class="menu mainmenu">
<ul>
<li><a href="index.html">Home</a>
<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
<li class='wideonly'><a href='about.html'>About</a>
<li class='desktoponly'><a href="docs.html">Documentation</a>
<li class='desktoponly'><a href="download.html">Download</a>
<li class='wideonly'><a href='copyright.html'>License</a>
<li class='desktoponly'><a href="support.html">Support</a>
<li class='desktoponly'><a href="prosupport.html">Purchase</a>
<li class='search' id='search_menubutton'>
<a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
</ul>
</div>
<div class="menu submenu" id="submenu">
<ul>
<li><a href='about.html'>About</a>
<li><a href='docs.html'>Documentation</a>
<li><a href='download.html'>Download</a>
<li><a href='support.html'>Support</a>
<li><a href='prosupport.html'>Purchase</a>
</ul>
</div>
<div class="searchmenu" id="searchmenu">
<form method="GET" action="search">
<select name="s" id="searchtype">
<option value="d">Search Documentation</option>
<option value="c">Search Changelog</option>
</select>
<input type="text" name="q" id="searchbox" value="">
<input type="submit" value="Go">
</form>
</div>
</div>
<script>
function toggle_div(nm) {
var w = document.getElementById(nm);
if( w.style.display=="block" ){
w.style.display = "none";
}else{
w.style.display = "block";
}
}
function toggle_search() {
var w = document.getElementById("searchmenu");
if( w.style.display=="block" ){
w.style.display = "none";
} else {
w.style.display = "block";
setTimeout(function(){
document.getElementById("searchbox").focus()
}, 30);
}
}
function div_off(nm){document.getElementById(nm).style.display="none";}
window.onbeforeunload = function(e){div_off("submenu");}
/* Disable the Search feature if we are not operating from CGI, since */
/* Search is accomplished using CGI and will not work without it. */
if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
document.getElementById("search_menubutton").style.display = "none";
}
/* Used by the Hide/Show button beside syntax diagrams, to toggle the */
function hideorshow(btn,obj){
var x = document.getElementById(obj);
var b = document.getElementById(btn);
if( x.style.display!='none' ){
x.style.display = 'none';
b.innerHTML='show';
}else{
x.style.display = '';
b.innerHTML='hide';
}
return false;
}
var antiRobot = 0;
function antiRobotGo(){
if( antiRobot!=3 ) return;
antiRobot = 7;
var j = document.getElementById("mtimelink");
if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
}
function antiRobotDefense(){
document.body.onmousedown=function(){
antiRobot |= 2;
antiRobotGo();
document.body.onmousedown=null;
}
document.body.onmousemove=function(){
antiRobot |= 2;
antiRobotGo();
document.body.onmousemove=null;
}
setTimeout(function(){
antiRobot |= 1;
antiRobotGo();
}, 100)
antiRobotGo();
}
antiRobotDefense();
</script>
<div class=fancy>
<div class=nosearch>
<div class="fancy_title">
The Geopoly Interface To The SQLite R*Tree Module
</div>
<div class="fancy_toc">
<a onclick="toggle_toc()">
<span class="fancy_toc_mark" id="toc_mk">►</span>
Table Of Contents
</a>
<div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div>
<div class="fancy-toc2"><a href="#geojson">1.1. GeoJSON</a></div>
<div class="fancy-toc2"><a href="#binary_storage_format">1.2. Binary storage format</a></div>
<div class="fancy-toc1"><a href="#using_the_geopoly_extension">2. Using The Geopoly Extension</a></div>
<div class="fancy-toc2"><a href="#queries">2.1. Queries</a></div>
<div class="fancy-toc1"><a href="#special_functions">3. Special Functions</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_overlap_p1_p2_function">3.1. The geopoly_overlap(P1,P2) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_within_p1_p2_function">3.2. The geopoly_within(P1,P2) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_area_p_function">3.3. The geopoly_area(P) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_blob_p_function">3.4. The geopoly_blob(P) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_json_p_function">3.5. The geopoly_json(P) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_svg_p_function">3.6. The geopoly_svg(P,...) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_bbox_p_and_geopoly_group_bbox_p_functions">3.7. The geopoly_bbox(P) and geopoly_group_bbox(P) Functions</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_contains_point_p_x_y_function">3.8. The geopoly_contains_point(P,X,Y) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_xform_p_a_b_c_d_e_f_function">3.9. The geopoly_xform(P,A,B,C,D,E,F) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_regular_x_y_r_n_function">3.10. The geopoly_regular(X,Y,R,N) Function</a></div>
<div class="fancy-toc2"><a href="#the_geopoly_ccw_j_function">3.11. The geopoly_ccw(J) Function</a></div>
<div class="fancy-toc1"><a href="#implementation_details">4. Implementation Details</a></div>
<div class="fancy-toc2"><a href="#binary_encoding_of_polygons">4.1. Binary Encoding of Polygons</a></div>
<div class="fancy-toc2"><a href="#shadow_tables">4.2. Shadow Tables</a></div>
</div>
</div>
<script>
function toggle_toc(){
var sub = document.getElementById("toc_sub")
var mk = document.getElementById("toc_mk")
if( sub.style.display!="block" ){
sub.style.display = "block";
mk.innerHTML = "▼";
} else {
sub.style.display = "none";
mk.innerHTML = "►";
}
}
</script>
</div>
<h1 id="overview"><span>1. </span>Overview</h1>
<p>
The Geopoly module is an alternative interface to the <a href="rtree.html">R-Tree extension</a> that uses
the <a href="http://geojson.org">GeoJSON</a> notation
(<a href="https://tools.ietf.org/html/rfc7946">RFC-7946</a>) to describe two-dimensional
polygons. Geopoly includes functions for detecting when one polygon is
contained within or overlaps with another, for computing the
area enclosed by a polygon, for doing linear transformations of polygons,
for rendering polygons as
<a href="https://en.wikipedia.org/wiki/Scalable_Vector_Graphics">SVG</a>, and other
similar operations.
</p><p>
The source code for Geopoly is included in the <a href="amalgamation.html">amalgamation</a>. However,
depending on configuration options and the a particular version of SQLite
you are using, the Geopoly extension may or may not be enabled by default.
To ensure that Geopoly is enabled for your build,
add the <a href="compile.html#enable_geopoly">-DSQLITE_ENABLE_GEOPOLY=1</a> compile-time option.
</p><p>
Geopoly operates on "simple" polygons - that is, polygons for which
the boundary does not intersect itself. Geopoly thus extends the capabilities
of the <a href="rtree.html">R-Tree extension</a> which can only deal with rectangular areas.
On the other hand, the <a href="rtree.html">R-Tree extension</a> is
able to handle between 1 and 5 coordinate dimensions, whereas Geopoly is restricted
to 2-dimensional shapes only.
</p><p>
Each polygon in the Geopoly module can be associated with an arbitrary
number of auxiliary data fields.
</p><h2 id="geojson"><span>1.1. </span>GeoJSON</h2>
<p>The <a href="https://tools.ietf.org/html/rfc7946">GeoJSON standard</a> is syntax for
exchanging geospatial information using JSON. GeoJSON is a rich standard
that can describe nearly any kind of geospatial content.
</p><p>The Geopoly module only understands
a small subset of GeoJSON, but a critical subset.
In particular, GeoJSON understands
the JSON array of vertexes that describes a simple polygon.
</p><p>A polygon is defined by its vertexes.
Each vertex is a JSON array of two numeric values which are the
X and Y coordinates of the vertex.
A polygon is a JSON array of at least four of these vertexes,
and hence is an array of arrays.
The first and last vertex in the array must be the same.
The polygon follows the right-hand rule: When tracing a line from
one vertex to the next, the area to the right of the line is outside
of the polygon and the area to the left is inside the polygon.
In other words, the net rotation of the vertexes is counter-clockwise.
</p><p>
For example, the following JSON describes an isosceles triangle, sitting
on the X axis and with an area of 0.5:
</p><div class="codeblock"><pre>[[0,0],[1,0],[0.5,1],[0,0]]
</pre></div>
<p>
A triangle has three vertexes, but the GeoJSON description of the triangle
has 4 vertexes because the first and last vertex are duplicates.
</p><h2 id="binary_storage_format"><span>1.2. </span>Binary storage format</h2>
<p>
Internally, Geopoly stores polygons in a binary format - an SQL BLOB.
Details of the binary format are given below.
All of the Geopoly interfaces are able to accept polygons in either the
GeoJSON format or in the binary format.
</p><h1 id="using_the_geopoly_extension"><span>2. </span>Using The Geopoly Extension</h1>
<p>
A geopoly table is created as follows:
</p><div class="codeblock"><pre>CREATE VIRTUAL TABLE newtab USING geopoly(a,b,c);
</pre></div>
<p>
The statement above creates a new geopoly table named "newtab".
Every geopoly table contains a built-in integer "rowid" column
and a "_shape" column that contains
the polygon associated with that row of the table.
The example above also defines three auxiliary data columns
named "a", "b", and "c" that can store whatever additional
information the application needs to associate
with each polygon. If there is no need to store auxiliary
information, the list of auxiliary columns can be omitted.
</p><p>
Store new polygons in the table using ordinary INSERT statements:
</p><div class="codeblock"><pre>INSERT INTO newtab(_shape) VALUES('[[0,0],[1,0],[0.5,1],[0,0]]');
</pre></div>
<p>
UPDATE and DELETE statements work similarly.
</p><h2 id="queries"><span>2.1. </span>Queries</h2>
<p>
To query the geopoly table using an indexed geospatial search,
use one of the functions geopoly_overlap()
or geopoly_within() as a boolean function in the WHERE clause,
with the "_shape" column as the first argument to the function.
For example:
</p><div class="codeblock"><pre>SELECT * FROM newtab WHERE geopoly_overlap(_shape, $query_polygon);
</pre></div>
<p>
The previous example will return every row for which the _shape
overlaps the polygon in the $query_polygon parameter. The
geopoly_within() function works similarly, but only returns rows for
which the _shape is completely contained within $query_polygon.
</p><p>
Queries (and also DELETE and UPDATE statements) in which the WHERE
clause contains a bare geopoly_overlap() or geopoly_within() function
make use of the underlying R*Tree data structures for a fast lookup that
only has to examine a subset of the rows in the table. The number of
rows examines depends, of course, on the size of the $query_polygon.
Large $query_polygons will normally need to look at more rows than small
ones.
</p><p>
Queries against the rowid of a geopoly table are also very quick, even
for tables with a vast number of rows.
However, none of the auxiliary data columns are indexes, and so queries
against the auxiliary data columns will involve a full table scan.
</p><h1 id="special_functions"><span>3. </span>Special Functions</h1>
<p>
The geopoly module defines several new SQL functions that are useful for
dealing with polygons. All polygon arguments to these functions can be
either the GeoJSON format or the internal binary format.
<a name="goverlap"></a>
</p><h2 id="the_geopoly_overlap_p1_p2_function"><span>3.1. </span>The geopoly_overlap(P1,P2) Function</h2>
<p>
If P1 and P2 are both polygons, then the geopoly_overlap(P1,P2) function returns
a non-zero integer if there is any overlap between P1 and P2, or it returns
zero if P1 and P2 completely disjoint.
If either P1 or P2 is not a polygon, this routine returns NULL.
</p><p>
The geopoly_overlap(P1,P2) function is special in that the geopoly virtual
table knows how to use R*Tree indexes to optimize queries in which the
WHERE clause uses geopoly_overlap() as a boolean function. Only the
geopoly_overlap(P1,P2) and geopoly_within(P1,P2) functions have this
capability.
<a name="gwithin"></a>
</p><h2 id="the_geopoly_within_p1_p2_function"><span>3.2. </span>The geopoly_within(P1,P2) Function</h2>
<p>
If P1 and P2 are both polygons, then the geopoly_within(P1,P2) function returns
a non-zero integer if P1 is completely contained within P2, or it returns zero
if any part of P1 is outside of P2. If P1 and P2 are the same polygon, this routine
returns non-zero.
If either P1 or P2 is not a polygon, this routine returns NULL.
</p><p>
The geopoly_within(P1,P2) function is special in that the geopoly virtual
table knows how to use R*Tree indexes to optimize queries in which the
WHERE clause uses geopoly_within() as a boolean function. Only the
geopoly_within(P1,P2) and geopoly_overlap(P1,P2) functions have this
capability.
<a name="garea"></a>
</p><h2 id="the_geopoly_area_p_function"><span>3.3. </span>The geopoly_area(P) Function</h2>
<p>
If P is a polygon, then geopoly_area(P) returns the area enclosed by
that polygon. If P is not a polygon, geopoly_area(P) returns NULL.
<a name="gblob"></a>
</p><h2 id="the_geopoly_blob_p_function"><span>3.4. </span>The geopoly_blob(P) Function</h2>
<p>
If P is a polygon, then geopoly_blob(P) returns the binary encoding
of that polygon as a BLOB.
If P is not a polygon, geopoly_blob(P) returns NULL.
<a name="gjson"></a>
</p><h2 id="the_geopoly_json_p_function"><span>3.5. </span>The geopoly_json(P) Function</h2>
<p>
If P is a polygon, then geopoly_json(P) returns the GeoJSON representation
of that polygon as a TEXT string.
If P is not a polygon, geopoly_json(P) returns NULL.
<a name="gsvg"></a>
</p><h2 id="the_geopoly_svg_p_function"><span>3.6. </span>The geopoly_svg(P,...) Function</h2>
<p>
If P is a polygon, then geopoly_svg(P,...) returns a text string which is a
<a href="https://en.wikipedia.org/wiki/Scalable_Vector_Graphics">Scalable Vector Graphics (SVG)</a>
representation of that polygon. If there is more one argument, then second
and subsequent arguments are added as attributes to each SVG glyph. For example:
</p><div class="codeblock"><pre>SELECT geopoly_svg($polygon,'class="poly"','style="fill:blue;"');
</pre></div>
<p>
If P is not a polygon, geopoly_svg(P,...) returns NULL.
</p><p>
Note that geopoly uses a traditional right-handed cartesian coordinate system
with the origin at the lower left, whereas SVG uses a left-handed coordinate
system with the origin at the upper left. The geopoly_svg() routine makes no
attempt to transform the coordinate system, so the displayed images are shown
in mirror image and rotated. If that is undesirable, the geopoly_xform() routine
can be used to transform the output from cartesian to SVG coordinates prior to
passing the polygons into geopoly_svg().
<a name="gbbox"></a>
</p><h2 id="the_geopoly_bbox_p_and_geopoly_group_bbox_p_functions"><span>3.7. </span>The geopoly_bbox(P) and geopoly_group_bbox(P) Functions</h2>
<p>
If P is a polygon, then geopoly_bbox(P) returns a new polygon that is
the smallest (axis-aligned) rectangle completely enclosing P.
If P is not a polygon, geopoly_bbox(P) returns NULL.
</p><p>
The geopoly_group_bbox(P) function is an aggregate version of geopoly_bbox(P).
The geopoly_group_bbox(P) function returns the smallest rectangle that will
enclose all P values seen during aggregation.
<a name="gpoint"></a>
</p><h2 id="the_geopoly_contains_point_p_x_y_function"><span>3.8. </span>The geopoly_contains_point(P,X,Y) Function</h2>
<p>
If P is a polygon, then geopoly_contains_point(P,X,Y) returns a
non-zero integer if and only
if the coordinate X,Y is inside or on the boundary of the polygon P.
If P is not a polygon, geopoly_contains_point(P,X,Y) returns NULL.
<a name="xform"></a>
</p><h2 id="the_geopoly_xform_p_a_b_c_d_e_f_function"><span>3.9. </span>The geopoly_xform(P,A,B,C,D,E,F) Function</h2>
<p>
The geopoly_xform(P,A,B,C,D,E,F) function returns a new polygon that is an
affine transformation of the polygon P and where the transformation
is defined by values A,B,C,D,E,F. If P is not a valid polygon, this
routine returns NULL.
</p><p>
The transformation converts each vertex of the polygon according to the
following formula:
</p><div class="codeblock"><pre>x1 = A*x0 + B*y0 + E
y1 = C*x0 + D*y0 + F
</pre></div>
<p>
So, for example, to move a polygon by some amount DX, DY without changing
its shape, use:
</p><div class="codeblock"><pre>geopoly_xform($polygon, 1, 0, 0, 1, $DX, $DY)
</pre></div>
<p>
To rotate a polygon by R radians around the point 0, 0:
</p><div class="codeblock"><pre>geopoly_xform($polygon, cos($R), sin($R), -sin($R), cos($R), 0, 0)
</pre></div>
<p>
Note that a transformation that flips the polygon might cause the
order of vertexes to be reversed. In other words, the transformation
might cause the vertexes to circulate in clockwise order instead of
counter-clockwise. This can be corrected by sending the result
through the <a href="geopoly.html#ccw">geopoly_ccw()</a> function after transformation.
<a name="regpoly"></a>
</p><h2 id="the_geopoly_regular_x_y_r_n_function"><span>3.10. </span>The geopoly_regular(X,Y,R,N) Function</h2>
<p>
The geopoly_regular(X,Y,R,N) function returns a convex, simple, regular,
equilateral, equiangular polygon with N sides, centered at X,Y, and with
a circumradius of R. Or, if R is negative or if N is less than 3, the
function returns NULL. The N value is capped at 1000 so that the routine
will never render a polygon with more than 1000 sides even if the N value
is larger than 1000.
</p><p>
As an example, the following graphic:
</p><blockquote>
<svg width="600" height="300" style="border:1px solid black">
<polyline points="140.003,100 80.0019,134.644 80.0019,65.3565 140.003,100" style="fill:none;stroke:red;stroke-width:2"></polyline> <text x="100" y="106" alignment-baseline="central" text-anchor="middle">3</text>
<polyline points="240.003,100 200,140.003 159.997,100 200,59.9973 240.003,100" style="fill:none;stroke:orange;stroke-width:2"></polyline> <text x="200" y="106" alignment-baseline="central" text-anchor="middle">4</text>
<polyline points="340.003,100 312.358,138.042 267.637,123.511 267.637,76.4893 312.358,61.9583 340.003,100" style="fill:none;stroke:green;stroke-width:2"></polyline> <text x="300" y="106" alignment-baseline="central" text-anchor="middle">5</text>
<polyline points="440.003,100 419.998,134.644 380.002,134.644 359.997,100 380.002,65.3565 419.998,65.3565 440.003,100" style="fill:none;stroke:blue;stroke-width:2"></polyline> <text x="400" y="106" alignment-baseline="central" text-anchor="middle">6</text>
<polyline points="540.003,100 524.94,131.276 491.101,138.995 463.959,117.353 463.959,82.6471 491.101,61.005 524.94,68.7243 540.003,100" style="fill:none;stroke:purple;stroke-width:2"></polyline> <text x="500" y="106" alignment-baseline="central" text-anchor="middle">7</text>
<polyline points="140.003,200 128.286,228.286 100,240.003 71.7143,228.286 59.9973,200 71.7143,171.714 100,159.997 128.286,171.714 140.003,200" style="fill:none;stroke:red;stroke-width:2"></polyline> <text x="100" y="206" alignment-baseline="central" text-anchor="middle">8</text>
<polyline points="240.003,200 232.363,223.511 212.358,238.042 187.642,238.042 167.637,223.511 159.997,200 167.637,176.489 187.642,161.958 212.358,161.958 232.363,176.489 240.003,200" style="fill:none;stroke:orange;stroke-width:2"></polyline> <text x="200" y="206" alignment-baseline="central" text-anchor="middle">10</text>
<polyline points="340.003,200 334.644,219.998 319.998,234.644 300,240.003 280.002,234.644 265.356,219.998 259.997,200 265.356,180.002 280.002,165.356 300,159.997 319.998,165.356 334.644,180.002 340.003,200" style="fill:none;stroke:green;stroke-width:2"></polyline> <text x="300" y="206" alignment-baseline="central" text-anchor="middle">12</text>
<polyline points="440.003,200 436.956,215.305 428.286,228.286 415.305,236.956 400,240.003 384.695,236.956 371.714,228.286 363.044,215.305 359.997,200 363.044,184.695 371.714,171.714 384.695,163.044 400,159.997 415.305,163.044 428.286,171.714 436.956,184.695 440.003,200" style="fill:none;stroke:blue;stroke-width:2"></polyline> <text x="400" y="206" alignment-baseline="central" text-anchor="middle">16</text>
<polyline points="540.003,200 538.042,212.358 532.363,223.511 523.511,232.363 512.358,238.042 500,240.003 487.642,238.042 476.489,232.363 467.637,223.511 461.958,212.358 459.997,200 461.958,187.642 467.637,176.489 476.489,167.637 487.642,161.958 500,159.997 512.358,161.958 523.511,167.637 532.363,176.489 538.042,187.642 540.003,200" style="fill:none;stroke:purple;stroke-width:2"></polyline> <text x="500" y="206" alignment-baseline="central" text-anchor="middle">20</text>
</svg>
</blockquote>
<p>Was generated by this script:
</p><div class="codeblock"><pre>SELECT '<svg width="600" height="300">';
WITH t1(x,y,n,color) AS (VALUES
(100,100,3,'red'),
(200,100,4,'orange'),
(300,100,5,'green'),
(400,100,6,'blue'),
(500,100,7,'purple'),
(100,200,8,'red'),
(200,200,10,'orange'),
(300,200,12,'green'),
(400,200,16,'blue'),
(500,200,20,'purple')
)
SELECT
geopoly_svg(geopoly_regular(x,y,40,n),
printf('style="fill:none;stroke:%s;stroke-width:2"',color))
|| printf(' <text x="%d" y="%d" alignment-baseline="central" text-anchor="middle">%d</text>',x,y+6,n)
FROM t1;
SELECT '</svg>';
</pre></div>
<a name="ccw"></a>
<h2 id="the_geopoly_ccw_j_function"><span>3.11. </span>The geopoly_ccw(J) Function</h2>
<p>The geopoly_ccw(J) function returns the polygon J with counter-clockwise (CCW) rotation.
</p><p>
<a href="https://tools.ietf.org/html/rfc7946">RFC-7946</a> requires that polygons use CCW rotation.
But the spec also observes that many legacy GeoJSON files do not following the spec and
contain polygons with clockwise (CW) rotation. The geopoly_ccw() function is useful for
applications that are reading legacy GeoJSON scripts. If the input to geopoly_ccw() is
a correctly-formatted polygon, then no changes are made. However, if the circulation of
the input polygon is backwards, then geopoly_ccw() reverses the circulation order so that
it conforms to the spec and so that it will work correctly with the Geopoly module.
</p><h1 id="implementation_details"><span>4. </span>Implementation Details</h1>
<p>The geopoly module is an extension to the <a href="rtree.html">R-Tree extension</a>. Geopoly
uses the same underlying logic and shadow tables as the <a href="rtree.html">R-Tree extension</a>.
Geopoly merely presents a different interface, and provides some extra logic
to compute polygon decoding, overlap, and containment.
</p><h2 id="binary_encoding_of_polygons"><span>4.1. </span>Binary Encoding of Polygons</h2>
<p>
Geopoly stores all polygons internally using a binary format. A binary
polygon consists of a 4-byte header following by an array of coordinate
pairs in which each dimension of each coordinate is a 32-bit floating point
number.
</p><p>
The first byte of the header is a flag byte. The least significant bit
of the flag byte determines whether the coordinate pairs that follow the
header are stored big-endian or little-endian. A value of 0 for the least
significant bit means big-endian and a value of 1 means little endian.
Other bits of the first byte in the header are reserved for future expansion.
</p><p>
The next three bytes in the header record the number of vertexes in the polygon
as a big-endian integer. Thus there is an upper bound of about 16 million
vertexes per polygon.
</p><p>
Following the header is the array of coordinate pairs. Each coordinate is
a 32-bit floating point number. The use of 32-bit floating point values for
coordinates means that any point on the earth's surface can be mapped with
a resolution of approximately 2.5 meters. Higher resolutions are of course
possible if the map is restricted to a single continent or country.
Note that the resolution of coordinates in the geopoly module is similar
in magnitude to daily movement of points on the earth's surface due to
tidal forces.
</p><p>
The list of coordinates in the binary format contains no redundancy.
The last coordinate is not a repeat of the first as it is with GeoJSON.
Hence, there is always one fewer coordinate pair in the binary representation of
a polygon compared to the GeoJSON representation.
</p><h2 id="shadow_tables"><span>4.2. </span>Shadow Tables</h2>
<p>
The geopoly module is built on top of the <a href="rtree.html">R-Tree extension</a> and uses the
same underlying shadow tables and algorithms. For indexing purposes, each
polygon is represented in the shadow tables as a rectangular bounding box.
The underlying R-Tree implementation uses bounding boxes to limit the search
space. Then the geoploy_overlap() and/or geopoly_within() routines further
refine the search to the exact answer.
</p><p align="center"><small><i>This page last modified on <a href="https://sqlite.org/docsrc/honeypot" id="mtimelink" data-href="https://sqlite.org/docsrc/finfo/pages/geopoly.in?m=7b64a47e71">2023-12-05 14:43:20</a> UTC </small></i></p>
|
