Documentation Source Text

<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

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

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

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

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

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:

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