3

I am trying to run a st_concavehull after st_boundary/st_exteriorring on polygons, however st_concavehull doesnt seem to reinclose the polygon properly. For example

enter image description here

SELECT ST_GeomFromText('POLYGON((-123.11897224620935 49.277180232191874,-123.1190714879429 49.277147859512795,-123.11909831003305 49.27705424110504,-123.11896889344808 49.277020993403475,-123.11885959343073 49.27706517784409,-123.11901046768781 49.27707961433591,-123.11896889344808 49.277129923289536,-123.11886898116228 49.277155296481496,-123.11897224620935 49.277180232191874))')

Becomes

enter image description here

SELECT ST_ConcaveHULL(ST_boundary(ST_geomFromText('POLYGON((-123.11897224620935 49.277180232191874,-123.1190714879429 49.277147859512795,-123.11909831003305 49.27705424110504,-123.11896889344808 49.277020993403475,-123.11885959343073 49.27706517784409,-123.11901046768781 49.27707961433591,-123.11896889344808 49.277129923289536,-123.11886898116228 49.277155296481496,-123.11897224620935 49.277180232191874))')),0.80)

Why does it become like this? I expected it to return the exact same polygon.

  • I suspect it is to do with your target percentage value you have chosen? – Hornbydd Nov 20 '18 at 22:22
  • i tried all the target_percentages already 1%, 99%, 100% yields (relatively) same (wrong) results – Newton Nov 20 '18 at 22:40
  • If you get rid of the st_boundary, it works (even with 0.99). – JGH Nov 21 '18 at 23:53
  • i am trying to remove 'loops' in the polygon and thus st_boundary is a requirement. Judging from the output of the polygon after st_boundary shouldnt i get something that resembles my original polygon or am i understanding st_concavehull wrong? – Newton Nov 22 '18 at 19:03
  • what exactly do you mean by "loops"? as in "self intersecting loops"? if so, try SELECT ST_ExteriorRing(ST_MakeValid(<geom>)) AS geom FROM <your_layer>; instead. not exactly solving the question, but maybe the issue... – ThingumaBob Nov 28 '18 at 12:37
3

Looking at the code and at this algorithm description (not the PostGIS one), it appears that the amount of input point does matter. The algorithm needs to look at nearby points to find the concave hull. In your example, the input vertices "inside" the main polygon are closer to the boundary on the other side of the polygon than from their connected vertices.

If we densify the input, the output shape is changed somewhat closer to the original shape.

SELECT st_asText(ST_ConcaveHULL(ST_Segmentize(ST_geomFromText('LINESTRING(-123.118972246209 49.2771802321919,-123.119071487943 49.2771478595128,-123.119098310033 49.277054241105,-123.118968893448 49.2770209934035,-123.118859593431 49.2770651778441,-123.119010467688 49.2770796143359,-123.118968893448 49.2771299232895,-123.118868981162 49.2771552964815,-123.118972246209 49.2771802321919)'),0.00001),0.65));

enter image description here

Using a smaller target percentage fails with an error. The max distance between vertices was somewhat randomly chosen. The used linestring is the output of st_boundary on the original polygon.

To get closer to the original shape, one might want to draw the convex hull, then to identify segment/vertices that are inside, then densify the vertices on those segments and at last compute the concave hull.... that sounds rater cumbersome though.

At this point, I am not sure if your input is a special case ("inside" vertices closer to other edge than to connected vertices) or if this is simply the expected algorithm behavior for small inputs.

On a side note, using the polygon directly works because the code is instructed to return the original polygon for any target percentage less than 1!

  • +1 for research. that algorithm is not more than a 'proof of concept' in my eyes; it doesn't guarantee the same results on multiple iterations (AFAIK). the task it is made for is somewhat unsolvable without a degree of interpretation; in the above example, the inbound 'curve' can easily be spanned between other vertices. no way for an algorithm to know what is expected of it without 'knowing' the context. the target percentage also quite directly refers to an approximation and convergence of/with the given percentage of convex hull area... – ThingumaBob Nov 28 '18 at 12:47
0

Newton, this problem is most detailed in the link (especially in the note) http://www.bostongis.com/postgis_concavehull.snippet, in General, deceive us with you : -), the maximum of your code: SELECT (ST_ConcaveHull(ST_Boundary(ST_GeomFromText ('POLYGON((-123.11897224620935 49.277180232191874, -123.1190714879429 49.277147859512795, -123.11909831003305 49.27705424110504, -123.11896889344808 49.277020993403475, -123.11885959343073 49.27706517784409, -123.11901046768781 49.27707961433591, -123.11896889344808 49.277129923289536, -123.11886898116228 49.277155296481496, -123.11897224620935 49.277180232191874))')),0.99)) you can get the result shown in the figure enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.