Algorithm to create a list of points bounding a collection of points

Question

Any idea where I can find an algorithm to create a list of 2D points that defines a boundary encompassing a collection of points? The algorithm should take a maximum length parameter to limit the length of a side and better control the boundary granularity.

This will be used in a GIS-type application. I've used this type of command in engineering apps for analyzing survey data but can't find a starting point for writing my own function.

Sample code is appreciated but at this point, I'm really looking for a starting point.

Thanks!

Answer 1

One solution could be to do a triangulation [0]. Postgis has such function, based on GEOS which uses JTS Topology suite. Everything is open source, so you can download the source code to get an example.

You would get a collection of triangles. From this, you would just unify the multipolygon to a single polygon. Then, you can use a simplification algorithm such as Douglas-Peucker [1] also implemented in Posgis.

I hope it's a start!

[0] http://en.wikipedia.org/wiki/Delaunay_triangulation

[1] http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm