Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Convex Hull

A convex hull of a shape is defined as:

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X (Wikipedia)

Wikipedia visualizes it nicely using a rubber band analogy (image below), and there are some good algorithms to compute it.

alt text

Concave Hull

A concave hull is visualized using the red line in the image below (the blue line visualizes the convex hull). Intuitively, it is a polygon which embraces all the points, but has less (minimal?) area compared to the convex hull. As a result, the polygon's boundary length is longer.

A concave hull may be the solution for some real-world problems (e.g. finding the reasonable boundary of a city).

enter image description here

I have failed to find a proper definition, algorithm and practical solution for the notion of a Concave Hull. The Grass Wiki has some descriptions and images, and there is a commercial solution in concavehull.com.

Any ideas, algorithms and links will be very much appreciated.

Adam

share|improve this question
    
In what context to you want to generate concave hulls/alpha shapes? In PostGIS, ArcMap, a web-map, your own software? –  fmark Aug 17 '10 at 0:39
    
Both PostGIS and my own Python scripts. –  Adam Matan Aug 17 '10 at 5:29

15 Answers 15

up vote 32 down vote accepted

As scw points out, you want an implementation of α-shapes.

Alpha shapes can be considered a generalisation of the convex hull. They were first described in 1981 in:

Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R.; , "On the shape of a set of points in the plane," Information Theory, IEEE Transactions on , vol.29, no.4, pp. 551- 559, Jul 1983

Open source implementations exist for the environments you are interested in:

PostGIS

If you are using the PostGIS stack, pgRouting's optional Driving Distance extension exposes an alpha shape implementation. I'm not sure if you can vary the alpha parameter, however.

Usage is below:

SELECT the_geom AS alpha_shape 
FROM 
  points_as_polygon(
    'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

Python

There are probably many python modules you could use. I have heard good things about CGAL, a C++ computational geometry library. Python wrappers exist for parts of CGAL, including exposing CGAL's alpha shape implementation to Python.

Be aware that parts of CGAL are licensed under the QPL, which means that if you distribute your program, linked to CGAL, you may need to release it under the QPL. It is fine to keep your code proprietary if you do not redistribute your program code or binaries.

share|improve this answer
    
+1 Excellent, thanks. I'll try it right away. –  Adam Matan Aug 17 '10 at 8:19
    
I can't get the python wrappers of CGAL to compile---it seems that these haven't been supported in a while and no longer work with a recent version of CGAL. –  conradlee Jul 24 '11 at 22:16
    
@fmark: Second link you posted seems to be dead. –  radek Dec 6 '11 at 14:32

There is also Concave Hull Estimator script for ArcGIS:

Derives a polygon feature class that estimates the concave hull, or footprint, of an input point feature layer.

enter image description here

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

To help with the "proper definition" part of your question; you have looked at https://en.wikipedia.org/wiki/Convex_hull and gotten what could well be considered a "proper" definition but found it lacking, so perhaps a more "useful" definition

For every point inside a convex hull, a straight line to any point not within the hull will only intersect the hull once.

This is useful because given a point you can construct a line through it and test for that constructed line intersecting segments of the hull.

  • No intersection the point is not in the hull.
  • One intersection the point is on the hull.
  • Two intersections the point is within the hull
  • A straight line cannot intersect a convex hull more than twice
share|improve this answer

There is an implementation of ST_ConcaveHull in PostGIS trunk. http://postgis.net/docs/ST_ConcaveHull.html

/Nicklas

share|improve this answer
1  
I think this first appears in Version 2.0 of PostGis –  Adrian Aug 14 '11 at 14:42

You can download my php class concave-hull @ phpclasses.org. It uses a delaunay triangulation and it removes the longest edges. You can also try my example @ http://www.phpdevpad.de/geofence.

share|improve this answer

In response to Radek, the newest ArcGIS ToolBox that attempts this can be sourced here

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

    
Welcome to GIS Stack Exchange! Being new to the Q&A format of this site I hope you do not mind me suggesting that it would be better to simply edit @Radek's answer with that additional information rather than creating an additional answer for it. –  PolyGeo Aug 23 '13 at 8:43

There is a new Addon for GRASS GIS 7 available: v.concave.hull. See also http://grasswiki.osgeo.org/wiki/Create_concave_hull

share|improve this answer

Here is an R function that implements the Alpha Hull model. The output is an sp polygon object. Please see the example in the header. It requires the sp, alphahull and maptools packages.

######################################################################################
# PROGRAM: ConvexHull 
# USE: CREATE CONVEX HULL USING THE Pateiro-Lopez ALPHAHULL MODEL  
# REQUIRES: sp, alphahull, maptools 
#                                                                                                                                                                                                     
# ARGUMENTS:  
#       x          sp Points CLASS OBJECT                       
#       alpha      CONVEX HULL ALPHA VALUE (SEE ?alphahull)
#       increment  DEFAULT 360    
#       rnd        DEFAULT 2
# 
# VALUE:  
#      A sp SpatialPolygonsDataFrame OBJECT         
#
# NOTES:
#    THIS METHOD PROVIDES FLEXIBILITY OVER TRADITIONAL CONVEX FUNCTIONS. YOU CAN 
#      ADJUST THE ALPHA PARAMETER TO RELAX OR INCREASE TENSION BETWEEN EDGE-BOUNDARY
#      POINTS TO CREATE MORE OF AN EXACT FIT OF THE ENVELOPE (SEE EXAMPLE).
#
# REFERENCES:
#    Pateiro-López & Rodríguez-Casal (2009) Generalizing the Convex Hull of a Sample: 
#      The R Package alphahull. Journal of Statistical Software 34(5):1-28 
#      http://www.jstatsoft.org/v34/i05/paper
#                                                                       
# EXAMPLES: 
#    require(sp)
#    data(meuse)
#    coordinates(meuse) = ~x+y
#    a <- ConvexHull(meuse, alpha=100000)
#      plot(a)
#        points(meuse, pch=19)
#    # TEST MULTIPLE alpha VALUES
#    a=c(1000, 100000)
#     par(mfcol=c(1,2))
#       for (alpha in a) {
#       ch <- ConvexHull(meuse, alpha=alpha)
#         plot(ch)
#          points(meuse, pch=19) 
#       }
#                                                                                   
# CONTACT:
#     Jeffrey S. Evans
#     Senior Landscape Ecologist  
#     The Nature Conservancy
#     Central Science/DbyD
#     Affiliate Assistant Professor
#     Environment and Natural Resources
#     University of Wyoming
#     Laramie, WY 82070 
#     jeffrey_evans@tnc.org
#     (970) 672-6766
######################################################################################  
ConvexHull <- function(x, alpha=250000, increment=360, rnd=2)   {
    if (!require (sp)) stop("sp PACKAGE MISSING")
      if (!require (alphahull)) stop("sp PACKAGE MISSING")
        if (!require(maptools)) stop("maptools PACKAGE MISSING")
    if (!inherits(x, "SpatialPointsDataFrame") |  !inherits(x, "SpatialPoints") ) 
      stop(deparse(substitute(x)), " MUST BE A sp Points OBJECT")
        x.coords <- coordinates(x)    
    ahull2sp <- function(x, increment=360, rnd=10, proj4string=CRS(as.character(NA))){
      if (class(x) != "ahull")
        stop("x needs to be an ahull class object")
      xdf <- as.data.frame(x$arcs)
      xdf <- subset(xdf,xdf$r > 0)
      res <- NULL
      if (nrow(xdf) > 0){
        linesj <- list()
        prevx<-NULL
        prevy<-NULL
        j<-1
        for(i in 1:nrow(xdf)){
          rowi <- xdf[i,]
          v <- c(rowi$v.x, rowi$v.y)
          theta <- rowi$theta
          r <- rowi$r
          cc <- c(rowi$c1, rowi$c2)
          ipoints <- 2 + round(increment * (rowi$theta / 2),0)
          angles <- anglesArc(v, theta)
          seqang <- seq(angles[1], angles[2], length = ipoints)
          x <- round(cc[1] + r * cos(seqang),rnd)
          y <- round(cc[2] + r * sin(seqang),rnd)
          if (is.null(prevx)){
            prevx<-x
            prevy<-y
          } else if (x[1] == round(prevx[length(prevx)],rnd) && y[1] == round(prevy[length(prevy)],rnd)){
              if (i == nrow(xdf)){
                prevx<-append(prevx,x[2:ipoints])
                prevy<-append(prevy,y[2:ipoints])
                prevx[length(prevx)]<-prevx[1]
                prevy[length(prevy)]<-prevy[1]
                coordsj<-cbind(prevx,prevy)
                colnames(coordsj)<-NULL
                linej <- Line(coordsj)
                linesj[[j]] <- Lines(linej, ID = as.character(j))
              } else {
                prevx<-append(prevx,x[2:ipoints])
                prevy<-append(prevy,y[2:ipoints])
              }
            } else {
              prevx[length(prevx)]<-prevx[1]
              prevy[length(prevy)]<-prevy[1]
              coordsj<-cbind(prevx,prevy)
              colnames(coordsj)<-NULL
              linej <- Line(coordsj)
              linesj[[j]] <- Lines(linej, ID = as.character(j))
              j<-j+1
              prevx<-NULL
              prevy<-NULL
            }
        }
        lspl <- SpatialLines(linesj)
        lns <- slot(lspl, "lines")
        polys <- sapply(lns, function(x) { 
          crds <- slot(slot(x, "Lines")[[1]], "coords")
          identical(crds[1, ], crds[nrow(crds), ])
        }) 
        polyssl <- lspl[polys]
        list_of_Lines <- slot(polyssl, "lines")
        sppolys <- SpatialPolygons(list(Polygons(lapply(list_of_Lines, function(x) {
    Polygon(slot(slot(x, "Lines")[[1]], "coords")) }), ID = "1")), proj4string=proj4string)
        hid <- sapply(slot(sppolys, "polygons"), function(x) slot(x, "ID"))
          areas <- sapply(slot(sppolys, "polygons"), function(x) slot(x, "area"))
          df <- data.frame(hid,areas)
            names(df) <- c("HID","Area")
            rownames(df) <- df$HID
        res <- SpatialPolygonsDataFrame(sppolys, data=df)
       res <- res[which(res@data$Area > 0),]
      }  
      return(res)
  }
   a <- ahull(x.coords, alpha=alpha)
    return(ahull2sp(a, rnd=rnd)) 
}
share|improve this answer
    
+1 Could you explain how this differs from the alpha shapes package? –  whuber Aug 14 '12 at 19:07
2  
The output of alphahull object is stored as a matrix and must be coerced to a usable sp object. I would consider this a "helper" function to create a polygon that can be exported to a GIS format. This function uses the alphahull package to create the hull matrix object, creates an sp object and then explodes the polygon slot so it is a single-part polygon dataframe object. Nothing is showing up in the package help but there may be newly implemented native coercion to an sp class object that I am not aware of. If this is the case please let me know so I can decommission this function. –  Jeffrey Evans Aug 14 '12 at 21:13
    
What's the programming language? –  Adam Matan Aug 15 '12 at 8:07

I created a highly-efficient tool, called [lasboundary][1,2], that computes a concave hull for LIDAR in LAS/LAZ/SHP/ASCII format and stores the result as a vector boundary polygon in ESRI Shapefile format or a geo-referenced KML file.

Here is an example run:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Some result pictures are here.

share|improve this answer
1  
+1 Nice work! Thank you for your contribution. –  whuber Aug 29 '11 at 15:00

Here's a program written in C that computes convex hulls, alpha shapes, Delauney triangluations and Voronoi volumes:

  • Hull - Ken Clarkson (2002)

Another convex hull algorithm with C and Java implementations is here:

share|improve this answer

Speaking about JTS, you can use Geoscript for manipulating JTS library. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html for an article about convex hull. GeoScript implementations are available in JavaScript, Python, Scala, and Groovy. The official website : http://geoscript.org

share|improve this answer

Here is what you are looking for.

You can download and test the program: (in java, under GPL license)

alt text

The paper presenting the algorithm is there:

Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

share|improve this answer

About R implementation Alpha-Shapes, there's an article about "Converting Alpha-Shapes into SP Objects"

It's based on alphahull, sp and spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919

share|improve this answer

This seems to be a specific application of alpha shapes, which are from my reading a more general form of this problem. R has the alphahull module, which has excellent documentation on computing alpha shapes. Also check this detailed background on alpha shapes. If you only want to compute convex/concave hulls, check out lasboundary, part of lastools, it scales well and can handle millions of input points.

Finally, this interesting application of alpha shapes by Flickr made the rounds a while ago, showing their utility for aggregating user generated point content:

alpha hull of texas from flickr

share|improve this answer
    
+1 Neat. Will look into it. –  Adam Matan Aug 16 '10 at 7:41
    
OMG the source is written in FORTRAN :-) –  Adam Matan Aug 16 '10 at 7:51
    
There's the clustr package written in C++ if that suits you better; but be careful with the licensing on CGAL: github.com/straup/Clustr –  scw Aug 16 '10 at 8:11
1  
Nice real-world example. –  DavidF Aug 16 '10 at 13:23

JTS (http://tsusiatsoftware.net/jts/main.html) provides a Convex Hull implementation. Martin Davies also mentioned having an Alpha Shape algorithm in the works so you might want to check the SVN repository to see if it is in yet if that's what you want.

share|improve this answer
    
Still no concave hull/alpha shapes implementation as of June 2012 as far as I can tell. –  blah238 Jun 5 '12 at 5:54
    
Still nothing in May 2013. –  Crescent Fresh May 1 '13 at 17:42
    
Is JTS alive? Last version is from Dec 19, 2006. vividsolutions.com/jts/JTSHome.htm –  angelcervera Aug 25 '13 at 21:57
    
try the link in the answer –  iant Aug 26 '13 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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