用递归Sql和SVG绘制Sierpiń滑雪三角形

2020-05-19 05:51:17

数据库通常用作CRUD应用程序数据的哑存储箱。然而,这并不公平:PostgreSQL等数据库系统的能力和通用性要强得多,支持跨许多不同数据类型的广泛操作。

与Postgres交互的标准方式是SQL-您知道,您可能在WebDev类中学过一些东西,在WebDev类中,您可以从满足某些条件的一组表中选择内容。但这与利用这种声明性的、令人惊讶的图灵完整编程语言的全部功能集所能达到的效果相去甚远。

在这篇文章中,我将介绍一个非常简单的递归CTE1,它实现了一个迭代函数系统,用于生成SierpiSVGsvg滑雪三角形的变体,以及一个用于可视化目的的基本ń代码生成例程。最终结果将如下所示:

这篇文章大致基于我在2017年夏天托尔斯滕·格鲁斯特(Torsten Grust)在图宾根大学(University Of Tübingen)举办的高级SQL讲座上所学到的东西。请看讲课幻灯片,以获得深入的解释和大量的示例。

你已经在上面看到的sierpiń滑雪三角形,是一个自相似的分形,它的形状是一个等边三角形,它被分成四个“子三角形”:中间的是空白的,其余的也是以同样的方式划分的,而且是无穷大的。它可以以多种方式构建,所有两种方式都很有趣--但在这篇文章中,我们只关注其中一种。

与此同时,迭代函数系统通常用于生成自相似分形,就像我们今天要画的那样。维基百科对它们的定义如下:

形式上,迭代函数系是完备度量空间上的压缩映射的有限集合。

开个玩笑--这句话对我来说没有任何意义,因为我数学不好,我希望如果我在假设你不会更好的情况下继续做下去,你不会被冒犯。非正式地说,迭代函数系统(Iterated Function System,IFS)是一组函数,它们可以以任何顺序和您喜欢的次数相互应用于彼此的输出,结果最终以一种充满希望的有趣方式分布。

维基百科接着概述了我们将执行的IFS的具体应用:

计算IFS分形最常用的算法被称为“混沌博弈”。它包括在平面上选取一个随机点,然后迭代地应用从函数系统中随机选择的一个函数来变换该点以获得下一个点。

在这种情况下,函数简单地将点移动到以三角形配置排列的三个锚点中的一个。假设我们的画布是一个单位正方形(原点位于左上角,因为这是计算机图形中通常的位置):

您会注意到,这些点并不完全形成一个等边三角形,但这并不重要-我们只会得到一个略微伸展的Sierpiń滑雪三角形。(如果我们偏离中心,我们会得到一个倾斜的三角形。)。

让我们定义一下我们的函数系统。它包括三个函数,每个函数对应于一个锚点。每个函数将其输入点移动到其分配的锚点的一半:

现在!。如果我们从随机开始,将其随机送入三个函数中的一个,将结果反馈给另一个随机函数,然后继续重复,Sierpiń滑雪三角形就会慢慢从初始噪音中浮现出来。

您可以在下面的3张图中观察到这一点-从左上角到右下角的每个子图将过程推进4个迭代10次。

让我们来了解一下SQL特性,它将有助于实现我们的IFS!

公用表表达式(CTE)对于构造复杂查询非常有用,它允许查询编写器定义临时的类似视图的构造。它们有助于将大型查询分解为可能可重用的组件:WITH关键字用于将查询链接在一起,同时为每个组件查询指定一个名称,通过该名称,可以在同一WITH块内的所有后续查询中引用其结果。

WITH块由可能引用任何命名组件的标准查询终止-通常,这只是一个TABLE语句。

例如,此基本5CTE计算预测结果和观测序列6之间的平方残差之和:

预测(id,n)为(选择s。N,Exp(S)。n)从Generate_Series(0,4)as s(N)),观察(id,n)as(值(0,2),(1,3),(2,7),(3,19),(4,53)),残差(id,n)as(SELECT P.。ID,o.。N-P。来自预测p的n连接在p上观察到的o。id=o。id),平方(id,n)as(从残差中选择id,n^2),sum(N)as(从平方中选择sum(N))表SUM;

递归CTE(可通过递归关键字识别)还有另一张王牌:它们可以多次运行自引用查询,直到不再生成任何行。有点出乎意料的是,这是一个迭代的过程。

以递归面(n,res)为(SELECT 7,1 UNION ALL SELECT n-1,res*n from fac where n>;1)select res from fac where n=1;

此查询在迭代过程开始时只评估一次。它的结果被插入到临时工作表中,并且在考虑第二部分↓之后被插入到输出表中。这构成了CTE的第一次迭代。

控制每次迭代后如何组合结果的运算符:UNION ALL或UNION。

在后一种情况下,在迭代之间并且在将工作表的内容附加到输出表之前,消除相对于自身和输出表都是重复的7的工作表的行。

递归术语,可以在其FROM列表或子查询中引用当前CTE(此处:FAC)。

这样的引用被解析到工作表,该工作表始终只包含在上一次迭代中创建的行:其旧内容在每次迭代后刷新到输出表,并替换为当前迭代的结果。

当且仅当工作表在迭代开始时为空时,进程才会终止。

在Postgres中,CTE的递归术语只支持通常SQL查询工具箱的一个子集。最值得注意的是,ORDER BY不能使用8-但在子查询中允许使用,这使得这一特殊限制在实践中不是问题。

希望您已经理解了迭代函数系统和递归CTE的一般概念,让我们开始用ń实现我们的Sierpi SQLski三角形生成器。

首先,我们需要定义一个表9来存放三个锚点-没什么特别的,我们甚至不需要id列:

创建表锚(x浮点,y浮点);插入锚定值(0。5,0),(0,1),(1,1);

在编写查询之前,我们将定义要计算的函数系统的迭代次数。psql的\set功能在这里派上了用场(请注意,1e4只是的缩写)。

现在让我们开始编写将为我们玩混沌游戏的递归查询!

我将以与构建查询的顺序大致相同的顺序分阶段展示它,从递归构建的表的模式开始:我们需要与一个id列一起存储,该列将在每次迭代中递增,直到它遮蔽:n,这是我们的终止条件。

现在,非递归项必须选择我们的点的起始值-,为了更好地衡量,我们只需要选择单位正方形的中心。

好啦!由于我们将在每次迭代中递增id列,因此我们永远不会创建任何重复项。因此:

说到在每次迭代中递增id列-让我们这样做,同时实现我们的终止条件。一旦我们运行查询,:n将替换为我们先前设置的psql变量的值。请记住,只有在上一次迭代中添加的行对于递归项是可见的,否则我们将获得指数增长,而不是线性增长。

以递归点(id,x,y)为(选择1,0。5::浮点数,0。5::浮动并集全部选择p。ID+1,.,.。从p点开始,..。其中p。ID<;:n).。

下一步是从锚表中选择随机锚点(即隐含的随机选择)。您可能倾向于将其表述如下…

以递归点(id,x,y)为(选择1,0。5::浮点数,0。5::浮动并集全部选择p。ID+1,.,.。从点p开始,将a锚定在p所在的位置。ID<;:n ORDER BY RANDOM()--⚠此不符合工作限制1).。

…。但这不会起作用,因为如前所述,Postgres在递归术语的最外层查询中不支持ORDER BY。回到绘图板-让我们试试子查询:

以递归点(id,x,y)为(选择1,0。5::浮点数,0。5::浮动并集全部选择p。ID+1,.,.。从点p(SELECT*FROM ACKORS ORDER BY RANDOM()LIMIT 1)as a(x,y),其中p。ID<;:n).。

这可能不那么优雅,但它会工作得很好。

最后,剩下要做的就是实现我们的点的更新位置的计算-我们基本上可以从上面填写公式。我们还将利用最后的表点输出结果。

以递归点(id,x,y)为(选择1,0。5::浮点数,0。5::浮动并集全部选择p。ID+1,(p.。X+a。x)/2,(p.。y+a。y)/2从点p(SELECT*FROM ACKORS ORDER BY RANDOM()LIMIT 1)作为a(x,y),其中p。id<;:n)表点;

就这样!。我们的迭代函数系统按照预期迭代,我们可以通过查看查询结果来验证这一点:

+-+|id|x|y|+-+|1|0.5|0。.5|2|0·5|0·25||3|0·25|0.625||4|0.625|0.8125||5|0.3125|0.90625||6|0.40625|0.453125||7|0.453125|0.2265625||8|0.4765625|0.11328125||9|0.23828125|0.556640625||10|0.619140625|0.7783203125||11|0.8095703125|0.88916015625||12|0.90478515625|0.944580078125|13|0.952392578125|0。.9722900390625||14|0.7261962890625|0.48614501953125||15|0.86309814453125|0.743072509765625||16|0.681549072265625|0.371536254882812||17|0.840774536132812|0.685768127441406||18|0.420387268066406|0.842884063720703||19|0.710193634033203|0.921442031860352|20|0.605096817016602|0.460721015930176|21|0.802548408508301|0.730360507965088||22|0.40127420425415|0.865180253982544||23|0.450637102127075|0.432590126991272|24|0.475318551063538|0.216295063495636|25|0.487659275531769|0。.108147531747818||26|0.493829637765884|0.054073765873909||27|0.246914818882942|0.527036882936954||28|0.123457409441471|0.763518441468477||29|0.311728704720736|0.381759220734239||30|0.155864352360368|0.690879610367119|┆|9990|0.363056443960706|0.85909628057552||9991|0.431528221980353|0.42954814028776||9992|0.465764110990177|0.21477407014388||9993|0.482882055495088|0.10738703507194||9994|0.241441027747544|0.55369351753597||9995|0.370720513873772|0.276846758767985。|10000|0.435360256936886|0.138423379383993||9997|0.217680128468443|0.569211689691996||9998|0.358840064234222|0.284605844845998||9999|0.179420032117111|0.642302922422999|10000|0.589710016058555|0.8211514612115|+-+(10000行)

这看起来可能是对的,但我们怎么知道呢?不管怎样,我无法在脑海中想象出这一系列的点,所以让我们来想象一下吧!

有太多的工具10我们可以把这个表放进去--但是我认为现在通过生成一个基本的SVG图像(每个Web浏览器都可以显示)来停留在SQL的范围内会更有趣。

…。一种基于可扩展标记语言(XML)的二维图形矢量图像格式,支持交互性和动画。

交互性和动画很酷,但就我们的目的而言,SVG的各种标记中只有两个11是相关的:

<;svg>;标记充当文档的根元素,与HTML的<;html>;标记非常相似。其ViewBox属性界定内部坐标系的可见部分-其值可以解释为LEFT_EDGE BOOT_EDGE WIDTH HEIGHT。

<;Circle>;标记绘制一个圆,其半径必须通过r属性定义,以cx和cy属性指定的坐标为中心。我们将使用此标记来绘制锚点和在每次迭代中生成的点。它的外观可以用style属性中的CSS定义(如果没有以这种方式覆盖,则外观继承自<;svg>;元素的style属性)。

有了这些知识,我们就可以使用SQL的字符串连接运算符||和两个子查询来生成我们的图像:

\设置WIDT1000\设置带递归点(id,x,y)的高度1000为(.),将SVG(文本)设置为(SELECT';<;SVG xmlns=";http://www.w3.org/2000/svg";视图框=";-3-3';||:Width+6||';';||:Height+6||';";Style=";笔划:无;填充:黑色;";&>;';||(SELECT STRING_AGG(';<;Circle Cx=";';||x*:Width||';";Cy=";';||y*:Height||';";r=";1";/>;';';';';)从点)||(SELECT STRING_AGG(';<;圆形Cx=";';||x*:宽度||';";Cy=";||y*:高度||';";r=";3";style=";Fill:red;";/>;';,';';))||';<;/SVG>;)表格SVG;

依此类推--我们组装的巨型字符串以通常的表格输出格式打印,表格的顶层规则占据了终端窗口的多个屏幕。我们可以向下滚动,找到生成的SVG代码,将其复制粘贴到文本编辑器中,将缓冲区另存为.svg,然后打开该文件。但这并不是很令人满意,因此,让我们使用--Quiet标志调用psql,并将查询结果通过管道传输到一个文件中:

这实际上还不够。我们需要再执行几个配置命令…。

…。禁用默认输出格式的各个方面。但一旦完成,我们就可以向后仰身,享受我们仅用几行SQL就能取得的成就:

如果您还没有开始编码,那么完成的sierpinsky.sql看起来就像这样:

\set n 1 e4\set width 1000\set Height 1000--ShutUp,w̶e̶s̶l̶e̶y̶postgres\p设置页脚0\p设置页脚关闭\pset tuples_Only ON\Timing OFF--如果存在锚点,则设置锚点丢弃表;创建表锚点(x浮点,y浮点);插入锚点值(0.。5,0),(0,1),(1,1);--截断锚点;--插入锚点值--(0.5,0),--(0,0.4),--(1,0.4),--(0.2,1),--(0.8,1);--让';s-a开始!以递归点(id,x,y)为(选择1,0。5::浮点数,0。5::浮动并集全部选择p。ID+1,(p.。X+a。x)/2,(p.。y+a。y)/2从点p(SELECT*FROM ACKORS ORDER BY RANDOM()LIMIT 1)作为a(x,y),其中p。ID<;:n),SVG(文本)As(SELECT';<;SVG xmlns=";http://www.w3.org/2000/svg";视图框=";-3-3';||:宽度+6||';';||:高度+6||';";样式=";笔划:无;填充:黑色;";>;';|(SELECT STRING_AGG(';<;Circle Cx=";';||x*:Width||';";Cy=";';";r=&";1";/&>;';,';';)||(SELECT STRING_AGG(';<;r=";1";/&>;';';';)|(SELECT STRING_AGG(';<;)。';||x*:宽度||';";Cy=";';||y*:高度||';";r=";3";style=";Fill:red;";/>;';,';';';';<;/SVG>;';)表格SVG。

为了生成“理论”部分底部显示的“进化”可视化,我对本文中详细介绍的查询进行了修改和参数化,以输出一个小的倍数图。如果您感兴趣,下面的代码片断将替换下面的所有内容--让我们开始吧!评论:

\SET WIDTH 100\SET HEIGHT 100\SET ROWS 8\SET COLS 8\SET FAC 10\SET POINT_r 1\SET ANG_R 3 WITH RAPRING POINTING(ROW,COL,ID,x,Y)为(SELECT ROW,COL,1,0.。5::浮点数,0。5::FLOAT FROM GENERATE_SELECTION(0,(SELECT:ROWS-1))AS ROW(ROW),GENERATE_Series(0,(SELECT:COLS-1))AS COOL(COL)UNION ALL SELECT p.。ROW,P。科尔,P.。ID+1,(p.。X+a。x)/2,(p.。y+a。y)/2从点p(SELECT*FROM ACKORS ORDER BY RANDOM()LIMIT 1)作为a(x,y),其中p。ID<;:FAC*(p.。行*:COLS+P。COL)--WHERE p.id<;p.col*(:fac^p.row),svg(文本)As(SELECT';<;svg xmlns=";http://www.w3.org/2000/svg";视图框=";-';||:锚点_r||';-';|:锚点_r||';';|:WIDTH*(:COLS+1)+2*:锚定_r||';';||:高度*(:行+1)+2*:锚定_r||';";Style=";笔划:无;填充:黑色;";>;';||(SELECT STRING_AGG(';';||(SELECT STRING_AGG(';<;圆圈Cx=";';||(coll+x+coll/(:cols-1.。0))*:宽度||';";cy=";';||(row+y+row/(:row-1.。0))*:高度||';";r=";';||:point_r||';";/>;';,';';)。行和列=p。COL)||(选择STRING_AGG(';<;圆圈Cx=";';||(COL+x+COL/(:COLS-1.。0))*:宽度||';";cy=";';||(row+y+row/(:row-1.。0))*:高度||';";r=";';||:锚_r||';";style=";Fill:red;";/>;';,';';)。行和列=p。COL),';';&39;)从点p开始,其中p。ID=1)||';<;/SVG>;';)表SVG;

该实现将基于PostgreSQLSQL的方言,但只需稍加修改即可普遍使用。--↩

就我个人而言,我非常喜欢Stephen wolfram的Rule90元胞自动机采用sierpiński三角形的形状-如何在sql中模拟初级元胞自动机可能是未来一篇文章的重点。此外,令人惊讶的是,您可以使用单个HTML<;div>;标签和少量css来绘制它。“↩。

此图像是由我们即将制定的查询的改编版本生成的。但如果你更喜欢动画,看看启发我写这篇文章的推文,或者试试这个绝对令人惊叹的互动工具。-↩。

当然,我们可以无限地继续下去,但就像所有蒙特卡洛式的过程一样,我们很快就会达到回报递减的地步-此外,svg文件目前的大小超过1MB。-↩。

在“生产”上下文中,人们不会将此特定问题拆分成相当多的独立查询,但这是一个很好的示例。-↩。

许多类型的递归查询永远不会产生重复项,因此在。

..