Debian Codegraph @

www/geopoly.html

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