作者
digoal
日期
2019-08-03
标签
PostgreSQL , PostGIS , 空间排序 , 算法 , minx , Morton curve , Hilbert curve , 空间紧凑排序
背景
PostGIS 是专业的空间插件，空间数据最常见的空间排序是怎么做的呢？
1、2.4以前，空间排序使用的是x轴的最小值，算法粗糙。
2、2.4开始引入了Z-order curve (Morton curve)排序算法，
https://en.wikipedia.org/wiki/Z-order_curve
3、3 开始，使用Hilbert curve代替了Z-order curve。
https://en.wikipedia.org/wiki/Hilbert_curve
例子
1、创建离散点，如图
```
CREATE SEQUENCE points_seq;
CREATE TABLE points AS
SELECT (ST_Dump
( ST_GeneratePoints(
ST_MakeEnvelope(-10000,-10000,10000,10000,3857),
10000)
)).geom AS geom,
nextval('points_seq') AS pk;
```
2、使用min(x轴)排序，聚合成线段，如图，可以清晰的看到排序后的线段是这些离散点根据min(x轴)的值顺序描绘出来的
SELECT ST_MakeLine(geom ORDER BY ST_X(geom)) AS geom
FROM points;
3、使用Z-order_curve算法排序（使用PostGIS 2.5的版本排序即可），聚合成线段，如图，可以看到Z象限的顺序
SELECT ST_MakeLine(geom ORDER BY geom) AS geom
FROM points;
4、使用Hilbert_curve（使用PostGIS 3排序），聚合成线段，如图，可以看到顺序和hilbert wiki描述一致
SELECT ST_MakeLine(geom ORDER BY geom) AS geom
FROM points;
参考
https://info.crunchydata.com/blog/waiting-for-postgis-3-hilbert-geometry-sorting
https://en.wikipedia.org/wiki/Z-order_curve
https://en.wikipedia.org/wiki/Hilbert_curve
PostgreSQL 许愿链接
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
9.9元购买3个月阿里云RDS PostgreSQL实例
PostgreSQL 解决方案集合
德哥 / digoal's github - 公益是一辈子的事.
