ST_ConcaveHull

[robe]

This would be the hull that shrink-wraps (vacuum seals) a geometry as opposed to our ST_ConvexHull which wraps a rubber band around the geometries.

I have a version working which relies on Nicklas ST_ShortestLine/ST_ClosestPoint functions, but need to stress test it more on more obscure cases.

[havatv]

In general, there is no such thing as "the" ConcaveHull of a set of geometries. The reference I have seen solves this by including a "smoothness" parameter to the function. I think it would be useful to describe the intended behaviour of this function, with references to the algorithm that will be used. ​http://ubicomp.algoritmi.uminho.pt/local/concavehull.html

[robe]

at r5954 I think the performance is pretty decent. Will probably still make some minor tweaks, but seems to work well and reasonably fast even on 5000 line data set.

​http://www.postgis.org/documentation/manual-svn/ST_ConcaveHull.html

Still need to put together the regress test.

Anyone who is interested should try it. I'll close this out once I'bve put the regresson tests in place and fixed the documentation.

[etiennebr]

I must say it's a really nice feature. Though, I don't know, shouldn't it be called ​alpha shape or alpha hull ? Or maybe add a reference to it in the doc. Is the difference coming from the way the dimensions of the gap are specified ? As in alpha shape you use alpha directly as a way to specify the minimal gap between two points, while in the present function I understand it is specified in percent of the window size. (In fact, it's not really clear to me how the target percent is used even after looking at the examples. Can you deduce the distance between points with the target percent ?)

[robe]

Thought about calling it alpha hull, but didn't much like that term. The algorithms we used I couldn't really think of how it mapped to all those discussed in the literature.

The basic inspiration of it comes from a dream where you start with a Convex Hull and then you cave it (shrink wrap) in until you can cave it in no more. The percent target is meant to be the percent target of the convex hull. Well in theory if you think about it, you can't always hit your target percent and sometimes it even overshoots depending on how it slices up the geometry. So the function recurses trying to reach the target until it reaches a point where it can do no better (or hits one of those topological exceptions thrown by GEOS) and then exits with the best solution it had.

Right now we're tackling issues with GEOS with the tolerances causing problems and yielding too many topological exception errors (and fixing sometimes produces a concave hull that does not fully contain the geometry). Haven't revisited that yet -- but will soon once other tasks lighten up.

[robe]

finally got around to whipping up some regress tests. Still some speed improvement and cleanup to do, but its functional, documented, and tests in place for it now.