利⽤PostGIS实现求解点集的最⼩⾯积包围矩形
利⽤PostGIS实现求解点集的最⼩⾯积包围矩形
最近，空间数据库原理课上涉及到利⽤PostGIS求解点集的最⼩⾯积包围矩形的问题，记录在此，希望能帮助到有需要的⼈。第⼀次写博客，有什么错误希望见谅。
本⽅法的实现原理为：最⼩⾯积外接矩形的⼀条边肯定与点集的凸包的⼀条边重合，所以思路为遍历凸包的每条边，构造外接矩形，计算⾯积，找出⾯积最⼩的那个外接矩形即可。
⼀、建⽴⼀个multipnt表⽤于保存测试数据
CREATE TABLE multipnt(
发烧友是什么意思gid rial,
geom geometry
);trumpf
⼆、 输⼊三条测试数据
INSERT INTO multipnt(geom) VALUES
(ST_GeomFromText('MULTIPOINT(50 5, 100 70, 50 20, 30 10,70 400)')),
(ST_GeomFromText('MULTIPOINT(145 35, 200 50, 276 300)')),
(ST_GeomFromText('MULTIPOINT(350 5, 450 78, 370 20, 320 108,540 400,325 87)'));
三、 利⽤ST_ConvexHull函数建⽴多点要素的最⼩凸多边形并将其转化成线环，将结果放⼊到视图ch_polygon中
CREATE OR REPLACE VIEW ch_polygon AS(
SELECT gid,ST_Boundary(ST_ConvexHull(geom)) AS geom
FROM multipnt
);
创建的最⼩凸多边形转换成线环，在QGIS中显⽰如下
四、 创建最⼩包围矩形
1、 将每个多边形的每条边取出来⽤起点终点表⽰，放在新建的视图edges中，⽤于后⾯计算每条边的⽅位⾓。（外接矩形的长宽的计算要根据各个点在某⼀条边上的投影来确定，但是投影的计算⽐较复杂，所以可以将多边形进⾏旋转，依次让⼀条边和x轴平⾏，这样的话，最⼩外接矩形的长宽即分别为各点xy的最⼤值与最⼩值之差，构造出最⼩外接矩形后，再将构造出来的矩形按照前⾯旋转的反⽅向进⾏旋转，就可以得到最⼩外接矩形）
CREATE OR REPLACE VIEW edges AS(
visit的音标
WITH RECURSIVE x(gid,n,pnt_num) AS(
SELECT gid,1AS n,ST_NumPoints(geom) AS pnt_num
FROM ch_polygon
UNION ALL
lon
SELECT gid,n+1,pnt_num
FROM x
WHERE n<pnt_num-1
)
SELECT gid,n AS eid,ST_PointN(geom,n)AS from_pnt,
ST_PointN(geom,n+1)AS to_pnt,geom FROM
(
SELECT x.gid,n,geom FROM x INNER JOIN ch_polygon p ON(x.gid=p.gid)
) AS a
);
2、 计算每个多边形的每条边的⽅位⾓，然后将多边形进⾏旋转使得每个多边形分别与⾃⼰的每条边平⾏，以便于计算其他边在这条边上的投影，将所得的结果存放在新视图rotate_polygon中
CREATE OR REPLACE VIEW rotate_polygon AS(
WITH t AS(
SELECT gid,eid,3*PI()/2+ST_Azimuth(from_pnt,to_pnt)AS angle,geom
adam lamberg
FROM edges
)
SELECT gid,eid,ST_Rotate(geom,angle)AS geom,angle
FROM t
);
同义词典
在QGIS中显⽰图形如下所⽰，可以看到每个旋转后的多边形都有⼀条边与x轴平⾏。
3、 将rotate_polygon中的每个线串的x、y的最⼤最⼩值，并将结果放在新视图pnt_exterma
4、 利⽤pnt_exterma视图中的数据，计算由x、y的最⼤最下值形成的各个矩形的⾯积，求出最⼩值，即是最⼩矩形，将结果存放在视图min_rect中。
CREATE OR REPLACE VIEW pnt_exterma as (
WITH RECURSIVE x(gid,eid,n,pnt_num) AS (
SELECT gid,eid,1 AS n,ST_NumPoints(geom) AS pnt_num
FROM rotate_polygon
UNION ALL
SELECT gid,eid,n+1,pnt_num
FROM x
WHERE n<pnt_num-1
)
SELECT gid,eid,MIN (ST_X(geom))AS minx,MIN (ST_Y(geom))AS miny,
MAX (ST_X(geom))AS maxx,MAX (ST_Y(geom))AS maxy
FROM (
SELECT r.gid,r.eid,n,ST_PointN(geom,n)AS geom
FROM rotate_polygon r
INNER JOIN x ON (r.gid=x.gid and r.eid=x.eid)
)AS a
shmGROUP BY a.gid,a.eid ORDER BY gid,eid
);
在QGIS中显⽰结果如下图所⽰ 5、 将min_rect中的矩形进⾏旋转，最后得到点集的⾯积最⼩的包围矩形，将结果放⼊新视图result中
CREATE OR REPLACE VIEW min_rect AS (
SELECT * FROM (
WITH t AS (
天府之国英语SELECT gid,eid,ST_MakeEnvelope(minx,miny,maxx,maxy)AS geom,
(maxx-minx)*(maxy-miny) AS area
FROM pnt_exterma
)
SELECT gid,eid,geom,area,
RANK() OVER(PARTITION BY gid ORDER BY area) AS area_rank
demarkFROM t
)AS a
WHERE area_rank=1);
中北大学怎么样
CREATE VIEW result AS (
WITH t AS (
SELECT m.gid,angle
FROM min_rect m,rotate_polygon p
WHERE m.gid=p.gid AND m.eid=p.eid
)
SELECT min_rect.gid,area,ST_Rotate(geom,-angle)AS geom
FROM min_rect,t
WHERE min_rect.gid=t.gid
);
在QGIS中显⽰结果如下图所⽰，点集的⾯积最⼩的包围矩形得以求解。
其⾯积在属性表中显⽰如下：
