Documentation Source Text

Check-in [81cf14c724]
Login

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

Overview
Comment:Fix typos in the geopoly document.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 81cf14c72443aee1f5ee526a445a8afa51f82f876130bc6ef7e3bab91059d590
User & Date: drh 2018-09-11 22:44:34.560
Context
2018-09-12
10:49
Fix typos in the windowfunctions.html document. (check-in: 221cce4209 user: drh tags: trunk)
2018-09-11
22:44
Fix typos in the geopoly document. (check-in: 81cf14c724 user: drh tags: trunk)
18:17
Updates to the change log. (check-in: 5c91ca999e user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to pages/geopoly.in.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<title>The Geopoly Interface To The SQLite R*Tree Module</title>
<tcl>hd_keywords {geopoly} {Geopoly module}</tcl>
<table_of_contents>

<h1>Overview</h1>

<p>
The Geopoly module is an alternative interface to the [R-Tree extension] that uses
the [http://geojson.org | GeoJSON] notation
([https://tools.ietf.org/html/rfc7946 | RFC-7946]) 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 trasformations of polygons,
for rendering polygons as
[https://en.wikipedia.org/wiki/Scalable_Vector_Graphics | SVG], and other
similar operations.

<p>
Geopoly operates on "simple" polygons - that is, polygons for which
the boundary does not intersect itself.  Geopoly thus extends the capabilities












|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<title>The Geopoly Interface To The SQLite R*Tree Module</title>
<tcl>hd_keywords {geopoly} {Geopoly module}</tcl>
<table_of_contents>

<h1>Overview</h1>

<p>
The Geopoly module is an alternative interface to the [R-Tree extension] that uses
the [http://geojson.org | GeoJSON] notation
([https://tools.ietf.org/html/rfc7946 | RFC-7946]) 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
[https://en.wikipedia.org/wiki/Scalable_Vector_Graphics | SVG], and other
similar operations.

<p>
Geopoly operates on "simple" polygons - that is, polygons for which
the boundary does not intersect itself.  Geopoly thus extends the capabilities
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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>
For example, the following JSON describes an isosceles triangle, sitting
on the X access and with an area of 0.5:

<codeblock>
&#91;&#91;0,0],&#91;1,0],&#91;0.5,1],&#91;0,0]]
</codeblock>

<p>
A triangle has three vertexes, but the GeoJSON description of the triangle







|







47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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>
For example, the following JSON describes an isosceles triangle, sitting
on the X axis and with an area of 0.5:

<codeblock>
&#91;&#91;0,0],&#91;1,0],&#91;0.5,1],&#91;0,0]]
</codeblock>

<p>
A triangle has three vertexes, but the GeoJSON description of the triangle
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
<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>
Querys (and also DELETE and UPDATE statements) in which the WHERE
clause contains a bare geopoly_overlap() or geopoly_within() function
make use of the underly 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.








|







115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
<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>
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 underly 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.

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
<p>
If P1 and P2 are both polygons, then the geopoly_overlap(P1,P2) function returns
true if there is any overlap between P1 and P2, or it returns false if P1 and P2
completely disjoint.
If either P1 or P2 is not a polygon, this routine returns NULL.

<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.

<tcl>hd_fragment gwithin geopoly_within</tcl>
<h2>The geopoly_within(P1,P2) Function</h2>

<p>
If P1 and P2 are both polygons, then the geopoly_within(P1,P2) function returns
true if P2 is completely contained within P1, or it returns false if any part of
P2 is outside of P1.  If P1 and P2 are the same polygon, this routine returns true.
If either P1 or P2 is not a polygon, this routine returns NULL.

<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.

<tcl>hd_fragment garea geopoly_area</tcl>
<h2>The geopoly_area(P) Function</h2>







|















|







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
<p>
If P1 and P2 are both polygons, then the geopoly_overlap(P1,P2) function returns
true if there is any overlap between P1 and P2, or it returns false if P1 and P2
completely disjoint.
If either P1 or P2 is not a polygon, this routine returns NULL.

<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.

<tcl>hd_fragment gwithin geopoly_within</tcl>
<h2>The geopoly_within(P1,P2) Function</h2>

<p>
If P1 and P2 are both polygons, then the geopoly_within(P1,P2) function returns
true if P2 is completely contained within P1, or it returns false if any part of
P2 is outside of P1.  If P1 and P2 are the same polygon, this routine returns true.
If either P1 or P2 is not a polygon, this routine returns NULL.

<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.

<tcl>hd_fragment garea geopoly_area</tcl>
<h2>The geopoly_area(P) Function</h2>
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
If P is not a polygon, geopoly_blob(P) returns NULL.

<tcl>hd_fragment gjson geopoly_json</tcl>
<h2>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 TEPT string.
If P is not a polygon, geopoly_json(P) returns NULL.

<tcl>hd_fragment gsvg geopoly_svg</tcl>
<h2>The geopoly_svg(P,...) Function</h2>

<p>
If P is a polygon, then geopoly_svg(P,...) returns a text string which is a







|







188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
If P is not a polygon, geopoly_blob(P) returns NULL.

<tcl>hd_fragment gjson geopoly_json</tcl>
<h2>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.

<tcl>hd_fragment gsvg geopoly_svg</tcl>
<h2>The geopoly_svg(P,...) Function</h2>

<p>
If P is a polygon, then geopoly_svg(P,...) returns a text string which is a
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
can be used to transform the output from cartesian to SVG coordinates prior to
passing the polygons into geopoly_svg().

<tcl>hd_fragment gbbox geopoly_bbox</tcl>
<h2>The geopoly_bbox(P) Function</h2>

<p>
If P is a polygon, then geopoly_bbox(P) returns the a new polygon that is
the smallest rectangle completely enclosing P.
If P is not a polygon, geopoly_bbox(P) returns NULL.

<tcl>hd_fragment gpoint geopoly_constains_point</tcl>
<h2>The geopoly_contains_point(P,X,Y) Function</h2>

<p>
If P is a polygon, then geopoly_contains_point(P,X,Y) returns true 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.

<tcl>hd_fragment xform geopoly_xform</tcl>
<h2>The geopoly_xform(P,A,B,C,D,E,F) Function</h2>

<p>
The geopoly_xform(P,A,B,C,D,E,F) returns a new polygon that is a
linear 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>
The transformation converts each vertex of the polygon according to the
following formula:








|
|















|







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
can be used to transform the output from cartesian to SVG coordinates prior to
passing the polygons into geopoly_svg().

<tcl>hd_fragment gbbox geopoly_bbox</tcl>
<h2>The geopoly_bbox(P) Function</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.

<tcl>hd_fragment gpoint geopoly_constains_point</tcl>
<h2>The geopoly_contains_point(P,X,Y) Function</h2>

<p>
If P is a polygon, then geopoly_contains_point(P,X,Y) returns true 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.

<tcl>hd_fragment xform geopoly_xform</tcl>
<h2>The geopoly_xform(P,A,B,C,D,E,F) Function</h2>

<p>
The geopoly_xform(P,A,B,C,D,E,F) returns a new polygon that is a
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>
The transformation converts each vertex of the polygon according to the
following formula:

276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
Geopoly merely presents a different interface, and provides some extra logic
to compute polygon decoding, overlap, and containment.

<h2>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 coordinate
pairs which each dimension of each coordinate is of 32-byte floating point
number.

<p>
The first byte of the header is a flag byte.  The least significant bit
of the flag byte determines whether the coordinate pairs the 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>
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







|
|




|







276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
Geopoly merely presents a different interface, and provides some extra logic
to compute polygon decoding, overlap, and containment.

<h2>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 of 32-byte floating point
number.

<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>
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