I talked about convex hulls some time ago in an alpha shape post.
The convex hull is probably one of the most basic computational geometry algorithms, and because of that it is present in almost, if not all, geometry/cad/gis libraries and software packages. In this post you will find an explanation of one of the existing algorithms to compute it, an implementation with C++, plus a set of scripts to generate various point clouds and the corresponding hulls.
- Describe one of the possible convex hull algorithms
- Implement the algorithm in C++
- Provide various scripts to generate random point clouds and compute its convex hulls
I won’t lie to you, this post might be boooring ;-).