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

algorithm geometry 2d gis concave-hull
Fabio Ceconello picture Fabio Ceconello · Sep 17, 2008 · Viewed 30.1k times · Source

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

nsanders picture nsanders · Sep 17, 2008

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.

Related questions

How do I calculate the area of a 2d polygon?

Assuming a series of points in 2d space that do not self-intersect, what is an efficient method of determining the area of the resulting polygon? As a side note, this is not homework and I am not looking for code. …

Read More
Simple 2d polygon triangulation

Trying to triangulate a set of simple 2d polygons, I've come up with this algorithm: 1) For each vertex in the polygon, compute the angle between the two linked edges 2) Sort vertices by decreasing angle relative to the interior of the …

Read More
How to draw a Perspective-Correct Grid in 2D

I have an application that defines a real world rectangle on top of an image/photograph, of course in 2D it may not be a rectangle because you are looking at it from an angle. The problem is, say that …

Read More