I recently bought a book on computational geometry, and have been working my way through it, implementing some of the algorithms as I go. Eventually I’d like to implement all of the algorithms in the book, and get them working on made up sample data. For some of them, however, I’d like to implement more practical projects.

The first algorithm in the book is the convex hull. The convex hull algorithm takes a set of points and computes the smallest convex polygon that contains every point in the set.

I tried to think of where I could get some interesting “real life” point data and one thing that came to mind was the track points from GPS tracks. I’m not sure how useful it is, but the results are kinda neat.

The picture above is the result of running the code on some ski tracks from A Basin. The green polygon is the convex hull. The white lines are the ski tracks.

The code could use some polishing, but its mostly straightforward. It basically just reads the track points from a GPX file, calculates the convex hull, and spits out some KML that can be loaded into Google Earth.

The next chapter focuses on finding all of the intersections in a set of line segments and various applications of that. The algorithms are a bit more complicated, but I’m hoping to have it implemented in the next few days, and hopefully I’ll be posting something about it in the next few days.

I’m keeping all of the CG code in GitHub.