Opened 11 years ago

Closed 10 years ago

#312 closed enhancement (fixed)

ST_ConcaveHull

Reported by: robe Owned by: robe
Priority: medium Milestone: PostGIS 2.0.0
Component: postgis Version: master
Keywords: history Cc:

Description

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.

Change History (8)

comment:1 Changed 11 years ago by 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

comment:2 Changed 11 years ago by robe

Owner: changed from pramsey to robe

comment:3 Changed 10 years ago by robe

Status: newassigned

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.

comment:4 Changed 10 years ago by robe

Milestone: PostGIS FuturePostGIS 2.0.0

comment:5 Changed 10 years ago by 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 ?)

comment:6 Changed 10 years ago by 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.

comment:7 Changed 10 years ago by robe

Keywords: history added

comment:8 Changed 10 years ago by robe

Resolution: fixed
Status: assignedclosed
Version: trunk

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.

Note: See TracTickets for help on using tickets.