Is there an efficient algorithm to generate a 2D concave hull?

Question

Having a set of (2D) points from a GIS file (a city map), I need to generate the polygon that defines the 'contour' for that map (its boundary). Its input parameters would be the points set and a 'maximum edge length'. It would then output the corresponding (probably non-convex) polygon.

The best solution I found so far was to generate the Delaunay triangles and then remove the external edges that are longer than the maximum edge length. After all the external edges are shorter than that, I simply remove the internal edges and get the polygon I want. The problem is, this is very time-consuming and I'm wondering if there's a better way.

Answer 1

One of the former students in our lab used some applicable techniques for his PhD thesis. I believe one of them is called "alpha shapes" and is referenced in the following paper:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

That paper gives some further references you can follow.

Answer 2

A quick approximate solution (also useful for convex hulls) is to find the north and south bounds for each small element east-west.

Based on how much detail you want, create a fixed sized array of upper/lower bounds. For each point calculate which E-W column it is in and then update the upper/lower bounds for that column. After you processed all the points you can interpolate the upper/lower points for those columns that missed.

It's also worth doing a quick check beforehand for very long thin shapes and deciding wether to bin NS or Ew.

Answer 3

Good question! I haven't tried this out at all, but my first shot would be this iterative method:

1. Create a set N ("not contained"), and add all points in your set to N.
2. Pick 3 points from N at random to form an initial polygon P. Remove them from N.
3. Use some point-in-polygon algorithm and look at points in N. For each point in N, if it is now contained by P, remove it from N. As soon as you find a point in N that is still not contained in P, continue to step 3. If N becomes empty, you're done.
4. Call the point you found A. Find the line in P closest to A, and add A in the middle of it.
5. Go back to step 3

I think it would work as long as it performs well enough -- a good heuristic for your initial 3 points might help.

Good luck!

Answer 4

The guys here claim to have developed a k nearest neighbors approach to determining the concave hull of a set of points which behaves "almost linearly on the number of points". Sadly their paper seems to be very well guarded and you'll have to ask them for it.

Here's a good set of references that includes the above and might lead you to find a better approach.

Answer 5

A simple solution is to walk around the edge of the polygon. Given a current edge om the boundary connecting points P0 and P1, the next point on the boundary P2 will be the point with the smallest possible A, where

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

Then you set

P0 <- P1
P1 <- P2

and repeat until you get back where you started.

This is still O(N^2) so you'll want to sort your pointlist a little. You can limit the set of points you need to consider at each iteration if you sort points on, say, their bearing from the city's centroid.

Answer 6

Check thiis http://www.wipo.int/pctdb/en/wo.jsp?WO=2008107859&IA=IB2008050849&DISPLAY=DESC