[postgis-tickets] [SCM] PostGIS branch master updated. 3.2.0-400-g0f2afd2ac
git at osgeo.org
git at osgeo.org
Fri Jan 28 14:18:51 PST 2022
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via 0f2afd2ac3f1a1e8faddd8b4e1aa3df6301848a5 (commit)
from a7298c25a7531f78fb4a8c8861c407da942667cc (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 0f2afd2ac3f1a1e8faddd8b4e1aa3df6301848a5
Author: Paul Ramsey <pramsey at cleverelephant.ca>
Date: Fri Jan 28 14:18:00 2022 -0800
ST_ConcaveHull implementation from GEOS 3.11+
A native code concave hull implementation with better performance
and fewer failure cases than the current PL/PgSQL implementation.
diff --git a/doc/html/image_src/Makefile.in b/doc/html/image_src/Makefile.in
index 2f535e01a..a88e08363 100644
--- a/doc/html/image_src/Makefile.in
+++ b/doc/html/image_src/Makefile.in
@@ -61,12 +61,6 @@ IMAGES= \
../images/st_contains06.png \
../images/st_concavehull01.png \
../images/st_concavehull02.png \
- ../images/st_concavehull03.png \
- ../images/st_concavehull04.png \
- ../images/st_concavehull05.png \
- ../images/st_concavehull06.png \
- ../images/st_concavehull07.png \
- ../images/st_concavehull08.png \
../images/st_convexhull01.png \
../images/st_crosses01.png \
../images/st_crosses02.png \
diff --git a/doc/html/image_src/st_concavehull01.wkt b/doc/html/image_src/st_concavehull01.wkt
index 9e71e3a44..555c5d391 100644
--- a/doc/html/image_src/st_concavehull01.wkt
+++ b/doc/html/image_src/st_concavehull01.wkt
@@ -1,2 +1,2 @@
-Style1;POLYGON((175 150, 20 40, 50 60, 125 100, 175 150))
-Style1;POLYGON((130 170,129.615705608065 166.098193559677,128.477590650226 162.346331352698,126.629392246051 158.888595339608,124.142135623731 155.857864376269,121.111404660392 153.370607753949,117.653668647302 151.522409349774,113.901806440323 150.384294391935,110 150,106.098193559677 150.384294391935,102.346331352698 151.522409349774,98.888595339608 153.370607753949,95.8578643762691 155.857864376269,93.3706077539491 158.888595339608,91.5224093497743 162.346331352698,90.3842943919354 166.098193559677,90 170,90.3842943919354 173.901806440323,91.5224093497742 177.653668647302,93.3706077539491 181.111404660392,95.857864376269 184.142135623731,98.8885953396079 186.629392246051,102.346331352698 188.477590650226,106.098193559677 189.615705608065,110 190,113.901806440323 189.615705608065,117.653668647302 188.477590650226,121.111404660392 186.629392246051,124.142135623731 184.142135623731,126.629392246051 181.111404660392,128.477590650226 177.653668647302,129.615705608065 173.901806440323,
130 170))
+Style2;POLYGON ((18 142, 21 151, 27 160, 35 167, 44 172, 54 175, 64 178, 74 180, 84 181, 94 181, 104 181, 114 181, 124 181, 134 179, 144 177, 153 173, 162 168, 171 162, 177 154, 182 145, 184 135, 173 134, 161 134, 150 133, 139 132, 136 142, 128 149, 119 153, 109 155, 99 155, 89 155, 79 153, 69 150, 61 144, 63 134, 72 128, 82 125, 92 123, 102 121, 112 119, 122 118, 132 116, 142 113, 151 110, 161 106, 170 102, 178 96, 185 88, 189 78, 190 68, 189 58, 185 49, 179 41, 171 34, 162 29, 153 25, 143 23, 133 21, 123 19, 113 19, 102 19, 92 19, 82 19, 72 21, 62 22, 52 25, 43 29, 33 34, 25 41, 19 49, 14 58, 10 72, 21 73, 31 74, 42 74, 53 76, 56 66, 63 58, 71 51, 81 48, 91 46, 101 45, 111 46, 121 47, 131 50, 140 55, 145 64, 144 74, 135 80, 125 83, 115 85, 105 87, 95 89, 85 91, 75 93, 65 95, 55 98, 45 102, 37 107, 29 114, 22 122, 19 132, 18 142))
+Style1;MULTIPOINT ((10 72), (53 76), (56 66), (63 58), (71 51), (81 48), (91 46), (101 45), (111 46), (121 47), (131 50), (140 55), (145 64), (144 74), (135 80), (125 83), (115 85), (105 87), (95 89), (85 91), (75 93), (65 95), (55 98), (45 102), (37 107), (29 114), (22 122), (19 132), (18 142), (21 151), (27 160), (35 167), (44 172), (54 175), (64 178), (74 180), (84 181), (94 181), (104 181), (114 181), (124 181), (134 179), (144 177), (153 173), (162 168), (171 162), (177 154), (182 145), (184 135), (139 132), (136 142), (128 149), (119 153), (109 155), (99 155), (89 155), (79 153), (69 150), (61 144), (63 134), (72 128), (82 125), (92 123), (102 121), (112 119), (122 118), (132 116), (142 113), (151 110), (161 106), (170 102), (178 96), (185 88), (189 78), (190 68), (189 58), (185 49), (179 41), (171 34), (162 29), (153 25), (143 23), (133 21), (123 19), (113 19), (102 19), (92 19), (82 19), (72 21), (62 22), (52 25), (43 29), (33 34), (25 41), (19 49), (14 58), (21 73), (31 74)
, (42 74), (173 134), (161 134), (150 133), (97 104), (52 117), (157 156), (94 171), (112 106), (169 73), (58 165), (149 40), (70 33), (147 157), (48 153), (140 96), (47 129), (173 55), (144 86), (159 67), (150 146), (38 136), (111 170), (124 94), (26 59), (60 41), (71 162), (41 64), (88 110), (122 34), (151 97), (157 56), (39 146), (88 33), (159 45), (47 56), (138 40), (129 165), (33 48), (106 31), (169 147), (37 122), (71 109), (163 89), (37 156), (82 170), (180 72), (29 142), (46 41), (59 155), (124 106), (157 80), (175 82), (56 50), (62 116), (113 95), (144 167))
diff --git a/doc/html/image_src/st_concavehull02.wkt b/doc/html/image_src/st_concavehull02.wkt
index 937a14681..dea4d9980 100644
--- a/doc/html/image_src/st_concavehull02.wkt
+++ b/doc/html/image_src/st_concavehull02.wkt
@@ -1,3 +1,2 @@
-Style2;POLYGON((20.5 39,20 39,19.5 39,19.5 39.5,19 39.5,19 40,19 40.5,93.5 157,93.5 157.5,93 157.5,93 158,92.5 158.5,92.5 159,92 159,92 159.5,91.5 160.5,91 160.5,91 161,90.5 162,90.5 162.5,90.5 163,90 163,90 163.5,90 164.5,89.5 164.5,89.5 165,89.5 165.5,89.5 166,89.5 166.5,89.5 167,89 167,89 167.5,89 168,89 168.5,89 169,89 169.5,89 170,89 171,89 171.5,89 172,89 172.5,89 173,89.5 174,89.5 174.5,89.5 175,90 175.5,90 176.5,90 177,90.5 177,90.5 177.5,90.5 178,91 179,91 179.5,91.5 180,92 180.5,92 181,92.5 181,92.5 181.5,92.5 182,93 182,93 182.5,93.5 182.5,93.5 183,94 183.5,94 184,94.5 184,95 184.5,95 185,96 185.5,96 186,96.5 186,97 186,97 186.5,97.5 186.5,97.5 187,98 187,98 187.5,98.5 187.5,99 187.5,99 188,99.5 188,100.5 188.5,100.5 189,101 189,102 189.5,102.5 189.5,103 189.5,103 190,103.5 190,104 190,104.5 190,105 190.5,105.5 190.5,106 190.5,106.5 190.5,107 190.5,107 191,107.5 191,108 191,108.5 191,109 191,109.5 191,110 191,110.5 191,111 191,111.5 191,112 191,112.5 191,113 191,114 190.5
,115 190.5,115.5 190,116 190,116.5 190,117 190,117 189.5,117.5 189.5,118 189.5,119 189,119.5 189,119.5 188.5,120 188.5,120.5 188,121 188,121 187.5,121.5 187.5,122.5 187,122.5 186.5,123 186.5,123.5 186,124 186,124 185.5,124.5 185,125 185,125 184.5,125.5 184,126 184,126 183,126.5 183,126.5 182.5,127 182.5,127 182,127.5 181.5,127.5 181,128 181,128 180.5,128.5 179.5,129 179.5,129 179,129 178.5,129.5 178,129.5 177.5,129.5 177,130 177,130 176.5,130 176,130 175.5,130.5 175,130.5 174.5,130.5 174,130.5 173.5,130.5 173,131 173,131 172.5,131 172,131 171.5,131 171,131 170.5,131 170,131 169.5,131 169,131 168.5,131 168,131 167.5,131 167,130.5 166,130.5 165,130 164.5,130 164,130 163.5,130 163,129.5 163,129.5 162.5,129.5 162,129 161,175 151,175.5 151,175.5 150.5,176 150.5,176 150,176 149.5,175.5 149.5,135 109,125.5 99.5,125.5 99,20.5 39))
-Style1;POLYGON((175 150, 20 40, 50 60, 125 100, 175 150))
-Style1;POLYGON((130 170,129.615705608065 166.098193559677,128.477590650226 162.346331352698,126.629392246051 158.888595339608,124.142135623731 155.857864376269,121.111404660392 153.370607753949,117.653668647302 151.522409349774,113.901806440323 150.384294391935,110 150,106.098193559677 150.384294391935,102.346331352698 151.522409349774,98.888595339608 153.370607753949,95.8578643762691 155.857864376269,93.3706077539491 158.888595339608,91.5224093497743 162.346331352698,90.3842943919354 166.098193559677,90 170,90.3842943919354 173.901806440323,91.5224093497742 177.653668647302,93.3706077539491 181.111404660392,95.857864376269 184.142135623731,98.8885953396079 186.629392246051,102.346331352698 188.477590650226,106.098193559677 189.615705608065,110 190,113.901806440323 189.615705608065,117.653668647302 188.477590650226,121.111404660392 186.629392246051,124.142135623731 184.142135623731,126.629392246051 181.111404660392,128.477590650226 177.653668647302,129.615705608065 173.901806440323,
130 170))
+Style2;POLYGON ((43 69, 50 84, 57 100, 63 118, 68 133, 74 149, 81 164, 88 180, 101 180, 112 180, 119 164, 126 149, 132 131, 139 113, 143 100, 150 84, 157 69, 163 51, 168 36, 174 20, 163 20, 150 20, 143 36, 139 49, 132 64, 114 64, 99 64, 81 64, 63 64, 57 49, 52 36, 46 20, 37 20, 26 20, 32 36, 35 45, 39 55, 43 69), (88 124, 81 109, 74 93, 83 82, 99 82, 112 82, 121 96, 114 109, 110 122, 103 138, 92 138, 88 124))
+Style1;MULTIPOINT ((132 64), (114 64), (99 64), (81 64), (63 64), (57 49), (52 36), (46 20), (37 20), (26 20), (32 36), (39 55), (43 69), (50 84), (57 100), (63 118), (68 133), (74 149), (81 164), (88 180), (101 180), (112 180), (119 164), (126 149), (132 131), (139 113), (143 100), (150 84), (157 69), (163 51), (168 36), (174 20), (163 20), (150 20), (143 36), (139 49), (132 64), (99 151), (92 138), (88 124), (81 109), (74 93), (70 82), (83 82), (99 82), (112 82), (126 82), (121 96), (114 109), (110 122), (103 138), (99 151), (34 27), (43 31), (48 44), (46 58), (52 73), (63 73), (61 84), (72 71), (90 69), (101 76), (123 71), (141 62), (166 27), (150 33), (159 36), (146 44), (154 53), (152 62), (146 73), (134 76), (143 82), (141 91), (130 98), (126 104), (132 113), (128 127), (117 122), (112 133), (119 144), (108 147), (119 153), (110 171), (103 164), (92 171), (86 160), (88 142), (79 140), (72 124), (83 131), (79 118), (68 113), (63 102), (68 93), (35 45))
diff --git a/doc/html/image_src/st_concavehull03.wkt b/doc/html/image_src/st_concavehull03.wkt
deleted file mode 100644
index aa84a0ece..000000000
--- a/doc/html/image_src/st_concavehull03.wkt
+++ /dev/null
@@ -1,3 +0,0 @@
-Style2;POLYGON((20 40,91.5 177.75,93.25 181,95.75 184.25,99 186.75,102.25 188.5,106 189.5,110 190,114 189.5,117.75 188.5,121 186.75,175 150,125 100,20 40))
-Style1;POLYGON((175 150,125 100,50 60,20 40,175 150))
-Style1;POLYGON((130 170,129.5 166,128.5 162.25,126.75 159,124.25 155.75,121 153.25,117.75 151.5,114 150.5,110 150,106 150.5,102.25 151.5,99 153.25,95.75 155.75,93.25 159,91.5 162.25,90.5 166,90 170,90.5 174,91.5 177.75,93.25 181,95.75 184.25,99 186.75,102.25 188.5,106 189.5,110 190,114 189.5,117.75 188.5,121 186.75,124.25 184.25,126.75 181,128.5 177.75,129.5 174,130 170))
diff --git a/doc/html/image_src/st_concavehull04.wkt b/doc/html/image_src/st_concavehull04.wkt
deleted file mode 100644
index 5a9c4d71f..000000000
--- a/doc/html/image_src/st_concavehull04.wkt
+++ /dev/null
@@ -1,2 +0,0 @@
-Style2;POLYGON((8 6,6 8,6 194,14 194,154 14,154 6,8 6))
-Style1-thinline;MULTIPOINT(14 14,34 14,54 14,74 14,94 14,114 14,134 14,150 14,154 14,154 6,134 6,114 6,94 6,74 6,54 6,34 6,14 6,10 6,8 6,7 7,6 8,6 10,6 30,6 50,6 70,6 90,6 110,6 130,6 150,6 170,6 190,6 194,14 194,14 174,14 154,14 134,14 114,14 94,14 74,14 54,14 34,14 14)
diff --git a/doc/html/image_src/st_concavehull05.wkt b/doc/html/image_src/st_concavehull05.wkt
deleted file mode 100644
index 5e89c4115..000000000
--- a/doc/html/image_src/st_concavehull05.wkt
+++ /dev/null
@@ -1 +0,0 @@
-Style2;POLYGON((8 6,6 8,6 50,6 90,6 130,6 170,6 194,14 194,14 154,14 134,14 94,114 14,134 14,154 14,154 6,114 6,74 6,34 6,8 6))
diff --git a/doc/html/image_src/st_concavehull06.wkt b/doc/html/image_src/st_concavehull06.wkt
deleted file mode 100644
index b8928383d..000000000
--- a/doc/html/image_src/st_concavehull06.wkt
+++ /dev/null
@@ -1 +0,0 @@
-Style2;POLYGON((26 179,27 177,26 170,24 162,27 157,26 150,24 142,27 137,26 130,24 122,27 117,26 110,24 102,27 97,26 90,24 82,27 77,26 70,24 62,27 57,26 50,24 42,25 41,27 34,27 27,31 27,41 37,54 40,64 38,74 40,84 38,94 40,104 38,114 40,124 38,134 40,154 14,154 6,8 6,6 8,6 194,14 194,26 179))
\ No newline at end of file
diff --git a/doc/html/image_src/st_concavehull07.wkt b/doc/html/image_src/st_concavehull07.wkt
deleted file mode 100644
index 59661771a..000000000
--- a/doc/html/image_src/st_concavehull07.wkt
+++ /dev/null
@@ -1,2 +0,0 @@
-Style2;POLYGON((132 10,66 28,22 64,36 150,92 182,132 186,176 184,190 122,190 100,186 52,178 34,168 18,132 10))
-Style1-thinline;MULTILINESTRING((106 164,30 112,74 70,82 112,130 94,130 62,122 40,156 32,162 76,172 88),(132 178,134 148,128 136,96 128,132 108,150 130,170 142,174 110,156 96,158 90,158 88),(22 64,66 28,94 38,94 68,114 76,112 30,132 10,168 18,178 34,186 52,184 74,190 100,190 122,182 148,178 170,176 184,156 164,146 178,132 186,92 182,56 158,36 150,62 150,76 128,88 118))
\ No newline at end of file
diff --git a/doc/html/image_src/st_concavehull08.wkt b/doc/html/image_src/st_concavehull08.wkt
deleted file mode 100644
index b3dfbe63c..000000000
--- a/doc/html/image_src/st_concavehull08.wkt
+++ /dev/null
@@ -1,2 +0,0 @@
-Style2;POLYGON((132 10,119 23,85 35,68 29,66 28,49 42,32 56,22 64,32 110,40 119,36 150,57 158,75 171,92 182,114 184,132 186,146 178,176 184,179 162,184 141,190 122,190 100,185 79,186 56,186 52,178 34,168 18,147 13,132 10))
-Style1-thinline;MULTILINESTRING((106 164,30 112,74 70,82 112,130 94,130 62,122 40,156 32,162 76,172 88),(132 178,134 148,128 136,96 128,132 108,150 130,170 142,174 110,156 96,158 90,158 88),(22 64,66 28,94 38,94 68,114 76,112 30,132 10,168 18,178 34,186 52,184 74,190 100,190 122,182 148,178 170,176 184,156 164,146 178,132 186,92 182,56 158,36 150,62 150,76 128,88 118))
\ No newline at end of file
diff --git a/doc/reference_processing.xml b/doc/reference_processing.xml
index f21d6168c..cb667a838 100644
--- a/doc/reference_processing.xml
+++ b/doc/reference_processing.xml
@@ -628,194 +628,100 @@ POINT(0.5 1)
<refsection>
<title>Description</title>
- <para>A concave hull of a geometry represents a possibly concave
- geometry that encloses the input geometry.
- The result is a single polygon, line or point.
- It will not contain holes unless the optional <varname>allow_holes</varname> argument is specified as true.
- </para>
- <para>One can think of a concave hull as a geometry obtained by "shrink-wrapping" a set of geometries.
- This is different to the convex hull, which is more like wrapping a rubber band around the geometries.
- It is slower to compute than the convex hull but generally has a smaller area
- and represents a more natural boundary for the input geometry.</para>
+ <para>A concave hull of a geometry is a possibly concave
+ geometry that encloses the vertices of the input geometry.
+ In the general case the concave hull is a Polygon.
+ The polygon will not contain holes unless the optional <varname>allow_holes</varname>
+ argument is specified as true.
+ The concave hull of two or more collinear points is a two-point LineString.
+ The concave hull of one or more identical points is a Point.
+ </para>
- <para>The <varname>target_percent</varname> is the percentage of area of the convex hull the solution tries to approach.
- A target_percent of 1 gives the same result as the convex hull. A target_percent
- between 0 and 0.99 produces a result that should have a smaller area than the convex hull.
+ <para>One can think of a concave hull as "shrink-wrapping" a set of points.
+ This is different to the <link linkend="ST_ConvexHull">convex hull</link>,
+ which is more like wrapping a rubber band around the points.
+ The concave hull generally has a smaller area
+ and represents a more natural boundary for the input points.
+ Like the convex hull, the vertices of a concave hull are a subset of the input points,
+ and all other input points are contained within it.</para>
+
+ <para>The <varname>target_percent</varname> controls the concaveness of the computed hull.
+ A value of 1 produces the convex hull.
+ A value of 0 produces a hull of maximum concaveness (but still a single polygon).
+ Values between 1 and 0 produce hulls of increasing concaveness.
+ Choosing a suitable value depends on the nature of the input data,
+ but often values between 0.3 and 0.1 produce reasonable results.
</para>
- <note><para>The smaller the target percent, the longer it takes to process the concave hull, and the more likely to run into topological exceptions. Also the more
- floating points and number of points you accrue. First try 0.99 which does a single pass, is usually very fast, sometimes as fast as computing the convex hull, and usually gives much better than 99% of shrink since it almost always overshoots.
- Second hope of 0.98 is slower, others get slower usually quadratically.
- To reduce precision and float points, use <xref linkend="ST_SimplifyPreserveTopology" /> or <xref linkend="ST_SnapToGrid" /> after ST_ConcaveHull. ST_SnapToGrid is a bit faster, but
- could result in invalid geometries whereas ST_SimplifyPreserveTopology almost always preserves the validity of the geometry.</para></note>
+ <para>Technically, the target percent determines a length as a fraction of the difference between
+ the longest and shortest edges in the Delaunay Triangulation of the input points.
+ Edges longer than this length are "eroded" from the triangulation.
+ The triangles remaining form the concave hull.
+ </para>
<para>This is not an aggregate function.
- To compute the concave hull of a set of geometries, use with <xref linkend="ST_Collect" />
- or <xref linkend="ST_Union" />
- (e.g. <code>ST_ConcaveHull(ST_Collect(somepointfield), 0.80)</code>.</para>
-
- <note><para>For use with sets of points or linestrings use <code>ST_Collect</code>.
- Use <code>ST_Union</code> for polygons, since it may fail with invalid geometries.</para></note>
-
- <para>More real world examples and brief explanation of the technique are shown <ulink
- url="http://www.bostongis.com/postgis_concavehull.snippet">http://www.bostongis.com/postgis_concavehull.snippet</ulink></para>
-
- <para>Also check out Simon Greener's article on demonstrating ConcaveHull introduced in Oracle 11G R2. <ulink
- url="http://www.spatialdbadvisor.com/oracle_spatial_tips_tricks/172/concave-hull-geometries-in-oracle-11gr2">http://www.spatialdbadvisor.com/oracle_spatial_tips_tricks/172/concave-hull-geometries-in-oracle-11gr2</ulink>.
- The solution we get at 0.75 target percent of convex hull is similar to the shape Simon gets with Oracle SDO_CONCAVEHULL_BOUNDARY.</para>
-
- <para>Performed by the GEOS module</para>
+ To compute the concave hull of a set of geometries use <xref linkend="ST_Collect" />
+ (e.g. <code>ST_ConcaveHull( ST_Collect( geom ), 0.80)</code>.</para>
<para>Availability: 2.0.0</para>
+ <para>Enhanced: 3.2.0</para>
</refsection>
<refsection>
<title>Examples</title>
-<programlisting>
---Get estimate of infected area based on point observations
-SELECT d.disease_type,
- ST_ConcaveHull(ST_Collect(d.pnt_geom), 0.99) As geom
- FROM disease_obs As d
- GROUP BY d.disease_type;
-</programlisting>
- <informaltable>
- <tgroup cols="2">
- <tbody>
- <row>
- <entry><para><informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull03.png" />
- </imageobject>
- <caption><para>ST_ConcaveHull of 2 polygons encased in target 100% shrink concave hull</para></caption>
- </mediaobject>
- </informalfigure>
- <programlisting>
--- geometries overlaid with concavehull
--- at target 100% shrink (this is the same as convex hull - since no shrink)
-SELECT
- ST_ConcaveHull(
- ST_Union(ST_GeomFromText('POLYGON((175 150, 20 40,
- 50 60, 125 100, 175 150))'),
- ST_Buffer(ST_GeomFromText('POINT(110 170)'), 20)
- ), 1)
- As convexhull;
- </programlisting>
- </para></entry>
- <entry><para><informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull02.png" />
- </imageobject>
- <caption><para>-- geometries overlaid with concavehull
- at target 90% of convex hull area</para></caption>
- </mediaobject>
- </informalfigure>
- <programlisting>
--- geometries overlaid with concavehull at target 90% shrink
-SELECT
- ST_ConcaveHull(
- ST_Union(ST_GeomFromText('POLYGON((175 150, 20 40,
- 50 60, 125 100, 175 150))'),
- ST_Buffer(ST_GeomFromText('POINT(110 170)'), 20)
- ), 0.9)
- As target_90;
- </programlisting>
- </para></entry>
- </row>
- <row>
- <entry><para><informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull04.png" />
- </imageobject>
- <caption><para>L Shape points overlaid with convex hull</para></caption>
- </mediaobject>
- </informalfigure>
- <programlisting>
--- this produces a table of 42 points that form an L shape
-SELECT (ST_DumpPoints(ST_GeomFromText(
-'MULTIPOINT(14 14,34 14,54 14,74 14,94 14,114 14,134 14,
-150 14,154 14,154 6,134 6,114 6,94 6,74 6,54 6,34 6,
-14 6,10 6,8 6,7 7,6 8,6 10,6 30,6 50,6 70,6 90,6 110,6 130,
-6 150,6 170,6 190,6 194,14 194,14 174,14 154,14 134,14 114,
-14 94,14 74,14 54,14 34,14 14)'))).geom
- INTO TABLE l_shape;
-SELECT ST_ConvexHull(ST_Collect(geom))
-FROM l_shape;
- </programlisting>
- </para></entry>
- <entry><para><informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull05.png" />
- </imageobject>
- <caption><para>ST_ConcaveHull of L points at target 99% of convex hull</para></caption>
- </mediaobject>
- </informalfigure>
- <programlisting>
-SELECT ST_ConcaveHull(ST_Collect(geom), 0.99)
- FROM l_shape;
- </programlisting>
- </para></entry>
- </row>
- <row>
- <entry><para><informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull06.png" />
- </imageobject>
- <caption><para>Concave Hull of L points at target 80% convex hull area</para></caption>
- </mediaobject>
- </informalfigure>
+<para>
+ <informalfigure>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="images/st_concavehull01.png" />
+ </imageobject>
+ <caption><para>Concave Hull of a MultiPoint</para></caption>
+ </mediaobject>
+ </informalfigure>
<programlisting>
- -- Concave Hull L shape points
- -- at target 80% of convexhull
- SELECT ST_ConcaveHull(ST_Collect(geom), 0.80)
- FROM l_shape;
+SELECT ST_AsText( ST_ConcaveHull(
+ 'MULTIPOINT ((10 72), (53 76), (56 66), (63 58), (71 51), (81 48), (91 46), (101 45), (111 46), (121 47), (131 50), (140 55), (145 64), (144 74), (135 80), (125 83), (115 85), (105 87), (95 89), (85 91), (75 93), (65 95), (55 98), (45 102), (37 107), (29 114), (22 122), (19 132), (18 142), (21 151), (27 160), (35 167), (44 172), (54 175), (64 178), (74 180), (84 181), (94 181), (104 181), (114 181), (124 181), (134 179), (144 177), (153 173), (162 168), (171 162), (177 154), (182 145), (184 135), (139 132), (136 142), (128 149), (119 153), (109 155), (99 155), (89 155), (79 153), (69 150), (61 144), (63 134), (72 128), (82 125), (92 123), (102 121), (112 119), (122 118), (132 116), (142 113), (151 110), (161 106), (170 102), (178 96), (185 88), (189 78), (190 68), (189 58), (185 49), (179 41), (171 34), (162 29), (153 25), (143 23), (133 21), (123 19), (113 19), (102 19), (92 19), (82 19), (72 21), (62 22), (52 25), (43 29), (33 34), (25 41), (19 49), (14 58), (21 73), (31 7
4), (42 74), (173 134), (161 134), (150 133), (97 104), (52 117), (157 156), (94 171), (112 106), (169 73), (58 165), (149 40), (70 33), (147 157), (48 153), (140 96), (47 129), (173 55), (144 86), (159 67), (150 146), (38 136), (111 170), (124 94), (26 59), (60 41), (71 162), (41 64), (88 110), (122 34), (151 97), (157 56), (39 146), (88 33), (159 45), (47 56), (138 40), (129 165), (33 48), (106 31), (169 147), (37 122), (71 109), (163 89), (37 156), (82 170), (180 72), (29 142), (46 41), (59 155), (124 106), (157 80), (175 82), (56 50), (62 116), (113 95), (144 167))',
+ 0.1 ) );
+---st_astext--
+POLYGON ((18 142, 21 151, 27 160, 35 167, 44 172, 54 175, 64 178, 74 180, 84 181, 94 181, 104 181, 114 181, 124 181, 134 179, 144 177, 153 173, 162 168, 171 162, 177 154, 182 145, 184 135, 173 134, 161 134, 150 133, 139 132, 136 142, 128 149, 119 153, 109 155, 99 155, 89 155, 79 153, 69 150, 61 144, 63 134, 72 128, 82 125, 92 123, 102 121, 112 119, 122 118, 132 116, 142 113, 151 110, 161 106, 170 102, 178 96, 185 88, 189 78, 190 68, 189 58, 185 49, 179 41, 171 34, 162 29, 153 25, 143 23, 133 21, 123 19, 113 19, 102 19, 92 19, 82 19, 72 21, 62 22, 52 25, 43 29, 33 34, 25 41, 19 49, 14 58, 10 72, 21 73, 31 74, 42 74, 53 76, 56 66, 63 58, 71 51, 81 48, 91 46, 101 45, 111 46, 121 47, 131 50, 140 55, 145 64, 144 74, 135 80, 125 83, 115 85, 105 87, 95 89, 85 91, 75 93, 65 95, 55 98, 45 102, 37 107, 29 114, 22 122, 19 132, 18 142))
</programlisting>
- </para>
- </entry>
- <entry><para>
- <informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull07.png" />
- </imageobject>
- <caption><para>multilinestring overlaid with Convex hull</para></caption>
- </mediaobject>
- </informalfigure>
- <informalfigure>
- <mediaobject>
- <imageobject>
- <imagedata fileref="images/st_concavehull08.png" />
- </imageobject>
- <caption><para>multilinestring with overlaid with Concave hull
- of linestrings at 99% target -- first hop</para></caption>
- </mediaobject>
- </informalfigure>
+</para>
+
+<para>
+ <informalfigure>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="images/st_concavehull02.png" />
+ </imageobject>
+ <caption><para>Concave Hull of a MultiPoint, allowing holes</para></caption>
+ </mediaobject>
+ </informalfigure>
<programlisting>
-SELECT ST_ConcaveHull(ST_GeomFromText('MULTILINESTRING((106 164,30 112,74 70,82 112,130 94,
- 130 62,122 40,156 32,162 76,172 88),
-(132 178,134 148,128 136,96 128,132 108,150 130,
-170 142,174 110,156 96,158 90,158 88),
-(22 64,66 28,94 38,94 68,114 76,112 30,
-132 10,168 18,178 34,186 52,184 74,190 100,
-190 122,182 148,178 170,176 184,156 164,146 178,
-132 186,92 182,56 158,36 150,62 150,76 128,88 118))'),0.99)
+SELECT ST_AsText( ST_ConcaveHull(
+ 'MULTIPOINT ((132 64), (114 64), (99 64), (81 64), (63 64), (57 49), (52 36), (46 20), (37 20), (26 20), (32 36), (39 55), (43 69), (50 84), (57 100), (63 118), (68 133), (74 149), (81 164), (88 180), (101 180), (112 180), (119 164), (126 149), (132 131), (139 113), (143 100), (150 84), (157 69), (163 51), (168 36), (174 20), (163 20), (150 20), (143 36), (139 49), (132 64), (99 151), (92 138), (88 124), (81 109), (74 93), (70 82), (83 82), (99 82), (112 82), (126 82), (121 96), (114 109), (110 122), (103 138), (99 151), (34 27), (43 31), (48 44), (46 58), (52 73), (63 73), (61 84), (72 71), (90 69), (101 76), (123 71), (141 62), (166 27), (150 33), (159 36), (146 44), (154 53), (152 62), (146 73), (134 76), (143 82), (141 91), (130 98), (126 104), (132 113), (128 127), (117 122), (112 133), (119 144), (108 147), (119 153), (110 171), (103 164), (92 171), (86 160), (88 142), (79 140), (72 124), (83 131), (79 118), (68 113), (63 102), (68 93), (35 45))',
+ 0.15, true ) );
+---st_astext--
+POLYGON ((43 69, 50 84, 57 100, 63 118, 68 133, 74 149, 81 164, 88 180, 101 180, 112 180, 119 164, 126 149, 132 131, 139 113, 143 100, 150 84, 157 69, 163 51, 168 36, 174 20, 163 20, 150 20, 143 36, 139 49, 132 64, 114 64, 99 64, 81 64, 63 64, 57 49, 52 36, 46 20, 37 20, 26 20, 32 36, 35 45, 39 55, 43 69), (88 124, 81 109, 74 93, 83 82, 99 82, 112 82, 121 96, 114 109, 110 122, 103 138, 92 138, 88 124))
</programlisting>
- </para>
- </entry>
- </row>
- </tbody>
- </tgroup>
-</informaltable>
+</para>
+
+<para>Using with ST_Collect to compute the concave hull of a geometry set.</para>
+
+<programlisting>
+-- Compute estimate of infected area based on point observations
+SELECT disease_type,
+ ST_ConcaveHull( ST_Collect(obs_pnt), 0.3 ) AS geom
+ FROM disease_obs
+ GROUP BY disease_type;
+</programlisting>
+
</refsection>
+
<refsection>
<title>See Also</title>
- <para><xref linkend="ST_Collect" />, <xref linkend="ST_ConvexHull" />, <xref linkend="ST_SimplifyPreserveTopology" />, <xref linkend="ST_SnapToGrid" /></para>
+ <para><xref linkend="ST_ConvexHull" />, <xref linkend="ST_Collect" /></para>
</refsection>
</refentry>
@@ -841,7 +747,8 @@ SELECT ST_ConcaveHull(ST_GeomFromText('MULTILINESTRING((106 164,30 112,74 70,82
geometry that encloses all geometries in the input.</para>
<para>One can think of the convex hull as the geometry obtained by wrapping an rubber
- band around a set of geometries. This is different from a concave hull
+ band around a set of geometries. This is different from a
+ <link linkend="ST_ConcaveHull">concave hull</link>
which is analogous to "shrink-wrapping" the geometries.
A convex hull is often used to
determine an affected area based on a set of point observations.</para>
diff --git a/liblwgeom/liblwgeom.h.in b/liblwgeom/liblwgeom.h.in
index c48d58751..d1a1e4974 100644
--- a/liblwgeom/liblwgeom.h.in
+++ b/liblwgeom/liblwgeom.h.in
@@ -2535,6 +2535,20 @@ LWGEOM* lwgeom_delaunay_triangulation(const LWGEOM *geom, double tolerance, int3
*/
LWGEOM* lwgeom_voronoi_diagram(const LWGEOM* g, const GBOX* env, double tolerance, int output_edges);
+/**
+ * Take a geometry and build the concave hull. The concave
+ * hull is smaller than the convex hull, but still encompasses all the points
+ * of the input. For polygon input the hull encompasses all the input
+ * area. For line input the hull encompasses all the input lines.
+ *
+ * @param g the input geometry
+ * @param ratio proportion of output vs input
+ * @param allow_holes can there be holes in the output. large performance penalty.
+ */
+#if POSTGIS_GEOS_VERSION >= 31100
+LWGEOM* lwgeom_concavehull(const LWGEOM* geom, double ratio, uint32_t allow_holes);
+#endif
+
/**
* Take a list of LWGEOMs and a number of clusters and return an integer
* array indicating which cluster each geometry is in.
diff --git a/liblwgeom/lwgeom_geos.c b/liblwgeom/lwgeom_geos.c
index 77c40ec81..e3f321e04 100644
--- a/liblwgeom/lwgeom_geos.c
+++ b/liblwgeom/lwgeom_geos.c
@@ -2090,3 +2090,32 @@ lwgeom_voronoi_diagram(const LWGEOM* g, const GBOX* env, double tolerance, int o
return lwgeom_result;
}
+
+
+#if POSTGIS_GEOS_VERSION >= 31100
+LWGEOM*
+lwgeom_concavehull(const LWGEOM* geom, double ratio, uint32_t allow_holes)
+{
+ LWGEOM* result;
+ int32_t srid = RESULT_SRID(geom);
+ uint8_t is3d = FLAGS_GET_Z(geom->flags);
+ GEOSGeometry *g1, *g3;
+
+ initGEOS(lwnotice, lwgeom_geos_error);
+
+ if (!(g1 = LWGEOM2GEOS(geom, AUTOFIX))) GEOS_FAIL();
+
+ g3 = GEOSConcaveHull(g1, ratio, allow_holes);
+
+ if (!g3)
+ GEOS_FREE_AND_FAIL(g1);
+
+ GEOSSetSRID(g3, srid);
+
+ if (!(result = GEOS2LWGEOM(g3, is3d)))
+ GEOS_FREE_AND_FAIL(g1, g3);
+
+ GEOS_FREE(g1, g3);
+ return result;
+}
+#endif
diff --git a/postgis/lwgeom_geos.c b/postgis/lwgeom_geos.c
index 499f95c58..449d4e0f3 100644
--- a/postgis/lwgeom_geos.c
+++ b/postgis/lwgeom_geos.c
@@ -105,6 +105,7 @@ Datum ST_Equals(PG_FUNCTION_ARGS);
Datum ST_BuildArea(PG_FUNCTION_ARGS);
Datum ST_DelaunayTriangles(PG_FUNCTION_ARGS);
Datum ST_MaximumInscribedCircle(PG_FUNCTION_ARGS);
+Datum ST_ConcaveHull(PG_FUNCTION_ARGS);
Datum pgis_union_geometry_array(PG_FUNCTION_ARGS);
Datum pgis_geometry_union_finalfn(PG_FUNCTION_ARGS);
@@ -889,6 +890,35 @@ Datum convexhull(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(result);
}
+
+PG_FUNCTION_INFO_V1(ST_ConcaveHull);
+Datum ST_ConcaveHull(PG_FUNCTION_ARGS)
+{
+#if POSTGIS_GEOS_VERSION < 31100
+
+ lwpgerror("The GEOS version this PostGIS binary "
+ "was compiled against (%d) doesn't support "
+ "'GEOSConcaveHull' function (3.11.0+ required)",
+ POSTGIS_GEOS_VERSION);
+ PG_RETURN_NULL();
+
+#else /* POSTGIS_GEOS_VERSION >= 31100 */
+ GSERIALIZED* geom = PG_GETARG_GSERIALIZED_P(0);
+ double ratio = PG_GETARG_FLOAT8(1);
+ bool allow_holes = PG_GETARG_BOOL(2);
+
+ LWGEOM* lwgeom = lwgeom_from_gserialized(geom);
+ LWGEOM* lwresult = lwgeom_concavehull(lwgeom, ratio, allow_holes);
+ GSERIALIZED* result = geometry_serialize(lwresult);
+
+ lwgeom_free(lwgeom);
+ lwgeom_free(lwresult);
+ PG_FREE_IF_COPY(geom, 0);
+ PG_RETURN_POINTER(result);
+#endif
+}
+
+
PG_FUNCTION_INFO_V1(topologypreservesimplify);
Datum topologypreservesimplify(PG_FUNCTION_ARGS)
{
diff --git a/postgis/postgis.sql.in b/postgis/postgis.sql.in
index f3d3c4861..1f20e43c0 100644
--- a/postgis/postgis.sql.in
+++ b/postgis/postgis.sql.in
@@ -6425,6 +6425,23 @@ CREATE OR REPLACE FUNCTION ST_SquareGrid(size float8, bounds geometry, OUT geom
-- USER CONTRIBUTED
---------------------------------------------------------------
+
+#if POSTGIS_GEOS_VERSION >= 31100
+
+-- Availability: 3.3.0
+
+CREATE OR REPLACE FUNCTION ST_ConcaveHull(geom geometry, area_ratio float8, allow_holes boolean DEFAULT false)
+ RETURNS geometry
+ AS 'MODULE_PATHNAME', 'ST_ConcaveHull'
+ LANGUAGE 'c' IMMUTABLE STRICT
+ PARALLEL SAFE
+ _COST_HIGH;
+
+-- No longer needed with C language implementation
+DROP FUNCTION IF EXISTS _st_concavehull(geometry);
+
+#else
+
-- ST_ConcaveHull and Helper functions starts here --
-----------------------------------------------------------------------
-- Contributed by Regina Obe and Leo Hsu
@@ -6668,6 +6685,7 @@ $$
$$
LANGUAGE 'plpgsql' IMMUTABLE STRICT PARALLEL SAFE _COST_HIGH;
-- ST_ConcaveHull and Helper functions end here --
+#endif
-----------------------------------------------------------------------
-- X3D OUTPUT
diff --git a/regress/core/tests.mk.in b/regress/core/tests.mk.in
index 31663725d..2e4342230 100644
--- a/regress/core/tests.mk.in
+++ b/regress/core/tests.mk.in
@@ -34,7 +34,6 @@ TESTS += \
$(topsrcdir)/regress/core/chaikin \
$(topsrcdir)/regress/core/filterm \
$(topsrcdir)/regress/core/cluster \
- $(topsrcdir)/regress/core/concave_hull\
$(topsrcdir)/regress/core/ctors \
$(topsrcdir)/regress/core/curvetoline \
$(topsrcdir)/regress/core/dump \
@@ -170,6 +169,12 @@ ifeq ($(shell expr "$(POSTGIS_GEOS_VERSION)" ">=" 31000),1)
$(topsrcdir)/regress/core/geos310
endif
+# Only run the internal concavehull tests for GEOS < 3.11
+ifeq ($(shell expr "$(POSTGIS_GEOS_VERSION)" "<" 31100),1)
+ TESTS += \
+ $(topsrcdir)/regress/core/concave_hull
+endif
+
ifeq ($(INTERRUPTTESTS),yes)
# Allow CI servers to configure --with-interrupt-tests
TESTS += \
-----------------------------------------------------------------------
Summary of changes:
doc/html/image_src/Makefile.in | 6 -
doc/html/image_src/st_concavehull01.wkt | 4 +-
doc/html/image_src/st_concavehull02.wkt | 5 +-
doc/html/image_src/st_concavehull03.wkt | 3 -
doc/html/image_src/st_concavehull04.wkt | 2 -
doc/html/image_src/st_concavehull05.wkt | 1 -
doc/html/image_src/st_concavehull06.wkt | 1 -
doc/html/image_src/st_concavehull07.wkt | 2 -
doc/html/image_src/st_concavehull08.wkt | 2 -
doc/reference_processing.xml | 245 ++++++++++----------------------
liblwgeom/liblwgeom.h.in | 14 ++
liblwgeom/lwgeom_geos.c | 29 ++++
postgis/lwgeom_geos.c | 30 ++++
postgis/postgis.sql.in | 18 +++
regress/core/tests.mk.in | 7 +-
15 files changed, 177 insertions(+), 192 deletions(-)
delete mode 100644 doc/html/image_src/st_concavehull03.wkt
delete mode 100644 doc/html/image_src/st_concavehull04.wkt
delete mode 100644 doc/html/image_src/st_concavehull05.wkt
delete mode 100644 doc/html/image_src/st_concavehull06.wkt
delete mode 100644 doc/html/image_src/st_concavehull07.wkt
delete mode 100644 doc/html/image_src/st_concavehull08.wkt
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list