Tagged with Alpha Shapes

Alpha Shapes for MapInfo

One recurring question which pops up on the MapInfo mailing list relates to creating a polygon which encloses a set of objects.  While this can sometimes be achieved with a Convex Hull, the results aren’t always that useful. For example, take a bunch of points in the shape of the letter A:

Using the standard Convex Hull creates a polygon which totally encloses all these points. However, the polygon doesn’t closely follow the visual shape of the points and covers a much larger area then one would expect:

Convex hull

Alpha shapes are an alternative solution to polygon wrapping. An alpha shape will wrap the input points in a different manner to convex hulls, which more closely follows the ‘visual’ outline created by the points:

Alpha Shape

Mathematically, the concept of alpha shapes is well defined and they can be easily created from subsets of the Delaunay triangulations of an input set. Unfortunately, MapInfo doesn’t include any built-in methods for creating Delaunay triangulations, but it does have a tool for creating Voronoi diagrams. Lucky for us it’s possible to transform a Voronoi diagram into Delaunay triangles.

Ok, now all that background information is out of the way, it’s time to announce mi-alphashapes, a MapBasic based tool for creating alpha shapes in MapInfo!

mi-alphashapes in action

To use, simply load the mbx file and choose Alpha Shapes from the menu. You’ll need to enter an appropriate alpha value – larger values will cause the resultant polygon to behave more like a Convex Hull, smaller values will wrap the points more tightly but may result in multiple shapes. While the extension automatically calculates a sensible default value, you may need to experiment with this to get the best results. This is easy under MapInfo 10.5+, since the extension includes a handy preview window. Additionally, the tool also includes a routine for creating Delaunay triangulations.

Warning: You may run into problems if you’re not using projected coordinates.

I’ve uploaded all the source to GitHub, under a Public Domain license. Feel free to do with it what you will. Otherwise, compiled versions for both MapInfo 8.5+ and MapInfo 10.5+ are available here.

Tagged , ,