none
Anything out there that creates a *concave* hull? RRS feed

Answers

  • The algorithms for concave hulls are much more complicated than convex hulls; one reason is that, for any given set of points, there may be lots of different concave hulls. (illustrated quite nicely on the page you linked to by the figures illustrating the "smoothing" of concave hulls based on different k values)

    I notice that the link you provide exposes an API, but doesn't give away any details of the algorithm used... the reason for this may or may not be related to the fact that there seems to be at least one patent application for the automatic calculation of a concave hull for an arbitrary set of points:
    http://www.wipo.int/pctdb/en/wo.jsp?WO=2008107859&IA=IB2008050849&DISPLAY=DESC

    Either way, I'm afraid that I don't think you're going to find an easy-to-implement algorithm anywhere.... (I certainly haven't!). Did you have a particular application in mind which you needed to use it for?
    Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290
    Monday, February 22, 2010 7:01 PM
    Answerer
  • I've taken a bit of a look at this and had some ideas but haven't put together a concrete algorithm yet. An idea for getting an approximate concave hull (they are approximate to begin with) would be to use the spatial tools in SQL to generate a buffer around each point (STBuffer) so that you get a bunch of circular polygons, and then take these polygons and merge them together using STUnion. This will generate a polygon or multiple polygon that is fatter than you want but then you could use STBuffer against this polygon using a negative buffer that is smaller than the radius of your original buffer. (assuming you have more than two points, other wise just generate a polyline). It will take a bit of practice to get the radius right. You could try to be fancy and precalculate the distances between each point and use half the average distance as your radius. Here is a simple example of the main idea:

    DECLARE @p1 geography;
    DECLARE @p2 geography;
    DECLARE @p3 geography;
    DECLARE @p4 geography;
    DECLARE @p5 geography;
    DECLARE @p6 geography;
    DECLARE @hull geography;
    
    SET @p1 = geography::Point(43.66427051353536, -79.42874908447267, 4326);
    SET @p2 = geography::Point(43.654707932931295, -79.41312789916993, 4326);
    SET @p3 = geography::Point(43.65098183989867, -79.43750381469728, 4326);
    SET @p4 = geography::Point(43.67693548309421, -79.44625854492187, 4326);
    SET @p5 = geography::Point(43.68798410652186, -79.4169044494629, 4326);
    SET @p6 = geography::Point(43.650360801917195, -79.39596176147462, 4326);
    
    SET @hull = @p1.STBuffer(1500).STUnion(@p2.STBuffer(1500)).STUnion(@p3.STBuffer(1500));
    SET @hull = @hull.STUnion(@p4.STBuffer(1500)).STUnion(@p5.STBuffer(1500)).STUnion(@p6.STBuffer(1500));
    
    --Concave hull
    SELECT @hull.STBuffer(-500);

    Windows Live Developer MVP - http://rbrundritt.spaces.live.com
    Tuesday, February 23, 2010 10:51 PM

All replies

  • The algorithms for concave hulls are much more complicated than convex hulls; one reason is that, for any given set of points, there may be lots of different concave hulls. (illustrated quite nicely on the page you linked to by the figures illustrating the "smoothing" of concave hulls based on different k values)

    I notice that the link you provide exposes an API, but doesn't give away any details of the algorithm used... the reason for this may or may not be related to the fact that there seems to be at least one patent application for the automatic calculation of a concave hull for an arbitrary set of points:
    http://www.wipo.int/pctdb/en/wo.jsp?WO=2008107859&IA=IB2008050849&DISPLAY=DESC

    Either way, I'm afraid that I don't think you're going to find an easy-to-implement algorithm anywhere.... (I certainly haven't!). Did you have a particular application in mind which you needed to use it for?
    Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290
    Monday, February 22, 2010 7:01 PM
    Answerer
  • I've taken a bit of a look at this and had some ideas but haven't put together a concrete algorithm yet. An idea for getting an approximate concave hull (they are approximate to begin with) would be to use the spatial tools in SQL to generate a buffer around each point (STBuffer) so that you get a bunch of circular polygons, and then take these polygons and merge them together using STUnion. This will generate a polygon or multiple polygon that is fatter than you want but then you could use STBuffer against this polygon using a negative buffer that is smaller than the radius of your original buffer. (assuming you have more than two points, other wise just generate a polyline). It will take a bit of practice to get the radius right. You could try to be fancy and precalculate the distances between each point and use half the average distance as your radius. Here is a simple example of the main idea:

    DECLARE @p1 geography;
    DECLARE @p2 geography;
    DECLARE @p3 geography;
    DECLARE @p4 geography;
    DECLARE @p5 geography;
    DECLARE @p6 geography;
    DECLARE @hull geography;
    
    SET @p1 = geography::Point(43.66427051353536, -79.42874908447267, 4326);
    SET @p2 = geography::Point(43.654707932931295, -79.41312789916993, 4326);
    SET @p3 = geography::Point(43.65098183989867, -79.43750381469728, 4326);
    SET @p4 = geography::Point(43.67693548309421, -79.44625854492187, 4326);
    SET @p5 = geography::Point(43.68798410652186, -79.4169044494629, 4326);
    SET @p6 = geography::Point(43.650360801917195, -79.39596176147462, 4326);
    
    SET @hull = @p1.STBuffer(1500).STUnion(@p2.STBuffer(1500)).STUnion(@p3.STBuffer(1500));
    SET @hull = @hull.STUnion(@p4.STBuffer(1500)).STUnion(@p5.STBuffer(1500)).STUnion(@p6.STBuffer(1500));
    
    --Concave hull
    SELECT @hull.STBuffer(-500);

    Windows Live Developer MVP - http://rbrundritt.spaces.live.com
    Tuesday, February 23, 2010 10:51 PM