The upcoming jOOQ 3.16 will lastly provide help for the varied RDBMS GIS extensions by way of subject #982. That is nice information per se, and will likely be coated in a future weblog publish, when the mixing is prepared. This publish right here is about one thing else.
Including help for such a characteristic is a good supply of procrastination. You see, while you develop a backend library, all you ever do is implement algorithms, API, and different summary stuff. However GIS is completely different. With GIS, a SQL developer like me all of a sudden has entry to a “UI”, and getting access to a “UI” woke the inside programmer little one in me.
I used to be pleasantly shocked that DBeaver, my most well-liked SQL editor, has out of the field help for GIS’s WKT format. E.g. run a question like this:
SELECT st_geomfromtext('polygon((0 0, 2 3, 0 6, -2 3, 0 0))');
The output being
Let’s mess around with GIS
So, naturally, what different factor to do than mess around with it? The obvious subsequent factor to generate could be your favorite brand, which occurs to be very simple to map to polygons. Let’s have a look at just a few GIS options step-by-step. And for this weblog publish, I’ll be utilizing PostGIS, which you will get very simply from docker hub:
WITH
-- These "sprites" are simply reusable 2D polygons, which I declared
-- to keep away from having to cope with the prolonged WKT format
sprites AS (
SELECT
-- We challenge the unique 1x1 sq., and a scaled 4x4 model
s AS sq.,
st_scale(s, 4, 4) AS square4
-- Right here, we're making a sq. referred to as "s"
FROM (VALUES
(st_polygonfromtext('polygon ((0 0, 1 0, 1 1, 0 1, 0 0))'))
) t (s)
)
-- st_union combines 2 polygons right into a multipolygon
SELECT st_union(sq., st_translate(square4, 2, 0))
FROM sprites
The output of the above question is
MULTIPOLYGON (((0 0, 1 0, 1 1, 0 1, 0 0)), ((2 0, 6 0, 6 4, 2 4, 2 0)))
Or, utilizing DBeaver’s visualisation utility:
The st_union isn’t a lot completely different from another set union. Be aware that I’ve translated the bigger sq. 2 models to the correct, so that they don’t overlap. In any other case, the union would have simply been the larger sq..
A polygon describes a set of factors within the 2D quantity aircraft. Making a union of these two units of factors is pure. We will additionally create a distinction of the 2 squares, as a substitute:
WITH
sprites AS (
SELECT
s AS sq.,
st_scale(s, 4, 4) AS square4
FROM (VALUES
(st_polygonfromtext('polygon ((0 0, 1 0, 1 1, 0 1, 0 0))'))
) t (s)
)
SELECT st_difference(square4, sq.)
FROM sprites
Leading to:
POLYGON ((0 4, 4 4, 4 0, 1 0, 1 1, 0 1, 0 4))
Or, visually:
With these easy instruments, we are able to now create all 4 letters of the jOOQ brand. As a reminder, the instruments have been:
st_polygonfromtext: Create a polygon from a WKT textual content illustrationst_scale: Scale any geometry to a brand new measurementst_translate: Translate any geometry to a brand new placest_union: Mix two geometries (or extra, if used as an combination operate)st_difference: Take away one geometry from one other
The GIS API is huge, each in PostGIS in addition to within the ISO/IEC 13249-3:2016 normal model, however these easy instruments shall suffice for now. Let’s have a look at this question:
WITH
-- Creating the 2 squares to work with
sprites AS (
SELECT
s AS sq.,
st_scale(s, 4, 4) AS square4
FROM (VALUES
(st_polygonfromtext('polygon ((0 0, 1 0, 1 1, 0 1, 0 0))'))
) t (s)
),
-- All of the 4 letters j, o1, o2, q of the jOOQ brand
letters AS (
SELECT
-- The letter j
st_difference(
st_difference(
st_difference(
square4,
st_translate(st_scale(sq., 2, 3), 1, 1)
),
st_translate(st_scale(sq., 1, 2), 0, 2)
),
st_translate(st_scale(sq., 1, 0.5), 3, 2.5)
) AS j,
-- The letter o
st_difference(square4, st_translate(sq., 1, 1)) AS o1,
-- The letter o
st_difference(square4, st_translate(sq., 2, 2)) AS o2,
-- The letter q
st_union(
st_difference(
square4,
st_translate(st_scale(sq., 2, 2), 1, 1)
),
st_translate(st_scale(sq., 1, 2.5), 1.5, -1)
) as q
FROM sprites
)
SELECT
-- Mix all of the 4 letters
st_union(v)
FROM
letters,
-- Organize the 4 letters subsequent to one another
LATERAL (VALUES
(st_translate(j, 0, 5)),
(st_translate(o1, 5, 5)),
(o2),
(st_translate(q, 5, 0))
) t (v);
This produces:
Neat, huh?
Subsequent step: The Mandelbrot Set
A pure subsequent step for any procrastinator is to generate the Mandelbrot set. To organize ourselves for what’s behind the Mandelbrot, take a look at this neat video (extra procrastination):
There are other ways to calculate it with SQL, right here’s one which I got here up with:
WITH RECURSIVE
-- These are the scale which you could mess around with
dims (r1, r2, i1, i2, s, it, p) AS (
VALUES (
-- The size of the actual axis
-2::float, 1::float,
-- The size of the imaginary axis
-1.5::float, 1.5::float,
-- The step measurement on every axis, per pixel or sprite
0.01::float,
-- The utmost variety of iterations
100,
-- "Infinity", i.e. when to cease
256.0::float
)
),
-- The sq. once more, as earlier than
sprites (s) AS (VALUES
(st_polygonfromtext('polygon ((0 0, 0 1, 1 1, 1 0, 0 0))'))
),
-- The quantity aircraft, as ints
n1 (r, i) AS (
SELECT r, i
FROM
dims,
generate_series((r1 / s)::int, (r2 / s)::int) r,
generate_series((i1 / s)::int, (i2 / s)::int) i
),
-- The quantity aircraft as scaled floats
n2 (r, i) AS (
SELECT r::float * s::float, i::float * s::float
FROM dims, n1
),
-- The recursive calculation of the Mandelbrot formulation
-- zn = (zn-1)^2 + c
l (cr, ci, zr, zi, g, it, p) AS (
SELECT r, i, 0::float, 0::float, 0, it, p FROM n2, dims
UNION ALL
SELECT cr, ci, zr*zr - zi*zi + cr, 2*zr*zi + ci, g + 1, it, p
FROM l
-- The recursions stops once we attain the utmost
WHERE g < it
-- Or, once we attain "infinity"
AND zr*zr + zi*zi < p
),
-- Discover the final calculated worth per level within the
-- complicated quantity aircraft c (cr, ci), discard the others
x (cr, ci, zr, zi, g) AS (
SELECT DISTINCT ON (cr, ci) cr, ci, zr, zi, g
FROM l
ORDER BY cr, ci, g DESC
)
-- Flip each calculated level right into a sq.
SELECT
st_union(
st_translate(sprites.s, spherical(cr / dims.s), spherical(ci / dims.s))
)
FROM x, sprites, dims
-- Retain solely the factors *not* belonging to the Mandelbrot set
-- You can too inverse the equation to retain the factors that
-- belong to the set
WHERE zr*zr + zi*zi > p;
Be aware, I’m utilizing a synthetic “infinity” right here, as a result of:
- That speeds issues up with little noticeable distinction at this zoom scale
- I couldn’t work out how one can make PostgreSQL overflow float operations to drift infinities, like Java or CockroachDB or different IEEE 754 float implementations do. Any assist appreciated, see this Stack Overflow query.
The output is the well-known form
You’ll be able to mess around with this and use completely different values for “dims” to zoom in, e.g.
dims (r1, r2, i1, i2, s, it, p) as (values (
(-0.925-0.032)::float, (-0.925+0.032)::float,
(0.266-0.032)::float, (0.266+0.032)::float,
0.00005::float, 100, 256.0::float)
)
It will generate some actually neat zooms, all with SQL:
Granted, it’s not probably the most environment friendly technique to calculate these items, however that wasn’t the purpose right here, was it?
Sport of Life
I might be nerd-sniped:
And naturally, I needed to settle for that problem too! Now, the Sport of Life is a straightforward “sport” the place we now have the x,y pure quantity aircraft (e.g. “pixels”), and with every coordinate, we affiliate whether or not that “cell” is lifeless or alive. Then, we set up the next algorithm:
- Any stay cell with two or three stay neighbours survives.
- Any lifeless cell with three stay neighbours turns into a stay cell.
- All different stay cells die within the subsequent era. Equally, all different lifeless cells keep lifeless.
No, it’s laborious to “animate” issues in SQL utilizing spatial extensions, in order a workaround, I’ll simply show iterations of 100×100 pixel tiles of the Sport of Life subsequent to one another. The primary iteration is simply the start line, e.g. a random variety of “alive” cells:
WITH RECURSIVE
-- Once more generate a "sprite"a from a sq. polygon
sprites (s) AS (VALUES (
st_polygonfromtext('polygon ((0 0, 0 1, 1 1, 1 0, 0 0))')
)),
-- Generate the x, y quantity aircraft and affiliate a boolean worth
-- with every coordinate, generated randomly.
-- 10% of all cells are alive
m (x, y, b) AS (
SELECT x, y,
CASE WHEN random() > 0.9 THEN 1 ELSE 0 END
FROM
generate_series(1, 100) x,
generate_series(1, 100) y
)
SELECT st_union(st_translate(sprites.s, x::float, y::float))
FROM m, sprites
-- Show solely "alive" cells
WHERE b = 1
It will produce one thing like:
Now, all we now have to do is iterate the sport formulation. Now, recursive SQL has fairly just a few limitations. E.g. I couldn’t get PostgreSQL to combination recursive knowledge, nor self-join the recursive desk to seek out the closest neighbors of any cell. However with window features, that is positively attainable. So right here goes:
WITH RECURSIVE
sprites (s) AS (VALUES (
st_polygonfromtext('polygon ((0 0, 0 1, 1 1, 1 0, 0 0))')
)),
m (x, y, b) AS (
SELECT x, y,
CASE WHEN random() > 0.9 THEN 1 ELSE 0 END
FROM
generate_series(1, 100) x,
generate_series(1, 100) y
),
-- That is the recursion of the Sport of Life
e (x, y, b, g) AS (
-- The recursion begins with the above preliminary knowledge
SELECT x, y, b, 1 FROM m
UNION ALL
SELECT
e.x, e.y,
CASE
-- If this cell is alive, and a couple of or 3
-- neighbors are alive, too, then this
-- cell stays alive
WHEN e.b = 1 AND
sum(e.b) OVER w1
+ sum(e.b) OVER w2
+ sum(e.b) OVER w3 IN (2, 3)
THEN 1
-- If this cell is lifeless, and three neighbors
-- are alive, then this cell turns into alive
WHEN e.b = 0 AND
sum(e.b) OVER w1
+ sum(e.b) OVER w2
+ sum(e.b) OVER w3 = 3
THEN 1
-- In any other case, this cell dies or stays lifeless
ELSE 0
END,
e.g + 1
FROM e
-- The recursion stops after 100 iterations
WHERE e.g < 100
WINDOW
-- We order the info set by x, y. In SQL, there is not
-- a notion of a 2-dimensional quantity aircraft. We solely
-- have 1 dimension.
o AS (ORDER BY x, y),
-- w1 is all of the neighbors of the earlier row within the x, y
-- aircraft, which is all of the SQL rows which can be 101-99 rows
-- earlier than the present row.
w1 AS (o ROWS BETWEEN 101 PRECEDING AND 99 PRECEDING),
-- w2 is all of the neighbors of the present row within the x, y
-- quantity aircraft, excluding the present cell
w2 AS (o ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
EXCLUDE CURRENT ROW),
-- w3 is all of the neighbors of the subsequent row
w3 AS (o ROWS BETWEEN 99 FOLLOWING AND 101 FOLLOWING)
)
-- Lastly, mix all of the iterations
SELECT st_union(st_translate(
sprites.s,
(x + (g - 1) % 10 * 120)::float,
(y - (g - 1) / 10 * 120)::float
))
FROM e, sprites
WHERE b = 1
;
Consider the window specs as follows:
----+-------------+-------------+-------------+-------------+---- ... | 105: (1, 5) | 106: (1, 6) | 107: (1, 7) | 108: (1, 8) | ... ... | 205: (2, 5) | 206: (2, 6) | 207: (2, 7) | 208: (2, 8) | ... ... | 305: (3, 5) | 306: (3, 6) | 307: (3, 7) | 308: (3, 8) | ... ... | 405: (4, 5) | 406: (4, 6) | 407: (4, 7) | 408: (4, 8) | ...
So, in a 100×100 grid, x=3,y=7 might be encoded as 307, and its neighbors are
- w1: 206, 207, 208, i.e. between 101 previous and 99 previous of 307
- w2: 306, 308, i.e. between 1 previous and 1 following of 307
- w3: 406, 407, 408, i.e. between 99 following and 101 following of 307
The output seems like this:
Or, zooming in on iterations 1-4:
Or 21-24:
That’s actually cool, huh!
Glider Gun
The nerd-snipe was to animate the glider gun sample, which simply means we’ll have to exchange the random era of the primary iteration by one thing fixed.
WITH RECURSIVE
sprites (s) AS (VALUES (
st_polygonfromtext('polygon ((0 0, 0 1, 1 1, 1 0, 0 0))')
)),
m (x, y, b) AS (
SELECT x, y,
-- Preliminary knowledge right here
CASE WHEN (x, y) IN (
(2, 6), (2, 7), (3, 6), (3, 7), (12, 6), (12, 7), (12, 8),
(13, 5), (13, 9), (14, 4), (14, 10), (15, 4), (15, 10),
(16, 7), (17, 5), (17, 9), (18, 6), (18, 7), (18, 8),
(19, 7), (22, 4), (22, 5), (22, 6), (23, 4), (23, 5),
(23, 6), (24, 3), (24, 7), (26, 2), (26, 3), (26, 7),
(26, 8), (36, 4), (36, 5), (37, 4), (37, 5)
) THEN 1 ELSE 0 END
FROM
generate_series(1, 100) x,
generate_series(1, 100) y
),
e (x, y, b, g) AS (
SELECT x, y, b, 1 FROM m
UNION ALL
SELECT
e.x, e.y,
CASE
WHEN e.b = 1 AND
sum(e.b) OVER w1
+ sum(e.b) OVER w2
+ sum(e.b) OVER w3 IN (2, 3)
THEN 1
WHEN e.b = 0 AND
sum(e.b) OVER w1
+ sum(e.b) OVER w2
+ sum(e.b) OVER w3 = 3
THEN 1
ELSE 0
END,
e.g + 1
FROM e
WHERE e.g < 100
WINDOW
o AS (ORDER BY x, y),
w1 AS (o ROWS BETWEEN 101 PRECEDING AND 99 PRECEDING),
w2 AS (o ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
EXCLUDE CURRENT ROW),
w3 AS (o ROWS BETWEEN 99 FOLLOWING AND 101 FOLLOWING)
)
SELECT st_union(st_translate(
sprites.s,
(x + (g - 1) % 10 * 120)::float,
(y - (g - 1) / 10 * 120)::float
))
FROM e, sprites
WHERE b = 1
;
And, as you may see, the gun works:
It began with this:
And ultimately produces the well-known gliders:
