I learned quite a bit while doing this project. I ended up implementing all the code by hand in a new technology for me. I opted to use 'Cython' which is a Python-variant that allows for optimizations on top of python code that get compiled to C code. The point for me here was to see how effective the implementation of the algorithms could be in python. I wanted to reap the benefits of python's syntax while not sacrificing speed. The implementation seems to be pretty effective and runs fairly quickly for the fact that it was implemented in python.
I realized there were a ton of intricacies in these algorithms and their implementations which shows me why most people do not reimplement the basics (its time consuming and hard!). I pulled my code form the O'Rourke book, and the algorithms seemed fine for triangulating but from time to time the translation from C to python, and a few other details added their fair share of complications.
I also had the opportunity to search for different algorithms for triangulation, and I found some that were n^3, n log* n, and even n, but the as the computational complexity lowered, the implementation complexity went up substantially. The problem here is that there is no standard set of data types for these algorithms, and so just taking the code directly and using it would be impossible, which raised the barrier for quick use (I was running low on time, and needed code quickly). It would be pretty cool if there could be some sort of standard for points/triangles/verticies/polygons/etc, so that it would be trivial to pull in different algorithms at will.
I also feel that the act of implementing the entire algorithm set (triangulation/file reading/etc) helped me to understand the algorithms in a deeper way and that was really cool. It was a ton of work, and worked out really well. Obviously my code isn't tested and maintained like many of the libraries that are already out there, and so there are inefficencies and possibly problems that I may not be aware of.
I opted, because of time constraints, for a simple and dumb graph coloring algorithm for finding guard points. It was a little clumbsy and memory-inefficient, but it got the job done.
