The upcoming jOOQ 3.16 will lastly provide help for the varied RDBMS GIS extensions by way of situation #982. That is nice information per se, and can be coated in a future weblog publish, when the combination is prepared. This publish right here is about one thing else.
Including help for such a function is a superb supply of procrastination. You see, if you develop a backend library, all you ever do is implement algorithms, API, and different summary stuff. However GIS is totally different. With GIS, a SQL developer like me abruptly has entry to a “UI”, and accessing a “UI” woke the inside programmer little one in me.
I used to be pleasantly stunned that DBeaver, my most popular 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 straightforward to map to polygons. Let’s take a look at a number of 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 take care of the prolonged WKT format
sprites AS (
SELECT
-- We mission 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 totally different from another set union. Notice that I’ve translated the bigger sq. 2 models to the proper, 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 airplane. Making a union of these two units of factors is pure. We are able to 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 will 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 mixture perform)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 take 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 size that you may mess around with
dims (r1, r2, i1, i2, s, it, p) AS (
VALUES (
-- The scale of the actual axis
-2::float, 1::float,
-- The scale 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 airplane, 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 airplane 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
-- advanced quantity airplane 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
-- It's also possible to inverse the equation to retain the factors that
-- belong to the set
WHERE zr*zr + zi*zi > p;
Notice, 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 methods to 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 possibly can mess around with this and use totally 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)
)
This can generate some actually neat zooms, all with SQL:
Granted, it’s not essentially the most environment friendly technique to calculate this stuff, 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 “recreation” the place now we have the x,y pure quantity airplane (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 reside cell with two or three reside neighbours survives.
- Any lifeless cell with three reside neighbours turns into a reside cell.
- All different reside 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 place to begin, 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 airplane 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
This can produce one thing like:
Now, all now we have to do is iterate the sport formulation. Now, recursive SQL has fairly a number of limitations. E.g. I couldn’t get PostgreSQL to mixture recursive knowledge, nor self-join the recursive desk to search out the closest neighbors of any cell. However with window features, that is undoubtedly doable. 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 information set by x, y. In SQL, there is not
-- a notion of a 2-dimensional quantity airplane. 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
-- airplane, which is all of the SQL rows which are 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 airplane, 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 appears 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 possibly can see, the gun works:
It began with this:
And ultimately produces the well-known gliders:
